Chi tiết bài học Danh sách liên kết đơn

Danh sách liên kết là một cấu trúc dữ liệu gồm các node và các liên kết giữa các node đó. Mỗi node được kết nối với một node khác (trong trường hợp danh sách liên kết đơn) hoặc hai node (trong trường hợp danh sách liên kết kép) bằng con trỏ.

Các node gồm hai phần chính là phần dữ liệu và phần liên kết (các con trỏ để trỏ tới node khác), và phần bộ nhớ dánh cho chúng có thể được cấp phát bằng phương thức cấp phát động.

Trong thực tế chúng ta không nhất thiết phải dùng cấp phát động để xây dựng danh sách liên kết, còn có một cách khác nữa đó là dùng mảng. Nhưng cách dùng cấp phát động hay được sử dụng hơn và có nhiều ưu điểm hơn.

Một node trong danh sách liên kết đơn được cấu thành từ hai thành phần là dữ liệu và phần kết nối.

Xây dựng danh sách liên kết bởi liên kết các node với nhau.

Các điểm mạnh và điểm yếu của danh sách liên kết so với mảng:

Cả danh sách liên kết và mảng đều có thể được sử dụng để chứa các dữ liệu cùng kiểu.Nhưng chúng lại có những đặc điểm riêng, và ưu điểm của cái này lại là nhược điểm của cái còn lại.

Điểm mạnh:

Danh sách liên kết có kích thước động, có thể mở rộng hay thu hẹp rất dễ ràng.
Việc chèn hay xóa một phần tử trong danh sách liên kết là rất dễ dàng, ta chỉ cần thay đổi vị trí trỏ của các con trỏ thay vì phải dịch toàn bộ phần dữ liệu còn lại. Xem ví dụ sau khi ta muốn chèn node C vào giữa node A và B:

Trước khi chèn:

Sau khi chèn:

Điểm yếu:

Danh sách liên kết mang yếu điểm của cấp phát động về hiệu năng. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm tốt hơn (là các khối các ô nhớ liên tiếp) so với danh sách liên kết.
Ta không thể truy cập ngẫu nhiên một phần tử trong danh sách liên kết ngay lập tức, mà phải thực hiện duyệt từ đầu danh sách cho tới khi gặp phần tử đó. Do vậy ta không thể thực hiện tìm kiếm nhị phân với các danh sách liên kết.
Cần thêm không gian bộ nhớ cho con trỏ trong mỗi phần tử của danh sách liên kết.

Xây dựng danh sách liên kết đơn với C/C++

Để xây dựng một danh sách sách liên kết trước hết ta cần biết được danh sách liên kết cần bao gồm những thành phần nào và các thao tác mà ta có thể thực hiện với danh sách liên kết:

Các thành phần của danh sách liên kết đơn bao gồm:

Các node: Mỗi node bao gồm hai thành phần: phần dữ liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node tiếp theo, nói cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node cuối cùng của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả.
```
struct node {
    int data; /* Phần dữ liệu của một node*/
    struct node* next; /* Con trỏ tới node kế tiếp */
};
```
Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết.
```
struct node * head; /* Con trỏ tới head node */
```

Các thao tác chính với danh sách liên kết đơn:

Tạo một node mới và trả về con trỏ tới node đó.

/* Tạo một node mới và trả về con trỏ tới node đó. */
struct node* NewNode(int x) {
          struct node* new_node
                   = (struct node*)malloc(sizeof(struct node)); /* Cấp phát bộ nhớ cho node */
          new_node->data = x;
          new_node->next = NULL;
          return new_node;
}

Chèn một phần tử vào danh sách.

/* Chèn node vào vị trí cuối của danh sách liên kết */
void InsertAtTail(int x) {
          struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp  làm thay đổi vị trí trỏ của con trỏ head */
          struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần dữ liệu là tham số được truyền vào */
          if(head == NULL) { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */
                   head = new_node;
                   return;
          }
          while(temp->next != NULL) temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */
          temp->next = new_node; /* Chèn node mới vào cuối danh sách */
}

Xóa một phần tử khỏi danh sách.

struct node* Delete(struct node *head, int position)

{
    struct node *prev = NULL; /* Con trỏ lưu node ngay trước node cần xóa */
    struct node *ptr = head; /* Tạo ra bản sao của con trỏ head, tránh làm thay đổi vị trí trỏ của con trỏ head khi duyệt danh sách*/

    int pos = 0; /* Biến lưu vị trí các phần tử trong danh sách */
    if(position==0) /* Trường hợp xóa phần tử ở đầu danh sách */
    {
        head=head->next; /* Trả về vị trí của phần tử tiếp theo, vị trí trỏ của head thay đổi */
        free(ptr); /* Thu hồi bộ nhớ của phần tử cần được xóa */
    }
    else
    {
        while(position!=pos) /*Duyệt danh sách, lặp cho tới khi tìm thấy vị trí cần xóa */
        {
            ++pos;
            prev=ptr;
            ptr=ptr->next;
        }
        /* Sau vòng lặp tìm được node cần xóa là ptr, địa chỉ node ngay trước node cần xóa được lưu trữ trong prev */
        if(ptr!=NULL) /* Nếu tìm tháy node cần xóa trong danh sách, thực hiện xóa */

        {
            prev->next=ptr->next;
            free(ptr);
        }
    }
    return head;
}

Hiển thị tất cả các node trong danh sách.

void Display() {
          struct node* temp = head;
          while(temp != NULL) {
                   printf("%d ",temp->data);
                   temp = temp->next;
          }
          printf("n");
}

Ứng dụng của danh sách liên kết đơn trong thực tế:

Danh sách liên kết đơn chủ yếu được dùng để xây dựng các loại cấu trúc dữ liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị …

Đôi khi ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả các node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau.

struct node {
    int data;
    struct node* next;
    struct node* prev;
};

Cấu trúc trên chính là cấu trúc của danh sách liên kết kép.

Để hiểu hơn về danh sách liên kết kép mời bạn đọc bài tiếp theo.

Bạn cũng có thể đọc thêm các bài toán về danh sách liên kết đơn tại các đường dẫn sau:

In danh sách theo vị trí đảo ngược.
Phát hiện điểm nối của danh sách liên kết.
Xóa các node trùng lặp trong danh sách.
So sánh hai danh sách liên kết.
Kết hợp hai danh sách đã được sắp xếp.

Uncategorized

Danh sách liên kết đơn

Điểm mạnh:

Điểm yếu:

Xây dựng danh sách liên kết đơn với C/C++

Để lại một bình luận Hủy