Trong hướng dẫn này, bạn sẽ tìm hiểu các loại danh sách liên kết khác nhau. Ngoài ra, bạn sẽ tìm thấy việc triển khai danh sách liên kết trong C.
Trước khi bạn tìm hiểu về loại danh sách được liên kết, hãy đảm bảo rằng bạn biết về Cấu trúc dữ liệu LinkedList.
Có ba loại Danh sách liên kết phổ biến.
- Danh sách liên kết Singly
- Danh sách được liên kết gấp đôi
- Danh sách liên kết hình tròn
Danh sách liên kết Singly
Nó là phổ biến nhất. Mỗi nút có dữ liệu và một con trỏ đến nút tiếp theo.
Danh sách liên kết Singly
Nút được biểu diễn dưới dạng:
struct node ( int data; struct node *next; )
Một danh sách liên kết đơn gồm ba thành viên có thể được tạo như sau:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Danh sách được liên kết gấp đôi
Chúng tôi thêm một con trỏ vào nút trước đó trong danh sách được liên kết kép. Do đó, chúng ta có thể đi theo một trong hai hướng: tiến hoặc lùi.
Danh sách liên kết kép
Một nút được biểu thị là
struct node ( int data; struct node *next; struct node *prev; )
Một danh sách liên kết kép ba thành viên có thể được tạo như
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Danh sách liên kết hình tròn
Danh sách liên kết vòng tròn là một biến thể của danh sách liên kết trong đó phần tử cuối cùng được liên kết với phần tử đầu tiên. Điều này tạo thành một vòng tròn.
Danh sách liên kết tròn
Danh sách liên kết vòng tròn có thể được liên kết đơn lẻ hoặc liên kết kép.
- đối với danh sách được liên kết đơn lẻ, con trỏ tiếp theo của mục cuối cùng trỏ đến mục đầu tiên
- Trong danh sách được liên kết kép, con trỏ trước đó của mục đầu tiên cũng trỏ đến mục cuối cùng.
Một danh sách liên kết đơn lẻ của vòng tròn ba thành viên có thể được tạo như:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
