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

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

Danh sách liên kết là một cấu trúc tài liệu gồm những node và những liên kết giữa những node đó. Mỗi node được liên kết với một node khác ( trong trường hợp danh sách liên kết đơn ) hoặc hai node ( trong trường hợp danh sách liên kết kép ) bằng con trỏ .
Các node gồm hai phần chính là phần tài liệu và phần liên kết ( những con trỏ để trỏ tới node khác ), và phần bộ nhớ dánh cho chúng hoàn toàn có thể được cấp phép bằng phương pháp cấp phát động .

Trong thực tế chúng ta không nhất thiết phải dùng cấp phát động để xây dựng danh sách liên kết, còn có một cách khác nữa đó là dùng mảng. Nhưng cách dùng cấp phát động hay được sử dụng hơn và có nhiều ưu điểm hơn.

Một node trong danh sách liên kết đơn được cấu thành từ hai thành phần là tài liệu và phần liên kết .

Xây dựng danh sách liên kết bởi liên kết những node với nhau .

Các điểm mạnh và điểm yếu của danh sách liên kết so với mảng:

Cả danh sách liên kết và mảng đều hoàn toàn có thể được sử dụng để chứa những tài liệu cùng kiểu. Nhưng chúng lại có những đặc thù riêng, và ưu điểm của cái này lại là điểm yếu kém của cái còn lại .

Điểm mạnh :

  • Danh sách liên kết có size động, hoàn toàn có thể lan rộng ra hay thu hẹp rất dễ ràng .

  • Việc chèn hay xóa một thành phần trong danh sách liên kết là rất thuận tiện, ta chỉ cần đổi khác vị trí trỏ của những con trỏ thay vì phải dịch hàng loạt phần tài liệu còn lại. Xem ví dụ sau khi ta muốn chèn node C vào giữa node A và B :

Xem thêm  Cách xóa, gỡ ứng dụng trên iPhone 6, iPhone 6s đơn giản, nhanh chóng - https://bem2.vn

Trước khi chèn :

Sau khi chèn :

Điểm yếu :

  • Danh sách liên kết mang yếu điểm của cấp phát động về hiệu năng. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm tốt hơn ( là những khối những ô nhớ liên tục ) so với danh sách liên kết .

  • Ta không hề truy vấn ngẫu nhiên một thành phần trong danh sách liên kết ngay lập tức, mà phải triển khai duyệt từ đầu danh sách cho tới khi gặp thành phần đó. Do vậy ta không hề triển khai tìm kiếm nhị phân với những danh sách liên kết .

  • Cần thêm khoảng trống bộ nhớ cho con trỏ trong mỗi thành phần của danh sách liên kết .

Xây dựng danh sách liên kết đơn với C / C + +

Để thiết kế xây dựng một danh sách sách liên kết trước hết ta cần biết được danh sách liên kết cần gồm có những thành phần nào và những thao tác mà ta hoàn toàn có thể triển khai với danh sách liên kết :
Các thành phần của danh sách liên kết đơn gồm có :

  • Các node : Mỗi node gồm có hai thành phần : phần tài liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node tiếp theo, nói cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node sau cuối của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả .

    struct node {
        int data; /* Phần dữ liệu của một node*/
        struct node* next; /* Con trỏ tới node kế tiếp */
    };
  • Con trỏ head để trỏ tới vị trí tiên phong của danh sách liên kết .

    struct node * head; /* Con trỏ tới head node */

Các thao tác chính với danh sách liên kết đơn:

  • Tạo một node mới và trả về con trỏ tới node đó .

    /* Tạo một node mới và trả về con trỏ tới node đó. */
    struct node* NewNode(int x) {
              struct node* new_node
                       = (struct node*)malloc(sizeof(struct node)); /* Cấp phát bộ nhớ cho node */
              new_node->data = x;
              new_node->next = NULL;
              return new_node;
    }
  • Chèn một thành phần vào danh sách .
    /* Chèn node vào vị trí cuối của danh sách liên kết */
    void InsertAtTail(int x) {
              struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp  làm thay đổi vị trí trỏ của con trỏ head */
              struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần dữ liệu là tham số được truyền vào */
              if(head == NULL) { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */
                       head = new_node;
                       return;
              }
              while(temp->next != NULL) temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */
              temp->next = new_node; /* Chèn node mới vào cuối danh sách */
    }
  • Xóa một thành phần khỏi danh sách .
    struct node* Delete(struct node *head, int position)
    
    {
        struct node *prev = NULL; /* Con trỏ lưu node ngay trước node cần xóa */
        struct node *ptr = head; /* Tạo ra bản sao của con trỏ head, tránh làm thay đổi vị trí trỏ của con trỏ head khi duyệt danh sách*/
    
        int pos = 0; /* Biến lưu vị trí các phần tử trong danh sách */
        if(position==0) /* Trường hợp xóa phần tử ở đầu danh sách */
        {
            head=head->next; /* Trả về vị trí của phần tử tiếp theo, vị trí trỏ của head thay đổi */
            free(ptr); /* Thu hồi bộ nhớ của phần tử cần được xóa */
        }
        else
        {
            while(position!=pos) /*Duyệt danh sách, lặp cho tới khi tìm thấy vị trí cần xóa */
            {
                ++pos;
                prev=ptr;
                ptr=ptr->next;
            }
            /* Sau vòng lặp tìm được node cần xóa là ptr, địa chỉ node ngay trước node cần xóa được lưu trữ trong prev */
            if(ptr!=NULL) /* Nếu tìm tháy node cần xóa trong danh sách, thực hiện xóa */
    
            {
                prev->next=ptr->next;
                free(ptr);
            }
        }
        return head;
    }
  • Hiển thị toàn bộ những node trong danh sách .
    void Display() {
              struct node* temp = head;
              while(temp != NULL) {
                       printf("%d ",temp->data);
                       temp = temp->next;
              }
              printf("\n");
    }

Ứng dụng của danh sách liên kết đơn trong thực tế:

Xem thêm  ‎SnapCalc - Máy Tính Giải Toán

Danh sách liên kết đơn đa phần được dùng để thiết kế xây dựng những loại cấu trúc tài liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị …
Đôi khi ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả những node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau .

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

Cấu trúc trên chính là cấu trúc của danh sách liên kết kép .
Để hiểu hơn về danh sách liên kết kép mời bạn đọc bài tiếp theo .
Bạn cũng hoàn toàn có thể đọc thêm những bài toán về danh sách liên kết đơn tại những đường dẫn sau :

  1. In danh sách theo vị trí đảo ngược

    .

  2. Phát hiện điểm nối của danh sách liên kết

    .

  3. Xóa những node trùng lặp trong danh sách

    .

  4. So sánh hai danh sách liên kết.

  5. Kết hợp hai danh sách đã được sắp xếp

    .

Source: https://bem2.vn
Category: Ứng dụng hay

Rate this post

Bài viết liên quan

Để lại ý kiến của bạn:

Email của bạn sẽ không được hiển thị công khai.