Wikipedia

Danh sách liên kết

Trong khoa học máy tính, danh sách liên kết (tiếng Anh: linked list) là tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý nào của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử sẽ trỏ đến phần tử tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện cho một dãy. Ở dạng cơ bản nhất, mỗi nút chứa: dữ liệu và một tham chiếu (hay nói cách khác là một liên kết) đến nút tiếp theo trong chuỗi.[1] Cấu trúc này cho phép chèn hay loại bỏ phần tử khỏi bất kì vị trí nào trong trong chuỗi một cách hiệu quả trong quá trình lặp. Các biến thể phức tạp hơn như thêm các liên kết bổ sung, cho phép chèn hay loại bỏ các nút hiệu quả hơn tại vị trí bất kì. Một nhược điểm của danh sách liên kết là thời gian truy cập là tuyến tính (và khó thực thi ống dẫn). Truy cập nhanh hơn, ví dụ như truy cập ngẫu nhiên, là không khả thi. Mảng có vùng đệm (cache locality) tốt hơn so với danh sách liên kết.[2]

Danh sách liên kết là một chuỗi các nút chứa hai trường: giá trị số nguyên và liên kết đến nút tiếp theo. Nút cuối cùng được liên kết với một dấu chấm cuối được sử dụng để biểu thị sự kết thúc của danh sách.

Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất. Nó có thể được dùng để hiện thực một số kiểu dữ liệu trừu tượng phổ biến khác, bao gồm danh sách (list), ngăn xếp (stack), hàng đợi, mảng kết hợp, và S-expression, mặc dù không có gì lạ khi hiện thực các cấu trúc dữ liệu đó mà không dựa trên nền tảng của danh sách liên kết.[3]

Lợi ích chính của danh sách liên kết so với mảng thông thường là các phần tử danh sách có thể được chèn hay xóa một cách dễ dàng mà không cần phân bổ lại hoặc sắp xếp lại toàn bộ cấu trúc vì các mục dữ liệu không cần được lưu trữ liên tục trong bộ nhớ hay trên đĩa, trong khi tái cấu trúc một mảng tại thời gian chạy là một hoạt động tốn kém hơn nhiều. Danh sách liên kết cho phép chèn hay xóa nút tại bất kì điểm nào trong danh sách.[3]

Lịch sử sửa

Khái niệm và thuật ngữ sửa

Mỗi một bản ghi của danh sách liên kết thường được gọi là "nút" hoặc là "phần tử". Trường của nút chứa địa chỉ thường được gọi là "liên kết tiếp theo" hoặc "con trỏ tiếp theo". Trường còn lại được gọi là "dữ liệu", "thông tin" hay "giá trị".

Trong lập trình, các lập trình viên thường sử dụng từ khóa "head" như nút đầu tiên và "tail" như nút cuối cùng.

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

Danh sách liên kết đơn là một danh sách liên kết đơn giản nhất khi bao gồm hai trường là "giá trị" và trường "liên kết tiếp theo". Các thao tác có thể thực hiện trên danh sách liên kết đơn như chèn, xóa và duyệt.

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

Một hàm thêm nút cơ bản trong C++: 

node addNode(node head, int value) {
    node temp, p; // Tạo hai nút là temp và p
    temp = createNode(); // Giả sử hàm createNode tạo một nút có giá trị bằng 0 và trỏ nút tiếp theo là NULL rồi gán cho nút temp
    temp->value = value; // Gán giá trị value vào trường dữ liệu nút temp
    if (head == NULL) {
        head = temp;     // Liên kết đơn rỗng thì gán head bằng temp
    }
    else {
        p = head; // Gán giá trị head cho p
        while (p->next != NULL) {
            p = p->next; // Chạy qua danh sách bằng hàm while-do cho đến khi cho trỏ tiếp theo là NULL thì dừng lại. Con trỏ cuối cùng sẽ là con trỏ NULL
        }
        p->next = temp; // Gán con trỏ cuối cùng bằng con trỏ mới tạo
    }
    return head;
 }

Danh sách liên kết đôi sửa

Tương tự như danh sách liên kết đơn, danh sách liên kết đôi cũng có hai trường "giá trị" và "liên kết tiếp theo". Tuy nhiên, danh sách liên kết đôi sẽ bao gồm thêm một con trỏ chính là "liên kết trước đó", để trỏ về nút trước đó của nút hiện tại.

 
Danh sách liên kết đôi

Cơ bản của node trong ngôn ngữ C++: 

struct Node{
    int data; // Cho giá trị có kiểu số nguyên
    Node *next; // Địa chỉ của con trỏ tiếp theo 
    Node *prev; // Địa chỉ của con trỏ trước đó 
};
typedef struct Node NODE;

Danh sách liên kết nhân sửa

Trong danh sách liên kết nhân, mỗi nút sẽ chứa từ hai hoặc nhiều trường liên kết, mỗi trường sẽ được sử dụng để nối với một tập hợp các dữ liệu nhất định cùng tập hợp (ví dụ: tên, phòng ban, ngày sinh,...). Danh sách liên kết đôi cũng có thể xem là trường hợp đặc biệt của danh sách liên kết nhân.

Danh sách liên kết vòng sửa

Trong danh sách liên kết đơn, nút cuối cùng sẽ trỏ đến tham chiếu rỗng, tuy nhiên ở danh sách liên kết vòng, nút cuối cùng sẽ trỏ đến nút đầu tiên của danh sách liên kết.

 
Danh sách liên kết vòng

Tham khảo sửa

  1. ^ “Linked List Data Structure”. GeeksforGeeks (bằng tiếng Anh). Truy cập ngày 12 tháng 11 năm 2022.
  2. ^ “Linked List Data Structure”. www.programiz.com. Truy cập ngày 12 tháng 11 năm 2022.
  3. ^ a b “Linked list”, Wikipedia (bằng tiếng Anh), 12 tháng 11 năm 2022, truy cập ngày 12 tháng 11 năm 2022

Tài liệu tham khảo sửa

Liên kết ngoài sửa

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Danh_sách_liên_kết&oldid=69313215”