Danh sách liên kết đơn trong cấu trúc dữ liệu
Sarah Chen
⚡ Tóm tắt thông minh
Danh sách liên kết đơn là một cấu trúc dữ liệu tuyến tính, một chiều, trong đó mỗi nút lưu trữ dữ liệu và một con trỏ duy nhất đến nút tiếp theo, do đó việc duyệt chỉ diễn ra từ đầu đến cuối và bộ nhớ được cấp phát động khi các nút mới được thêm vào.
Danh sách liên kết đơn là gì?
Danh sách liên kết đơn là một cấu trúc dữ liệu tuyến tính và một chiều, trong đó dữ liệu được lưu trữ trên các nút, và mỗi nút được kết nối với nút kế tiếp thông qua một liên kết. Mỗi nút chứa một trường dữ liệu và một liên kết đến nút kế tiếp. Danh sách liên kết đơn chỉ có thể được duyệt theo một hướng, trong khi danh sách liên kết đơn có thể được duyệt theo nhiều hướng khác nhau. Danh sách được liên kết gấp đôi Có thể đi lại theo cả hai hướng.
Đây là cấu trúc nút của một danh sách liên kết đơn:
Cấu trúc của một nút trong danh sách liên kết
Tại sao nên sử dụng danh sách liên kết thay vì mảng?
Một số trường hợp ưu tiên sử dụng danh sách liên kết hơn là một danh sách liên kết thông thường. Mảng:
- Số phần tử không xác định: Khi số lượng phần tử cần thiết không được biết trước tại thời điểm biên dịch, danh sách liên kết sẽ cấp phát bộ nhớ một cách động khi các phần tử được thêm vào.
- Truy cập ngẫu nhiên: Khi không cần truy cập chỉ mục ngẫu nhiên, danh sách liên kết là một lựa chọn phù hợp.
- Chèn vào giữa: Chèn phần tử vào giữa mảng đòi hỏi phải dịch chuyển các phần tử. Danh sách liên kết cho phép chèn vào bất kỳ vị trí nào chỉ bằng cách thay đổi một vài con trỏ.
Operacác chức năng của danh sách liên kết đơn
Danh sách liên kết đơn rất tốt cho việc cấp phát bộ nhớ động. Nó hỗ trợ các thao tác chuẩn của danh sách liên kết, tức là chèn, xóa, tìm kiếm, cập nhật, hợp nhất hai danh sách và duyệt.
Bài viết này thảo luận về các thao tác sau:
- Chèn vào đầu
- Chèn ở đuôi
- Chèn sau một nút
- Chèn trước một nút
- Xóa nút đầu
- Xóa nút đuôi
- Tìm kiếm và xóa một nút
- Duyệt qua danh sách liên kết
Đây là một ví dụ về danh sách liên kết có bốn nút.
Ví dụ về danh sách liên kết đơn
Chèn phần tử vào đầu danh sách liên kết đơn
Đây là một thao tác đơn giản. Nó thường được biết đến như là thêm phần tử vào danh sách liên kết đơn. Một nút mới được tạo ra và đặt ở đầu danh sách.
Để thực hiện thao tác này, cần tuân thủ hai điều kiện quan trọng:
- Nếu danh sách trống, nút mới được tạo sẽ trở thành nút đầu và nó sẽ... tiếp theo Con trỏ là NULL.
- Nếu danh sách không rỗng, nút mới sẽ trở thành nút đầu và nó sẽ... tiếp theo Con trỏ trỏ đến nút đầu trước đó.
Đây là đoạn mã giả để chèn một nút vào đầu danh sách liên kết:
function insertAtHead(head, value): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Chèn vào đầu
Chèn phần tử vào cuối danh sách liên kết đơn
Việc chèn một nút vào cuối danh sách liên kết tương tự như chèn vào đầu. Duyệt đến nút cuối, sau đó trỏ đến nó. tiếp theo Con trỏ trỏ đến nút mới. Nếu đầu nút là NULL, nút mới sẽ trở thành đầu nút.
Bước 1) Đi tiếp cho đến khi tiếp theo Con trỏ của nút hiện tại trở thành NULL.
Bước 2) Tạo một nút mới với giá trị được chỉ định.
Bước 3) Gán nút mới làm nút tiếp theo của nút đuôi.
Đoạn mã giả để chèn vào cuối một danh sách đơn:
function insertAtEnd(head, value): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: head = head.next head.next = newNode newNode.next = NULL
Chèn ở đuôi
Chèn phần tử sau một nút trong danh sách liên kết đơn
Việc chèn thêm một nút sau một phần tử khác gồm hai bước: tìm kiếm nút đích và thêm nút mới vào sau nó. Duyệt qua danh sách cho đến khi tìm thấy nút phù hợp, sau đó chèn nút mới vào.
Bước 1) Duyệt tiếp cho đến khi giá trị của nút hiện tại bằng với giá trị cần tìm.
Bước 2) Đặt nút mới tiếp theo con trỏ đến nút hiện tại tiếp theo con trỏ.
Bước 3) Trỏ nút hiện tại tiếp theo Con trỏ trỏ đến nút mới.
Mã giả:
function insertAfter(head, value, searchItem): newNode = Node(value) while head.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
Chèn một nút sau một nút trong Danh sách liên kết đơn
Chèn một phần tử trước một nút trong danh sách liên kết đơn.
Thao tác này tương tự như việc chèn sau một nút. Duyệt cho đến khi nút tiếp theo khớp với giá trị tìm kiếm, sau đó chèn nút mới vào trước nút đó.
Bước 1) Di chuyển cho đến khi giá trị của nút tiếp theo bằng mục tìm kiếm.
Bước 2) Tạo một nút mới và thiết lập thuộc tính cho nó. tiếp theo con trỏ đến nút hiện tại tiếp theo.
Bước 3) Trỏ nút hiện tại tiếp theo đến nút mới.
function insertBefore(head, value, searchItem): newNode = Node(value) while head.next.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
Chèn một nút vào trước một nút trong Danh sách liên kết đơn
Xóa phần tử đầu của danh sách liên kết đơn
Con trỏ đầu được cung cấp dưới dạng tham số. Nút đầu bị xóa và nút tiếp theo trở thành nút đầu mới. Vùng nhớ của nút bị xóa phải được giải phóng để tránh rò rỉ bộ nhớ.
Bước 1) Chỉ định nút tiếp theo của đầu làm đầu mới.
Bước 2) Giải phóng bộ nhớ đã cấp phát của nút đầu trước đó.
Bước 3) Trả lại nút đầu mới.
function deleteHead(head): temp = head head = head.next free(temp) return head
Xóa phần đầu của danh sách liên kết
Xóa phần đuôi của danh sách liên kết đơn
Việc xóa nút cuối danh sách tương tự như xóa nút đầu danh sách. Điểm khác biệt là cần phải duyệt đến cuối danh sách. Trong danh sách liên kết đơn, nút có tiếp theo Con trỏ là NULL, đó là nút cuối cùng.
Bước 1) Duyệt đến ngay trước nút cuối. Lưu nút hiện tại.
Bước 2) Giải phóng bộ nhớ của nút tiếp theo (phần đuôi).
Bước 3) Đặt nút tiếp theo của nút hiện tại thành NULL.
function deleteTail(head): while head.next.next is not NULL: head = head.next free(head.next) head.next = NULL
Xóa phần đuôi của Danh sách liên kết đơn
Tìm kiếm và xóa một nút khỏi danh sách liên kết đơn.
Chức năng này thực hiện hai nhiệm vụ: tìm kiếm và xóa. Duyệt đến cuối danh sách. Nếu tìm thấy một nút phù hợp, hãy xóa nút đó và liên kết lại nút trước đó. tiếp theo con trỏ.
Bước 1) Duyệt đến hết danh sách. Kiểm tra xem nút hiện tại có bằng nút cần tìm hay không.
Bước 2) Nếu tìm thấy kết quả phù hợp, hãy lưu trữ con trỏ đến nút hiện tại.
Bước 3) tiếp theo Nút trước đó trở thành nút tiếp theo của nút hiện tại.
Bước 4) Xóa nút hiện tại và giải phóng bộ nhớ của nó.
function searchAndDelete(head, searchItem): while head.next.next is not NULL and head.next.value != searchItem: head = head.next temp = head.next head.next = head.next.next free(temp)
Tìm kiếm và xóa một nút khỏi Danh sách liên kết đơn
Duyệt qua danh sách liên kết đơn
Danh sách liên kết đơn chỉ hỗ trợ duyệt từ đầu đến cuối. Không có con trỏ đến nút trước đó, vì vậy không thể duyệt ngược. Mỗi nút được duyệt lần lượt, in giá trị của nó cho đến khi gặp NULL.
Bước 1) Duyệt qua từng nút cho đến khi gặp NULL.
Bước 2) In giá trị của nút hiện tại.
function traverse(head): while head is not NULL: print head.value head = head.next
Ví dụ về danh sách liên kết đơn trong C++
#include<iostream> using namespace std; struct Node{ int data; struct Node *next; }; void insertAtHead(Node* &head, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; if(head != NULL){ newNode->next = head; } head = newNode; cout<<"Added "<<newNode->data<<" at the front"<<endl; } void insertEnd(Node* &head, int value){ if(head == NULL){ insertAtHead(head, value); return; } Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = newNode; cout<<"Added "<<newNode->data<<" at the end"<<endl; } void searchAndDelete(Node **headPtr, int searchItem){ Node *temp = NULL; if((*headPtr)->data == searchItem){ temp = *headPtr; *headPtr = (*headPtr)->next; free(temp); } else { Node *currentNode = *headPtr; while(currentNode->next != NULL){ if(currentNode->next->data == searchItem){ temp = currentNode->next; currentNode->next = currentNode->next->next; free(temp); break; } else { currentNode = currentNode->next; } } } cout<<"Deleted Node\t"<<searchItem<<endl; } void insertAfter(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl; } void insertBefore(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->next->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl; } void traverse(Node *headPointer){ Node* tempNode = headPointer; cout<<"Traversal from head:\t"; while(tempNode != NULL){ cout<<tempNode->data; if(tempNode->next) cout<<" --> "; tempNode = tempNode->next; } cout<<endl; } int main(){ Node *head = NULL; insertAtHead(head, 5); insertAtHead(head, 6); insertAtHead(head, 7); insertEnd(head, 9); traverse(head); searchAndDelete(&head, 6); traverse(head); insertAfter(head, 7, 10); insertBefore(head, 9, 11); traverse(head); }
Đầu ra
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 --> 6 --> 5 --> 9 Deleted Node 6 Traversal from head: 7 --> 5 --> 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 --> 10 --> 5 --> 11 --> 9
Ví dụ về danh sách liên kết đơn trong Python
class Node: def __init__(self, data=None, next=None): self.data = data self.next = next class SinglyLinkedList: def __init__(self): self.head = None def insertAtHead(self, value): newNode = Node(data=value) if self.head is not None: newNode.next = self.head self.head = newNode print(f'Added {newNode.data} at the front.') def insertAtEnd(self, value): if self.head is None: self.insertAtHead(value) return newNode = Node(value) temp = self.head while temp.next is not None: temp = temp.next temp.next = newNode print(f'Added {newNode.data} at the end.') def searchAndDelete(self, searchItem): if self.head is None: return if self.head.data == searchItem: self.head = self.head.next print(f'Deleted node\t{searchItem}') return currentNode = self.head while currentNode.next is not None: if currentNode.next.data == searchItem: currentNode.next = currentNode.next.next print(f'Deleted node\t{searchItem}') return currentNode = currentNode.next def insertAfter(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} after node\t{searchItem}') def insertBefore(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.next.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} before node\t{searchItem}') def traverse(self): temp = self.head print("Traversing from head:\t", end="") while temp: print("{}\t".format(temp.data), end="") temp = temp.next print() singlyLinkedList = SinglyLinkedList() singlyLinkedList.insertAtHead(5) singlyLinkedList.insertAtHead(6) singlyLinkedList.insertAtHead(7) singlyLinkedList.insertAtEnd(9) singlyLinkedList.traverse() singlyLinkedList.searchAndDelete(6) singlyLinkedList.traverse() singlyLinkedList.insertAfter(7, 10) singlyLinkedList.insertBefore(9, 11) singlyLinkedList.traverse()
Đầu ra
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
Độ phức tạp của danh sách liên kết đơn
Có hai loại độ phức tạp: độ phức tạp thời gian và độ phức tạp không gian. Độ phức tạp thời gian trong trường hợp xấu nhất và trung bình là như nhau đối với danh sách liên kết đơn.
Độ phức tạp thời gian trong trường hợp tốt nhất:
- Việc chèn vào đầu có thể được thực hiện trong O(1). Không cần duyệt bên trong danh sách.
- Tìm kiếm và xóa có thể được thực hiện trong O(1) nếu phần tử mục tiêu nằm ở nút đầu.
Độ phức tạp thời gian trung bình:
- Việc chèn vào bên trong danh sách liên kết mất thời gian O(n), trong đó n là tổng số phần tử.
- Việc tìm kiếm và xóa cũng có thể mất O(n) vì phần tử mục tiêu có thể nằm ở bất kỳ đâu cho đến nút cuối cùng.
Độ phức tạp không gian của danh sách liên kết đơn
Danh sách liên kết đơn (Singly Linked List) cấp phát bộ nhớ động. Để lưu trữ n các phần tử, nó phân bổ n đơn vị bộ nhớ. Vì vậy, độ phức tạp không gian là O(n).
Ứng dụng của danh sách liên kết đơn
Danh sách liên kết đơn xuất hiện ở nhiều nơi mà việc duyệt chỉ theo chiều tiến và bộ nhớ động rất hữu ích:
- Ngăn xếp và hàng đợi: Hệ thống lưu trữ cơ bản cho các ngăn xếp LIFO và hàng đợi FIFO được xây dựng từ các nút.
- Chuỗi bảng băm: Các xung đột được giải quyết bằng cách liên kết các mục thành một danh sách liên kết đơn cho mỗi nhóm.
- Danh sách kề: Đồ thị thưa sử dụng một danh sách liên kết đơn (Singly Linked List) chứa các đỉnh lân cận cho mỗi đỉnh.
- Bảng ký hiệu: Trình biên dịch và trình thông dịch xâu chuỗi các định danh thành một danh sách liên kết đơn cho mỗi phạm vi.
- Bộ cấp phát bộ nhớ: Bộ phân bổ danh sách miễn phí track khối trống dưới dạng danh sách liên kết đơn.
