Danh sách liên kết đơn trong cấu trúc dữ liệu
Sarah Chen
Danh sách liên kết đơn là gì?
Danh sách liên kết đơn là cấu trúc dữ liệu tuyến tính và đơn hướng, trong đó dữ liệu được lưu trên các nút và mỗi nút được kết nối thông qua một liên kết đến nút tiếp theo. Mỗi nút chứa một trường dữ liệu và một liên kết đến nút tiếp theo. 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 đôi có thể được duyệt theo cả hai hướng.
Đây là cấu trúc nút của Danh sách liên kết đơn:
Tại sao sử dụng danh sách liên kết trên mảng?
Có một số trường hợp sử dụng Danh sách liên kết sẽ tốt hơn là sử dụng Mảng. Dưới đây là một số tình huống:
- Số phần tử không xác định: Khi bạn không biết mình cần lưu trữ bao nhiêu phần tử trong thời gian chạy chương trình, bạn có thể sử dụng Danh sách liên kết. Bộ nhớ được phân bổ động khi bạn thêm các phần tử vào danh sách liên kết.
- Truy cập ngẫu nhiên: Trong trường hợp bạn không cần sử dụng quyền truy cập ngẫu nhiên từ các phần tử, bạn có thể sử dụng Danh sách liên kết.
- Chèn vào giữa: Chèn vào giữa một mảng là một nhiệm vụ phức tạp. Bởi vì bạn cần đẩy các phần tử khác sang bên phải. Tuy nhiên, một danh sách được liên kết cho phép bạn thêm một phần tử vào bất kỳ vị trí nào bạn muốn.
Operacác chức năng của danh sách liên kết đơn
Danh sách liên kết đơn tốt cho việc phân bổ bộ nhớ động. Nó cung cấp tất cả các hoạt động cơ bả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 liên kết, duyệt, v.v.
Ở đây chúng ta sẽ thảo luận về hoạt động sau của danh sách liên kết:
- 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à ví dụ về danh sách liên kết có bốn nút.
Chèn vào đầu danh sách liên kết đơn
Đây là một hoạt động đơn giản. Nói chung, nó được gọi là đẩy một danh sách liên kết đơn. Bạn cần tạo một nút mới và đặt nút này ở đầu danh sách liên kết.
Để thực hiện thao tác này, chúng ta cần tuân theo hai điều kiện quan trọng. Họ là
- Nếu danh sách trống thì nút mới tạo sẽ là nút đầu và nút tiếp theo của đầu sẽ là ”NULL”.
- Nếu danh sách không trống, nút mới sẽ là nút đầu và nút tiếp theo sẽ trỏ đến nút đầu trước đó.
Đây là mã giả để chèn một nút vào đầu danh sách được 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 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 có một số điểm tương đồng với việc chèn vào phần đầu. Tất cả những gì bạn cần làm là duyệt đến nút cuối hoặc nút đuôi. Sau đó trỏ nút “tiếp theo” của nút cuối vào nút mới được tạo. Nếu nút đầu là null thì nút mới sẽ là nút đầu.
Đây là các bước:
Bước 1) Di chuyển cho đến khi nút “tiếp theo” 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.
Mã giả để chèn một nút vào cuối danh sách đơn lẻ:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
Chèn sau một nút trong Danh sách liên kết đơn
Chèn sau nút có hai phần: Tìm kiếm nút và đính kèm sau nút được tìm kiếm. Chúng ta cần duyệt qua tất cả các nút. Đối với mỗi nút, chúng ta cần khớp với phần tử tìm kiếm. Nếu trùng khớp thì chúng tôi sẽ thêm nút mới sau nút được tìm kiếm.
Đây là các bước:
Bước 1) Duyệt qua nút tiếp theo cho đến khi giá trị của nút hiện tại bằng mục tìm kiếm.
Bước 2) Con trỏ tiếp theo của nút mới sẽ là con trỏ tiếp theo của nút hiện tại.
Bước 3) Nút tiếp theo của nút hiện tại sẽ là nút mới.
Đây là mã giả để chèn một nút sau một nút:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Chèn trước một nút trong Danh sách liên kết đơn
Chức năng này rất giống với việc chèn sau một nút. Chúng ta phải tạo một nút mới và duyệt qua danh sách liên kết cho đến khi nút hiện tại khớp với nút tìm kiếm. Sau đó, chúng ta sẽ thêm nút mới làm nút trước của nút hiện tại.
Đây là các bước:
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à gán nút “tiếp theo” của nút đó với nút tiếp theo của nút hiện tại.
Bước 3) Gán nút mới làm nút tiếp theo của nút hiện tại.
Đây là mã giả:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Xóa phần đầu danh sách liên kết đơn
Trong mọi hàm của danh sách liên kết, con trỏ đầu được cung cấp dưới dạng tham số. Bạn cần xóa nút đầu và biến nút tiếp theo của nút đầu thành nút đầu mới của danh sách liên kết. Chúng ta cũng cần giải phóng bộ nhớ của nút đã xóa. Nếu không, bộ nhớ sẽ được đánh dấu là đã chiếm dụng khi một chương trình khác cố gắng truy cập vào nó.
Dưới đây là các bước để xóa phần đầu của danh sách liên kết đơn:
Bước 1) Gán nút tiếp theo của nút đầu làm nút đầu mới.
Bước 2) Giải phóng bộ nhớ được phân bổ bởi nút đầu trước đó.
Bước 3) Trả lại nút đầu mới.
Mã giả để xóa nút đầu:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Xóa phần đuôi của danh sách liên kết đơn
Xóa nút đuôi quen thuộc hơn với việc xóa nút đầu. Sự khác biệt là chúng ta cần duyệt đến cuối danh sách liên kết và xóa nó. Trong danh sách liên kết đơn, nút có nút tiếp theo là “NULL” là nút đuôi.
Dưới đây là các bước để xóa nút đuôi của danh sách liên kết:
Bước 1) Đi qua trước nút đuô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 của nút hiện tại.
Bước 3) Đặt nút tiếp theo của nút hiện tại là NULL.
Đây là mã giả để xóa nút đuôi:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
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 có hai nhiệm vụ, tìm kiếm và xóa. Chúng ta cần tìm kiếm cho đến hết danh sách liên kết đơn. Nếu chúng tôi tìm thấy bất kỳ nút nào tương tự, chúng tôi sẽ xóa nút đó. Sau đó, chúng ta cần hợp nhất hoặc liên kết các nút bên trái và bên phải của nút đã xóa. Dưới đây là các bước để thực hiện việc này:
Bước 1) Duyệt cho đến hết danh sách liên kết. Kiểm tra xem nút hiện tại có bằng nút tìm kiếm hay không.
Bước 2) Nếu bất kỳ nút nào khớp, hãy lưu con trỏ nút vào nút hiện tại.
Bước 3) Nút tiếp theo của nút trước sẽ là nút tiếp theo của nút hiện tại.
Bước 4) Xóa và giải phóng bộ nhớ của nút hiện tại.
Mã giả để tìm kiếm và xóa một nút khỏi danh sách liên kết đơn:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
Duyệt qua danh sách liên kết đơn
Danh sách liên kết đơn chỉ có chức năng duyệt từ đầu đến cuối. Không có điểm con trỏ tới nút trước đó; đó là lý do tại sao chúng ta không thể duyệt qua Danh sách liên kết đơn theo thứ tự ngược lại. Chúng tôi sẽ duyệt qua từng nút và in giá trị của nút hiện tại cho đến khi nhận được giá trị rỗng.
Đây là các bước:
Bước 1) Duyệt qua từng nút cho đến khi chúng ta nhận được nút rỗng là nút tiếp theo.
Bước 2) In giá trị của nút hiện tại.
Mã giả để duyệt danh sách liên kết đơn:
function traverse( head ): while head.next is not NULL: print the value of the head 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);
}
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 = new Node();
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);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
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 = new 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 chương trình
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.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
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):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
def insertAfter(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} after node\t{searchItem}')
return
def insertbefore(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} before node\t{searchItem}')
return
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 về thời gian và độ phức tạp về không gian. Độ phức tạp về thời gian 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 cho trường hợp tốt nhất:
- Việc chèn vào phần đầu có thể được thực hiện trong O(1). Vì chúng ta không cần duyệt qua bên trong danh sách liên kết.
- Hoạt động tìm kiếm và xóa có thể được thực hiện trong O(1) nếu phần tử tìm kiếm có trong nút đầu.
Độ phức tạp thời gian cho trường hợp trung bình:
- Việc chèn vào bên trong danh sách liên kết sẽ lấy O(n) nếu các phần tử “n” có trong Danh sách liên kết đơn.
- Tìm kiếm và xóa cũng có thể mất O(n), vì phần tử tìm kiếm có thể xuất hiện ở nút đuôi. Trong trường hợp đó, bạn nên duyệt qua toàn bộ danh sách.
Độ 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 phân bổ bộ nhớ động. Nếu chúng ta muốn lưu trữ n phần tử, nó sẽ phân bổ n đơn vị bộ nhớ. Vì vậy, độ phức tạp không gian là O(n).
