Ở bài viết trước, tôi đã hướng dẫn bạn cách cài đặt danh sách liên kết đơn và các kiến thức về danh sách liên kết. Bài viết này, mình sẽ hướng dẫn bạn cài đặt danh sách liên kết đôi nhé. Danh sách liên kết đôi có sự liên kết 2 chiều giữa 2 phần tử liền kề nhau trong khi danh sách liên kết đơn chỉ có liên kết 1 chiều.
1. Lý thuyết về Danh sách liên kết đôi
Một Node của danh sách liên kết đôi sẽ có dạng như sau:
1
2
3
4
5
---------------------------------------------
| | | |
| PREV | DATA | NEXT |
| | | |
---------------------------------------------
Và hình dưới đây so sanh sự khác nhau giữ dslk đôi và dslk đơn:
Khác biệt giữa danh sách liên kết đơn với danh sách liên kết đôi
NỘI DUNG BÀI VIẾT
2. Cài đặt danh sách liên kết đôi
2.1. Khai báo & khởi tạo
Khác một chút với dslk đơn, ngoài con trỏ next, chúng ta sẽ có thêm con trỏ prev để liên kết với Node trước nó. Chúng ta vẫn sẽ để data có kiểu int để đơn giản và dễ hiểu nhé.
Ngay sau khai báo, chúng ta sẽ khởi tạo Node đầu tiên của danh sách liên kết đôi.
1
2
3
4
5
6
7
structNode{
intdata;
structNode*next;
structNode*prev;
};
structNode*head;// Khởi tạo Node head global của dslk đôi.
2.2. Tạo mới 1 Node
Thay vì chỉ cho next = NULL và gán giá trị cho Node mới, chúng ta cũng phải cho con trỏ prev = NULL.
1
2
3
4
5
6
7
8
structNode*GetNewNode(intx){
structNode*newNode
=(structNode*)malloc(sizeof(structNode));
newNode->data=x;
newNode->prev=NULL;
newNode->next=NULL;
returnnewNode;
}
2.3. Thêm Node
Thêm vào đầu
Nếu head = NULL, ta sẽ cho cả head và tail = newNode.
Nếu head != NULL, ta sẽ cập nhật lại head mới là newNode. Ta cần tạo liên kết giữa head hiện tại với newNode trước khi cho newNode làm head mới.
1
2
3
4
5
6
7
8
9
10
11
voidInsertAtHead(intx){
structNode*newNode=GetNewNode(x);
if(head==NULL){
head=newNode;
tail=newNode;
return;
}
head->prev=newNode;
newNode->next=head;
head=newNode;
}
Về cơ bản, ý tưởng thêm Node vào đầu/ cuối vẫn giống với thêm vào đầu trong danh sách liên kết đơn.
Thêm vào cuối
Nếu head = NULL, newNode sẽ là head và tail luôn
Nếu head != NULL, cập nhật lại tail mới là newNode. Ta cần tạo liên kết thằng tail hiện tại với newNode trước khi để newNode làm tail mới.
1
2
3
4
5
6
7
8
9
10
11
voidInsertAtTail(intx){
structNode*newNode=GetNewNode(x);
if(head==NULL){
head=newNode;
tail=newNode;
return;
}
tail->next=newNode;
newNode->prev=tail;
tail=newNode;
}
2.4. Xóa Node
Xóa ở đầu
Nếu head = NULL, chẳng có gì để xóa
Nếu head != NULL, cho head mới bằng phần tử tiếp theo và sửa prev của nó = NULL(ngắt liên kết với thằng head cũ).
1
2
3
4
5
6
7
voidDeleteAtHead(){
if(head==NULL){
return;
}
head=head->next;
head->prev=NULL;
}
Xóa ở cuối
Nếu head = NULL, chẳng có gì để xóa
Nếu head != NULL, cho tail mới bằng phần tử trước nó và sửa next của nó = NULL(ngắt liên kết với thằng tail cũ).
1
2
3
4
5
6
7
voidDeleteAtTail(){
if(head==NULL){
return;
}
tail=tail->prev;
tail->next=NULL;
}
2.5. Duyệt danh sách liên kết
Duyệt từ đầu tới cuối
Ta sẽ duyệt bắt đầu từ Node head cho tới trước khi gặp Node NULL bằng cách dùng con trỏ next.
1
2
3
4
5
6
7
8
9
voidPrint(){
structNode*temp=head;
printf("\nForward: ");
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
printf("\n");
}
Duyệt từ cuối về đầu
Lần này, ta sẽ duyệt bắt đầu từ Node tailcho tới trước khi gặp Node NULL bằng cách dùng con trỏ prev.
1
2
3
4
5
6
7
8
9
10
11
voidReversePrint(){
structNode*temp=tail;
if(temp==NULL)return;// empty list, exit
// Traversing backward using prev pointer
printf("\nReverse: ");
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->prev;
}
printf("\n");
}
3. Full code danh sách liên kết đôi
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* Doubly Linked List implementation */
#include<stdio.h>
#include<stdlib.h>
structNode{
intdata;
structNode*next;
structNode*prev;
};
structNode*head,*tail;// Khởi tạo Node head global của dslk đôi.
//Creates a new Node and returns pointer to it.
structNode*GetNewNode(intx){
structNode*newNode
=(structNode*)malloc(sizeof(structNode));
newNode->data=x;
newNode->prev=NULL;
newNode->next=NULL;
returnnewNode;
}
//Inserts a Node at head of doubly linked list
voidInsertAtHead(intx){
structNode*newNode=GetNewNode(x);
if(head==NULL){
head=newNode;
tail=newNode;
return;
}
head->prev=newNode;
newNode->next=head;
head=newNode;
}
//Inserts a Node at tail of Doubly linked list
voidInsertAtTail(intx){
structNode*newNode=GetNewNode(x);
if(head==NULL){
head=newNode;
tail=newNode;
return;
}
tail->next=newNode;
newNode->prev=tail;
tail=newNode;
}
voidDeleteAtHead(){
if(head==NULL){
return;
}
head=head->next;
head->prev=NULL;
}
//Inserts a Node at tail of Doubly linked list
voidDeleteAtTail(){
if(head==NULL){
return;
}
tail=tail->prev;
tail->next=NULL;
}
//Prints all the elements in linked list in forward traversal order
voidPrint(){
structNode*temp=head;
printf("\nForward: ");
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
printf("\n");
}
//Prints all elements in linked list in reverse traversal order.
voidReversePrint(){
structNode*temp=tail;
if(temp==NULL)return;// empty list, exit
// Traversing backward using prev pointer
printf("\nReverse: ");
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->prev;
}
printf("\n");
}
intmain(){
/*Driver code to test the implementation*/
head=NULL;// empty list. set head as NULL.
// Calling an Insert and printing list both in forward as well as reverse direction.
