Danh sách liên kết đơn hay danh sách kết nối đơn là một trong các danh sách liên kết thường hay được sử dụng. Trong bài viết này, ta sẽ cùng tìm hiểu kiểu danh sách này và phân biệt nó với cấu trúc dữ liệu mảng.
Danh sách liên kết đơn
Danh sách liên kết đơn là loại danh sách kết nối đơn hướng, tức là nó chỉ có thể được liên kết theo một hướng từ nút đầu đến nút cuối cùng. Mỗi phần tử trong danh sách liên kết được gọi là một nút. Mỗi nút duy nhất chứa một đơn vị dữ liệu và một con trỏ đến nút tiếp theo nhằm duy trì cấu trúc của danh sách liên kết.
Nút đầu tiên được gọi là phần tử đầu tiên, nó trỏ đến nút đầu tiên của danh sách và giúp chúng ta truy cập vào mọi phần tử khác trong danh sách. Nút cuối cùng, đôi khi còn được gọi là đuôi, có giá trị là NULL, giúp chúng ta xác định phần kết thúc của danh sách.
Hình dưới đây sẽ minh họa một danh sách liên kết đơn
Ví dụ: Triển khai danh sách liên kết đơn bằng ngôn ngữ lập trình C.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *next; }; struct node *first, *last = NULL; void add(int a) { struct node *newEle = (struct node*)malloc(sizeof(struct node)); //Khởi tạo nút newEle->data = a; //Thêm dữ liệu vào trong nút newEle->next = NULL; //Đặt con trỏ next = NULL để kết thúc danh sách if(first == NULL) { first = newEle; last = newEle; } else { last->next = newEle; last = newEle; } } int display() { struct node *trav = first; if(first == NULL) { printf("Danh sách rỗng\n"); return 0; } while(trav != NULL) { //Duyệt các nút cho tới khi gặp giá trị là NULL thì dừng printf("%d ", trav->data); //In ra dữ liệu của nút trav = trav->next; } printf("\n"); return 0; } int main() { add(32); add(24); add(43); display(); return 0; } |
Kết quả:
|
1 |
32 24 34 |
Hình bên dưới đây sẽ mô tả hình dáng của danh sách kết nối đơn trong đoạn mã trên.
Trong đoạn mã trên, ban đầu ta sẽ có hai con trỏ là first và last nhận giá trị NULL. Khi ta thêm một nút, ta sẽ cho con trỏ first và last trỏ tới nút mới được tạo này. Lúc này, first và last trỏ cùng vào một nút. Tiếp theo khi thêm phần tử thứ 2, ta sẽ cho con trỏ last trỏ tới nút mới được tạo này, con trỏ first sẽ giữ nguyên (vẫn trỏ vào nút ban đầu). Và khi thêm phần tử thứ 3, ta sẽ cho con trỏ last trỏ tới nút mới này và cứ như thế cho các phần tử sau. Cuối cùng, ta sẽ có được một danh sách liên kết và có thể sử dụng một con trỏ khác để duyệt danh sách liên kết, bắt đầu từ nút đầu tiên được trỏ bởi con trỏ first.
Các thao tác với danh sách kết nối đơn
1. Duyệt qua các nút trong danh sách
Ta chỉ có thể duyệt qua các nút trong danh sách theo thứ tự từ trái qua phải, cho tới khi gặp giá trị NULL thì dừng thao tác duyệt.
2. Tìm kiếm một nút trong danh sách
Ta có thể xác định và truy xuất một nút cụ thể từ đầu, phía cuối hoặc bất kỳ đâu trong danh sách. Ta sẽ lần lượt đi qua từng nút để kiểm tra xem dữ liệu cần tìm có trong nút đó hay không. Nếu có thì ta dừng lại và lấy dữ liệu ra, nếu không thì tiếp tục duyệt qua các nút sau.
Trường hợp xấu nhất là phần tử cần tìm nằm ở phía cuối danh sách, bởi nó sẽ mất nhiều thời gian hơn.
3. Thêm một nút vào danh sách
Ta có thể thêm một nút ở đầu, cuối hoặc bất kỳ đâu trong danh sách liên kết. Khi ta thêm một nút vào trong danh sách, ta sẽ thực hiện liên kết con trỏ Next của nút phía trước cho nút mới này. Và con trỏ Next của nút mới sẽ liên kết tới nút phía sau nó. Nếu thêm nút mới vào cuối danh sách thì chỉ cần gán con trỏ Next với giá trị là NULL.
4. Xóa một nút khỏi danh sách
Ta có thể xóa một nút từ đầu, phía cuối hoặc từ bất kỳ đâu trong danh sách. Ta chỉ đơn giản là gán con trỏ Next của nút phía trước cho nút phía sau nút bị xóa.
5. Thay đổi dữ liệu của nút trong danh sách
Ta có thể cập nhật hoặc thay đổi giá trị của các dữ liệu được lưu trữ trong các nút. Tương tự như tìm kiếm dữ liệu trong danh sách, khi tìm tới được nút cần thay đổi dữ liệu thì ta chỉ cần dừng lại và gán giá trị khác cho dữ liệu trong nút đó.
Sự khác biệt giữa danh sách liên kết và mảng
| Mảng | Danh sách liên kết |
| Dữ liệu chỉ có thể được lưu trữ trong các khối bộ nhớ liền nhau, nên kích thước của nó không thể thay đổi trong thời gian thực thi. | Mỗi nút trỏ đến nút tiếp theo để dữ liệu có thể tồn tại ở các địa chỉ không liền kề nhau, cho phép kích thước có thể thay đổi trong thời gian thực thi. |
| Việc xáo trộn một mảng sẽ phức tạp hơn và chiếm nhiều bộ nhớ hơn. | Việc xáo trộn danh sách liên kết chỉ là vấn đề thay đổi các nút trong danh sách, do đó sẽ dễ dàng hơn. |
| Mảng cho phép việc truy cập các phần tử một cách ngẫu nhiên bằng cách sử dụng chỉ số. | Danh sách liên kết chỉ cho phép truy cập các phần tử theo thứ tự từ đầu đến cuối. |
| Kích thước của một mảng được biết trước hoặc được tạo lại khi nó cần phát triển lớn hơn. Bởi vì không gian bộ nhớ được phân bổ cho mảng trong thời gian biên dịch, tức là kích thước của nó được cố định khi ta khai báo nó. | Danh sách liên kết phát triển một cách tự nhiên, theo thứ tự được thêm dữ liệu. Không gian bộ nhớ được phân bổ cho danh sách liên kết trong thời gian thực thi, tức là kích thước của nó có thể tăng hoặc giảm trong khi chương trình đang thực thi. |
| Một mảng sẽ giả định rằng mọi phần tử đều có cùng kích thước vì các phần tử của mảng phải có cùng kiểu dữ liệu. | Dễ dàng lưu trữ dữ liệu có kích thước khác nhau trong danh sách liên kết. |
| Mảng có kiểu mảng một chiều, mảng hai chiều hoặc mảng đa chiều. | Danh sách liên kết có kiểu danh sách liên kết đơn, đôi hoặc vòng. |
Trên đây là khái niệm và ví dụ cơ bản về danh sách kết nối đơn và sự khác biệt giữa nó với cấu trúc dữ liệu kiểu mảng. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!
P/s: Cảm ơn mọi người!
| Bài trước: Danh sách liên kết | Bài tiếp theo: Danh sách liên kết đôi |
