Danh sách liên kết đôi: C++, Python (Ví dụ về mã)
Sarah Chen
Danh sách liên kết đôi là gì?
Trong danh sách liên kết đôi, mỗi nút có liên kết đến cả nút trước và nút tiếp theo. Mỗi nút bao gồm ba phần tử: một phần tử chứa dữ liệu và hai phần tử còn lại là con trỏ của nút tiếp theo và trước đó. Hai con trỏ này giúp chúng ta tiến hoặc lùi từ một nút cụ thể.
Đây là cấu trúc cơ bản của danh sách liên kết đôi.
Mỗi danh sách liên kết đều có nút đầu và nút đuôi. Nút Đầu không có nút “trước” (con trỏ trước) và nút đuôi không có nút “tiếp theo”.
Dưới đây là một số thuật ngữ quan trọng đối với danh sách liên kết đôi:
- Prev: Mỗi nút được liên kết với nút trước đó của nó. Nó được sử dụng như một con trỏ hoặc liên kết.
- Tiếp theo: Mỗi nút được liên kết với nút tiếp theo của nó. Nó được sử dụng như một con trỏ hoặc liên kết.
- ngày: Điều này được sử dụng để lưu trữ dữ liệu trong một nút. “Dữ liệu” có thể chứa thông tin khác Cấu trúc dữ liệu bên trong nó. Ví dụ: chuỗi, từ điển, bộ, hashmap, v.v. có thể được lưu trữ trong “Dữ liệu”.
Đây là cấu trúc cơ bản của một nút trong danh sách liên kết đôi:
Operacác chức năng của danh sách liên kết đôi
Các hoạt động của danh sách liên kết đôi bao gồm thêm và xóa các nút, chèn và xóa các nút và duyệt danh sách liên kết từ trên xuống dưới.
Đây là danh sách các thao tác chúng ta có thể thực hiện bằng danh sách liên kết đôi:
- Chèn ở phía trước
- Chèn vào đuôi hoặc nút cuối cùng
- Chèn sau một nút
- Chèn trước một nút
- Xóa từ phía trước
- Xóa từ đuôi
- Tìm kiếm và xóa một nút
- Đi ngang từ đầu đến đuôi
- Xoay đuôi tới đầu
Chúng ta sẽ thấy cách triển khai và mã giả cho tất cả các hoạt động ở trên.
Chèn vào trước danh sách liên kết đôi
Chèn vào phía trước nghĩa là chúng ta cần tạo một nút trong danh sách liên kết và đặt nó vào đầu danh sách liên kết.
Ví dụ: có một nút nhất định “15”. Chúng ta cần thêm phần này vào nút đầu.
Đây là hai điều kiện quan trọng khi thực hiện thao tác này:
- Nút mới sẽ là nút đầu nếu không có nút nào trong Danh sách liên kết đôi.
- Nếu đã có nút đầu thì nút đầu trước sẽ được thay thế bằng nút mới.
Đây là mã giả cho thao tác này:
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
Chèn vào cuối danh sách liên kết đôi
“Insertion at the end” nghĩa là chúng ta sẽ tạo một node trong danh sách liên kết và đặt nó ở cuối.
Để thực hiện điều này, chúng ta có thể sử dụng hai phương pháp:
- Phương pháp 1: Bắt đầu duyệt từ phần đầu của Danh sách liên kết đôi cho đến khi phần “tiếp theo” trở thành rỗng. Sau đó liên kết nút mới với nút “tiếp theo”.
- Phương pháp 2: Lấy nút cuối cùng của Danh sách liên kết đôi. Sau đó, nút “tiếp theo” của nút cuối cùng sẽ liên kết với nút mới. Bây giờ, nút mới sẽ là nút đuôi.
Đây là mã giả để chèn vào nút đuôi:
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
Chèn sau một nút
Giả sử chúng ta có một danh sách liên kết kép hiện có như sau:
Chúng tôi muốn chèn một nút nhất định sẽ được liên kết sau nút có giá trị “12”.
Đây là các bước cho việc này:
Bước 1) Đi từ đầu đến nút cuối cùng. Kiểm tra nút nào có giá trị là “12”.
Bước 2) Tạo một nút mới và gán nó làm con trỏ tiếp theo của nút “12”. Nút “tiếp theo” của nút mới sẽ là 15.
Đây là mã giả để chèn một nút sau một nút trong danh sách liên kết đôi:
function insertAfter(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.value is not equal searchItem then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Chèn trước một nút
Thao tác này tương tự như thao tác “chèn sau một nút”. Chúng ta cần tìm kiếm giá trị của một nút cụ thể để thực hiện việc này. Sau đó chúng ta sẽ tạo một nút mới và chèn nó vào trước nút được tìm kiếm.
Giả sử chúng ta muốn chèn một nút đã cho “15” trước nút “12”. Sau đây là các bước để thực hiện:
Bước 1) Duyệt danh sách liên kết từ nút đầu đến nút đuôi.
Bước 2) Kiểm tra xem con trỏ tiếp theo của nút hiện tại có giá trị “12” hay không.
Bước 3) Chèn nút mới làm nút “tiếp theo” của nút hiện tại.
Đây là mã giả để chèn một nút trước một nút trong Danh sách liên kết kép:
function insertBefore(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.next.value is not equal searchItem then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Xóa phần đầu danh sách liên kết đôi
Nút đầu trong danh sách liên kết đôi không có nút nào trước đó. Vì vậy, con trỏ tiếp theo sẽ là nút đầu mới nếu chúng ta muốn xóa nút đầu. Chúng ta cũng cần giải phóng bộ nhớ bị chiếm bởi một nút trong khi xóa một nút.
Dưới đây là các bước để xóa nút đầu:
Bước 1) Gán một biến cho nút đầu hiện tại.
Bước 2) Truy cập nút “tiếp theo” của nút chính hiện tại và đặt nút “trước” (con trỏ trước) là '' NULL". Điều này có nghĩa là chúng tôi đang ngắt kết nối nút thứ hai khỏi nút đầu tiên.
Bước 3) Giải phóng bộ nhớ bị chiếm bởi nút đầu trước đó.
Đây là mã giả để xóa phần đầu khỏi danh sách liên kết đôi:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
Cần phải xóa bộ nhớ được phân bổ sau khi thực hiện bất kỳ loại thao tác xóa nào. Nếu không, trong toàn bộ thời gian chạy của chương trình, bộ nhớ cho khối đã xóa sẽ vẫn bị chiếm dụng. Không ứng dụng nào khác có thể sử dụng phân đoạn bộ nhớ đó.
Xóa phần đuôi của danh sách liên kết đôi.
Thao tác này gần giống như việc xóa phần đầu. Ở đây, thay vì phần đầu, chúng ta cần xóa phần đuôi. Để xác định một nút là nút đuôi, chúng ta nên kiểm tra xem con trỏ tiếp theo hoặc nút tiếp theo có rỗng hay không. Sau khi xóa phần đuôi, chúng ta cần giải phóng bộ nhớ.
Thao tác này còn được gọi là "xóa từ phía sau".
Dưới đây là các bước để thực hiện việc này:
Bước 1) Duyệt cho đến nút cuối của danh sách liên kết đôi.
Bước 2) Gán một biến hoặc con trỏ tới nút đuôi.
Bước 3) Đặt nút “tiếp theo” thành NULL và giải phóng bộ nhớ của nút đuôi.
Đây là mã giả để xóa nút đuôi:
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
Tìm kiếm và xóa một nút khỏi Danh sách liên kết đôi
Thao tác này cho phép chúng ta tìm kiếm dữ liệu nút cụ thể và xóa nút đó. Chúng ta cần thực hiện tìm kiếm tuyến tính vì danh sách liên kết là cấu trúc dữ liệu tuyến tính. Sau khi xóa chúng ta cũng cần giải phóng bộ nhớ.
Sau đây là các bước để tìm kiếm và xóa một nút trong danh sách liên kết đôi:
Bước 1) Duyệt danh sách liên kết từ đầu cho đến khi giá trị của nút bằng mục tìm kiếm.
Bước 2) Gán một biến “deleteNode” cho nút phù hợp.
Bước 3) Gán nút trước của “deleteNode” cho nút tiếp theo.
Bước 4) Giải phóng bộ nhớ của “deleteNode”
Sau đây là mã giả để tìm kiếm và xóa một nút khỏi danh sách được liên kết:
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
Duyệt danh sách liên kết đôi từ phía trước
Để duyệt từ nút đầu và lặp qua nút tiếp theo cho đến khi chúng ta tìm thấy “NULL”. Trong khi duyệt qua từng nút, chúng ta có thể in giá trị của nút đó. Dưới đây là các bước để di chuyển ngang từ phía trước (hướng về phía trước):
Bước 1) Gán một con trỏ hoặc biến cho nút đầu hiện tại.
Bước 2) Lặp lại nút tiếp theo của phần đầu cho đến khi nhận được “NULL”
Bước 3) In dữ liệu của nút trong mỗi lần lặp.
Bước 4) Trả về nút đầu.
Đây là mã giả để duyệt qua Danh sách liên kết đôi từ phía trước:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Ở đây, việc trả lại là không bắt buộc. Nhưng cách tốt nhất là trả lại nút đầu sau các thao tác.
Duyệt danh sách liên kết đôi từ phía sau
Thao tác này ngược lại với thao tác di chuyển ngang từ phía trước. Cách tiếp cận giống nhau với một chút khác biệt. Chúng ta phải duyệt đến nút cuối và sau đó duyệt từ nút cuối tới nút trước.
Dưới đây là các bước để duyệt qua danh sách liên kết đôi từ phía sau:
Bước 1) Di chuyển cho đến khi chúng ta đến được nút đuôi.
Bước 2) Từ nút đuôi, chúng ta sẽ duyệt qua cho đến khi nhận được nút trước đó là “NULL”. “prev” (con trỏ trước) sẽ rỗng đối với nút đầu
Bước 3) Ở mỗi lần lặp, chúng tôi sẽ in dữ liệu nút.
Đây là mã giả để duyệt từ phía sau:
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
Sự khác biệt giữa danh sách liên kết đơn và đôi
Sự khác biệt chính giữa danh sách Liên kết đơn và Danh sách liên kết kép là số lượng liên kết.
Đây là sự khác biệt giữa các nút của Danh sách liên kết đơn và cấu trúc nút của Danh sách liên kết đôi:
| Phần | Danh sách liên kết đơn | Danh sách được liên kết gấp đôi |
|---|---|---|
| Structure | Danh sách liên kết đơn có 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 đôi có một trường dữ liệu và hai liên kết. Một cho nút trước và một cho nút tiếp theo. |
| Truyền tải | Nó chỉ có thể đi từ đầu đến đuôi. | Nó có thể di chuyển cả về phía trước và phía sau. |
| Bộ nhớ | Chiếm ít bộ nhớ hơn. | Nó chiếm nhiều bộ nhớ hơn danh sách liên kết đơn. |
| Khả Năng Tiếp Cận | Danh sách liên kết đơn kém hiệu quả hơn vì chúng chỉ sử dụng một liên kết đến nút tiếp theo. Không có liên kết cho nút trước đó. | Danh sách liên kết đôi hiệu quả hơn Danh sách liên kết đơn. |
Danh sách liên kết đôi trong C++
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
struct node *prev;
};
void insertFront(node* &listHead, int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
if(listHead!=NULL)
{
listHead->prev = newNode;
newNode->next = listHead;
}
listHead = newNode;
cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node * &listHead, int value){
if(listHead==NULL)
{
insertFront(listHead,value);
}
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL){
head = head->next;
}
head->next = newNode;
newNode->prev = head;
cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL && head->data!=searchValue){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
newNode->prev = head;
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL && head->next->data!=searchValue){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
newNode->prev = head;
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
node* head = new node();
head = listHead;
cout<<"Traversal from head:\t";
while(head!=NULL){
cout<<head->data<<"\t ";
head = head->next;
}
cout<<endl;
}
void traverseFromEnd(node *listHead){
node* head = new node();
head = listHead;
cout<<"Traversal from head:\t";
while(head->next!=NULL){
head = head->next;
}
node *tail = head;
while(tail!=NULL){
cout<<tail->data<<"\t";
tail = tail->prev;
}
cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
node* head = new node();
head = (*listHead);
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
if(*listHead == NULL || head == NULL) return;
if((*listHead)->data == head->data){
*listHead = head->next;
}
if(head->next != NULL){
head->next->prev = head->prev;
}
if(head->prev != NULL){
head->prev->next = head->next;
}
free(head);
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
int main(){
node *head = NULL;
insertFront(head,5);
insertFront(head,6);
insertFront(head,7);
insertEnd(head,9);
insertEnd(head,10);
insertAfter(head,5,11);
insertBefore(head,5,20);
traverseFromFront(head);
traverseFromEnd(head);
searchAndDelete(&head,7);
traverseFromFront(head);
traverseFromEnd(head);
}
Đầu ra
Added 5 at the front Added 6 at the front Added 7 at the front Aded 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversal from head: 7 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
Danh sách liên kết đôi trong Python
class node:
def __init__(self,data = None, prev=None, next = None):
self.data = data
self.next = next
self.prev = prev
class DoublyLinkedList:
def __init__(self):
self.head = None
def insertFront(self, val):
newNode = node(data=val)
newNode.next = self.head
if self.head is not None:
self.head.prev = newNode
self.head = newNode
print("Added {} at the front".format(val))
def insertEnd(self,val):
newNode = node(data=val)
if self.head is None:
self.insertFront(val)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
newNode.prev = temp
print("Added {} at the end".format(val))
def traverseFromFront(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
def traverseFromEnd(self):
temp = self.head
print("Traversing from Tail:\t",end="")
while temp.next is not None:
temp = temp.next
tail = temp
while tail is not None:
print("{}\t".format(tail.data),end="")
tail = tail.prev
print()
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
newNode.prev = temp
if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} after node {}".format(value,searchItem))
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
newNode.prev = temp
if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} before node {}".format(value,searchItem))
def searchAndDelete(self,searchItem):
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is temp.data:
self.head = temp.next
if temp.next is not None:
temp.next.prev = temp.prev
if temp.prev is not None:
temp.prev.next = temp.next
print("Deleted Node\t{}".format(searchItem))
return
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
Đầu ra
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversing from head: 7 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6 7 Deleted Node 7 Traversing from head: 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6
Độ phức tạp của danh sách liên kết kép
Nhìn chung, độ phức tạp về thời gian được chia thành ba loại.
Đó là:
- Trường hợp tốt nhất
- Trường hợp trung bình
- Trường hợp xấu nhất
Độ phức tạp thời gian trong trường hợp tốt nhất cho Danh sách liên kết kép:
- Chèn vào đầu hoặc đuôi sẽ tốn O(1). Bởi vì chúng ta không cần phải duyệt bên trong danh sách được liên kết. Con trỏ đầu và đuôi có thể cho chúng ta quyền truy cập vào nút đầu và nút đuôi với độ phức tạp thời gian O(1).
- Xóa ở đầu hoặc đuôi sẽ tốn O(1).
- Tìm kiếm một nút sẽ có độ phức tạp thời gian là O(1). Bởi vì nút mục tiêu có thể là nút đầu.
Độ phức tạp thời gian trong trường hợp trung bình của Danh sách liên kết kép:
- Việc chèn vào đầu hoặc đuôi sẽ có độ phức tạp về thời gian là O(1).
- Việc xóa ở đầu hoặc đuôi sẽ có độ phức tạp thời gian là O(1).
- Tìm kiếm một nút sẽ có độ phức tạp thời gian là O(n). Bởi vì mục tìm kiếm có thể nằm ở bất kỳ đâu giữa danh sách được liên kết. Ở đây, “n” là tổng số nút có trong danh sách được liên kết.
Độ phức tạp thời gian trong trường hợp xấu nhất của danh sách liên kết kép sẽ giống với trường hợp trung bình.
Độ phức tạp của bộ nhớ danh sách liên kết đôi
Độ phức tạp của bộ nhớ là O(n), trong đó “n” là tổng số nút. Trong khi triển khai danh sách liên kết, chúng ta phải giải phóng bộ nhớ đã sử dụng. Nếu không, đối với danh sách liên kết lớn hơn, nó sẽ gây ra rò rỉ bộ nhớ.
Tổng kết
- Danh sách liên kết là một loại cấu trúc dữ liệu tuyến tính, một tập hợp dữ liệu được biểu diễn theo cách tuyến tính.
- Danh sách liên kết đôi là một loại danh sách liên kết trong đó một nút có liên kết với cả nút trước và nút tiếp theo.
- Danh sách liên kết đôi chứa tất cả các thao tác như thêm nút, xóa nút, chèn nút sau hoặc trước nút khác và duyệt qua danh sách liên kết từ đầu đến cuối.
- Danh sách liên kết đôi có một trường dữ liệu và hai liên kết. Một cho nút trước và một cho nút tiếp theo.
- Độ phức tạp của danh sách liên kết kép Trường hợp tốt nhất, Trường hợp trung bình
- Và trường hợp xấu nhất.
