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

This entry is part 5 of 16 in the series Cấu trúc dữ liệu

Ở 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.

Nội dung chính Show

2. Cài đặt danh sách liên kết đôi
2.1. Khai báo & khởi tạo
2.2. Tạo mới 1 Node
2.3. Thêm Node
2.4. Xóa Node
2.5. Duyệt danh sách liên kết
3. Full code danh sách liên kết đôi
Video liên quan

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:

---------------------------------------------

| | | |

| 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

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.

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

struct Node* 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.

struct Node* GetNewNode(int x) {

struct Node* newNode

= (struct Node*)malloc(sizeof(struct Node));

newNode->data = x;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

}

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.

void InsertAtHead(int x) {

struct Node* 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.

void InsertAtTail(int x) {

struct Node* 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ũ).

void DeleteAtHead() {

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ũ).

void DeleteAtTail() {

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.

void Print() {

struct Node* 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.

void ReversePrint() {

struct Node* 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

100

101

102

103

104

105

106

107

108

109

110

/* Doubly Linked List implementation */

#include

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

struct Node *head, *tail; // Khởi tạo Node head global của dslk đôi.

//Creates a new Node and returns pointer to it.

struct Node* GetNewNode(int x) {

struct Node* newNode

= (struct Node*)malloc(sizeof(struct Node));

newNode->data = x;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

}

//Inserts a Node at head of doubly linked list

void InsertAtHead(int x) {

struct Node* 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

void InsertAtTail(int x) {

struct Node* newNode = GetNewNode(x);

if(head == NULL) {

head = newNode;

tail = newNode;

return;

}

tail->next = newNode;

newNode->prev = tail;

tail = newNode;

}

void DeleteAtHead() {

if(head == NULL) {

return;

}

head = head->next;

head->prev = NULL;

}

//Inserts a Node at tail of Doubly linked list

void DeleteAtTail() {

if(head == NULL) {

return;

}

tail = tail->prev;

tail->next = NULL;

}

//Prints all the elements in linked list in forward traversal order

void Print() {

struct Node* 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.

void ReversePrint() {

struct Node* 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");

}

int main() {

/*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.

InsertAtTail(2);

Print(); ReversePrint();

InsertAtTail(4);

Print(); ReversePrint();

InsertAtHead(6);

Print(); ReversePrint();

InsertAtTail(8);

Print(); ReversePrint();

DeleteAtHead();

Print(); ReversePrint();

DeleteAtTail();

Print(); ReversePrint();

}

Kết quả chạy:

Forward: 2

Reverse: 2

Forward: 2 4

Reverse: 4 2

Forward: 6 2 4

Reverse: 4 2 6

Forward: 6 2 4 8

Reverse: 8 4 2 6

Forward: 2 4 8

Reverse: 8 4 2

Forward: 2 4

Reverse: 4 2

Process returned 0 (0x0) execution time : 0.040 s

Press any key to continue.

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

2. Cài đặt danh sách liên kết đôi

2.1. Khai báo & khởi tạo

2.2. Tạo mới 1 Node

2.3. Thêm Node

Thêm vào đầu

Thêm vào cuối

2.4. Xóa Node

Xóa ở đầu

Xóa ở cuối

2.5. Duyệt danh sách liên kết

Duyệt từ đầu tới cuối

Duyệt từ cuối về đầu

3. Full code danh sách liên kết đôi

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội