Ninja IT

Danh sách liên kết

Danh sách liên kết

Danh sách liên kết là tập hợp các dữ liệu mà một phần tử trỏ đến phần tử tiếp theo. Mỗi phần tử chỉ thường có hai phần đó chính là dữ liệu và tham chiếu đến phần tử tiếp theo.

Lợi ích chính khi sử dụng danh sách liên kết là thao tác xóa hoặc thêm một phần tử chỉ mất thời gian cố định O(1).

Cài đặt danh sách liên kết

Khởi tạo danh sách liên kết

Ví dụ sau đây sẽ khởi tạo danh sách liên kết với dữ liệu trong bộ nhớ heap với ba node có các giá trị 12, 22, 34.

 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

typedef struct Node {
  int data;
  struct Node* next;
} Node;

int main() {
  // Tạo bộ nhớ của node trong Heap
  Node* node1 = malloc(sizeof(Node));
  Node* node2 = malloc(sizeof(Node));
  Node* node3 = malloc(sizeof(Node));
  
  // Khởi tạo giá trị
  node1->data = 12;
  node2->data = 22;
  node3->data = 34;

  // liên kết các node
  node1->next = node2;
  node2->next = node3;
  node3->next = NULL;

  // xóa bộ nhớ của node khi sử dụng xong
  free(node1);
  free(node2);
  free(node3);
}

Vòng lặp duyệt qua các phần tử

Hàm printLinkedList sẽ in ra các giá trị của linked-list từ đầu đến cuối.
Kết quả sẽ in ra 12 -> 22 -> 34 -> null.

1
2
3
4
5
6
7
8
9

// print: 12 -> 22 -> 34 -> NULL
void printLinkedList(Node* head) {
  Node* node = head;
  while(node != NULL) {
    printf("%d -> ", node->data);
    node = node->next;
  }
  printf("NULL");
}

Loại bỏ một phần tử

Ví dụ sau loại bỏ phần tử thứ hai. Đầu tiên là phần tử đầu tiên tới phần tử thứ ba, sau đó mới xóa phần tử thứ hai.

1
2

node1->next = node3; // nối node1 vào node3
free(node2);          // xóa node2

Thêm một phần tử

Ví dụ sau chúng ta thêm một phần tử node11 vào giữa phần tử đầu tiên và phần tử thứ hai.
Đầu tiên là khởi tạo node11. Sau đó node1 sẽ nối vào node11 và node11 sẽ nối vào node2.

1
2
3
4
5
6

// Thêm node11 vào giữa node1 và node2
Node* node11 = malloc(sizeof(Node));
node11->data = 15;

node1->next = node11; // nối node1 vào node11
node11->next = node2; // nối node11 vào node2