Chèn Node vào danh sách liên kết đôi - Danh sách liên kết đôi
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách chèn Node vào danh sách liên kết đôi. Đây làm một bước khá quan trọng trong việc thêm dữ liệu vào danh sách. Chúng ta sẽ cùng nhau tìm hiểu hai cách thêm Node vào danh sách liên kết đôi Thêm Node vào đầu ...
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách chèn Node vào danh sách liên kết đôi. Đây làm một bước khá quan trọng trong việc thêm dữ liệu vào danh sách.
Chúng ta sẽ cùng nhau tìm hiểu hai cách thêm Node vào danh sách liên kết đôi
- Thêm Node vào đầu danh sách.
- Thêm Node vào cuối danh sách.
1. Thêm Node vào đầu danh sách
Trong phần này chúng ta sẽ thêm Node vào đầu danh sách (insertFirst). Về cơ bản thì nó tương tự như danh sách liên kết đơn, cùng mình tìm hiểu xem cách thêm nó như thế nào nhé.
Đầu tiên ta sử dụng hàm CreateNode() để tạo một Node mới newNode.
Tiếp đến ta xét điều kiện, nếu danh sách rỗng thì newNode vừa là Node đầu và Node cuối: head = newNode và tail = newNode. Nếu trong danh sách có phần tử thì ta thực hiện chèn vào đầu danh sách bằng cách:
- Thiết lập con trỏ prev của head trỏ đến newNode:
head -> prev = newNode - Thiết lập con trỏ next của newNode trỏ đến head:
newNode -> next = head - Dịch chuyển Node head về newNode, vì head luôn luôn quản lý Node đầu tiên trong danh sách:
head = newNode
/* thêm node vào đầu danh sách */
void InsertAtHead(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}2. Thêm Node vào cuối danh sách
Trong phần này chúng ta sẽ thực hiện chèn Node vào cuối danh sách, đây là cách thường được sử dụng rất nhiều.
Tương tự như thêm Node vào đầu danh sách, ta sử dụng hàm CreateNode() để tạo một Node mới newNode.
Sau đó cũng xét điều kiện, nếu danh sách rỗng thì newNode vừa là head vừa là tail. Nếu danh sách có phần tử thì ta thực hiện:
- Thiết lập con trỏ next của tail trỏ đến newNode.
- Thiết lập con trỏ prev của newNode trỏ đến tail.
- Dịch chuyển tail về newNode, vì tail luôn luôn quản lý Node cuối cùng.
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}3. Ví dụ thêm Node vào danh sách liên kết đôi
Trong ví dụ này chúng ta sẽ thực hiện một chương trình tạo một danh sách liên kết đôi với các thao tác: tạo, thêm vào đầu, thêm vào cuối, duyệt danh sách theo hai chiều.
Đầu tiên ta cần tạo cấu trúc dữ liệu cho danh sách liên kết đôi.
/* tạo cấu trúc node */
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.
/* tạo node mới */
struct Node* CreateNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}Tiếp đến ta viết hàm tạo Node CreateNode().
/* tạo node mới */
struct Node* CreateNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}Để kiểm tra được kết quả của chương trình ta cần một hàm duyệt danh sách: duyệt từ đầu đến cuối (Print()) và duyệt từ cuối về đầu (ReversePrint()).
/* hiển thị từ cuối về đầu */
void ReversePrint() {
struct Node* temp = tail;
if(temp == NULL) return; // empty list, exit
// Traversing backward using prev pointer
printf("
Cuối về đầu: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("
");
}
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}Và cuối cùng là hai cách thêm Node vào danh sách mà ta đã tìm hiểu ở trên.
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}Full code:
#include <iostream>
using namespace std;
/* tạo cấu trúc node */
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.
/* tạo node mới */
struct Node* CreateNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* hiển thị từ đầu đến cuối */
void Print() {
struct Node* temp = head;
printf("
Đầu đến cuối: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("
");
}
/* hiển thị từ cuối về đầu */
void ReversePrint() {
struct Node* temp = tail;
if(temp == NULL) return; // empty list, exit
// Traversing backward using prev pointer
printf("
Cuối về đầu: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("
");
}
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}
int main() {
head = NULL;
//gọi hàm thêm node vào đầu danh sách
InsertFirst(2);
InsertFirst(3);
InsertFirst(4);
cout<<"Danh sách sau khi thêm node vào đầu:
";
Print();
ReversePrint();
cout<<"
----------end--------------
";
//gọi hàm thêm node vào cuối danh sách
InsertLast(5);
InsertLast(6);
InsertLast(7);
cout<<"Danh sách sau khi thêm node vào cuối:
";
Print();
ReversePrint();
cout<<"
---------------------------------------
";
cout<<"Chương trình này được đăng tại Zaidap.com.net";
}Kết quả:
4. Kết luận
Như vậy là chúng ta đã tìm hiểu xong hai cách thêm Node vào danh sách liên kết đôi đó là thêm vào đầu danh sách và thêm vào cuối danh sách. Cũng như thực hiện chương trình thêm Node vào danh sách trong C++. Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách xóa Node trong danh sách liên kết đôi, hãy chú ý theo dõi nhé !!!
