Chào ace, bài này tất cả chúng ta sẽ tìm hiểu và khám phá về Danh sách liên kết kép – Doubly Linked List trong series tự học về cấu trúc tài liệu ( CTDL ) và giải thuật, sau đây cafedev sẽ trình làng và san sẻ cụ thể ( khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ … ) về nó trải qua những phần sau .
Trước khi đọc bài này, chúng tôi khuyên bạn nên đọc trước về các bài sau:
Bạn đang đọc: [CTDL] Danh sách liên kết kép – Doubly Linked List | Phần 1. Giới thiệu và chèn thêm node mới » https://final-blade.com
– Danh sách liên kết đơn – Linked List – Phần 1. Giới thiệu
– Danh sách liên kết đơn – Linked List – Phần 2. Chèn thêm node
So với Linked List thì một Doubly Linked List ( DLL – danh sách liên kết kép ) sẽ chứa thêm một con trỏ phụ, thường được gọi là previous pointer ( con trỏ trỏ đến node trước đó ), con trỏ previous này cùng với con trỏ next và phần data chứa tài liệu / giá trị của node ( 2 thành phần này đều nằm trong một node của linked list thường thì ) sẽ là những thành phần tạo nên một Doubly Linked List .
Dưới đây là đoạn code thiết lập một node của DLL bằng ngôn từ C :
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C JAVA PYTHON3
C
/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};
JAVA
// Class for Doubly Linked List
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
}
PYTHON3
# Node of a doubly linked list
class Node:
def __init__(self, next=None, prev=None, data=None):
self.next = next # reference to next node in DLL
self.prev = prev # reference to previous node in DLL
self.data = data
Tóm Tắt
1. Ưu điểm của danh sách liên kết kép – DLL so với danh sách liên kết đơn – LL
1. Đối với một DLL, tất cả chúng ta hoàn toàn có thể thực thi duyệt xuôi chiều, hoặc duyệt ngược chiều trên danh sách, đều được
2. Thao tác xóa node trong DLL sẽ hiệu suất cao hơn vì tất cả chúng ta có được con trỏ trỏ đến node cần xóa
3. Chúng ta hoàn toàn có thể chèn thêm một node mới vào phía trước một node đơn cử nào đó, một cách nhanh gọn. Trong Linked List thường thì, để xóa một node, tất cả chúng ta cần phải biết được tron trỏ trỏ đến node nằm trước node muốn xóa. Để có được node nằm trước node muốn xóa, đôi lúc tất cả chúng ta sẽ phải duyệt cả danh sách. Trong DLL, tất cả chúng ta hoàn toàn có thể có được node nằm trước node muốn xóa bằng cách sử dụng con trỏ previous .
2. Những điểm hạn chế của danh sách liên kết kép – DLL so với danh sách liên kết đơn – LL
1. Mọi node nằm trong DLL đều nhu yếu thêm khoảng trống dành cho một con trỏ previous. Tuy nhiên ta vẫn hoàn toàn có thể setup DLL với một con trỏ duy nhất, vẫn có cách để làm được điều đó .
2. Tất cả những thao tác đều nhu yếu phải duy trì thêm một con trỏ là con trỏ previous. Ví dụ, khi triển khai chèn thêm node mới vào trong DLL, tất cả chúng ta sẽ phải chỉnh sửa những con trỏ previous cùng với những con trỏ next. Ví dụ, trong những hàm chèn thêm node mới vào những vị trí khác nhau trên DLL, tất cả chúng ta sẽ cần thêm 1 hoặc 2 bước để thiết lập con trỏ previous .
3. Thao tác chèn thêm node mới vào trong DLL
Một node hoàn toàn có thể được chèn vào theo một trong bốn cách sau :
1. Chèn thêm vào đầu DLL
2. Chèn thêm vào phía sau một node đơn cử nào đó
3. Chèn thêm vào cuối DLL
4. Chèn thêm vào phía trước một node đơn cử nào đó
3.1. Chèn thêm node mới vào đầu DLL (gồm 5 bước)
Node mới sẽ luôn luôn được chèn vào phía trước node head của linked list được cho. Và node vừa mới được chèn thêm vào sẽ trở thành node head mới của DLL. Ví dụ, nếu DLL được cho có dạng 10 -> 15 -> 20 -> 25 và tất cả chúng ta chèn thêm một thành phần 5 vào phía trước, lúc đó DLL này sẽ trở thành 5 -> 10 -> 15 -> 20 -> 25. Chúng ta hãy gọi hàm có công dụng chèn thêm node mới vào phần đầu của DLL là hàm push ( ). Hàm push ( ) phải nhận vào một con trỏ trỏ đến con trỏ head, do tại hàm push phải biến hóa con trỏ head để con trỏ head trỏ đến node mới được chèn vào .
Dưới đây là 5 bước để chèn thêm node mới vào phần đầu của danh sách liên kết kép ( DLL ) :
Truyền vào cho hàm push ( ) một tham chiếu ( con trỏ trỏ đến con trỏ ) tới node head của DLL, một giá trị int mà node đó sẽ chứa, hàm push ( ) sẽ triển khai chèn thêm một node mới vào phần đầu của danh sách liên kết kép ( DLL ) :
1. Cấp phát bộ nhớ cho node mới
2. Truyền dữ liệu ( chính là giá trị int ) vào node mới
3. Làm cho con trỏ next của node mới trỏ đến ( bằng với ) con trỏ head của DLL, và làm cho con trỏ previous của node mới bằng với NULL
4. Làm cho con trỏ prev của node head trỏ đến node mới cần được chèn vào
5. Làm cho con trỏ head trỏ đến node mới được chèn vào
C
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
Java
// Adding a node at the front of the list
public void push(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_Node = new Node(new_data);
/* 3. Make next of new node as head and previous as NULL */
new_Node.next = head;
new_Node.prev = null;
/* 4. change prev of head node to new node */
if (head != null)
head.prev = new_Node;
/* 5. move the head to point to the new node */
head = new_Node;
}
Python3
# Adding a node at the front of the list
def push(self, new_data):
# 1 & 2: Allocate the Node & Put in the data
new_node = Node(data = new_data)
# 3. Make next of new node as head and previous as NULL
new_node.next = self.head
new_node.prev = None
# 4. change prev of head node to new node
if self.head is not None:
self.head.prev = new_node
# 5. move the head to point to the new node
self.head = new_node
Có 4 trong 5 bước ở phía trên giống với 4 bước được sử dụng để chèn thêm node mới vào phần đầu của danh sách liên kết đơn ( singly linked list ). Bước bổ trợ duy nhất là đổi khác con trỏ prev của node head .
3.2. Chèn thêm một node mới vào sau một node cụ thể trong DLL (gồm 7 bước)
Ở đây, tất cả chúng ta được cho một con trỏ trỏ đến một node, là con trỏ prev_node, và node mới sẽ được chèn vào phía sau một node đơn cử trong DLL .
Dưới đây là 7 bước để chèn thêm một node mới vào phía sau một node đơn cử trong DLL :
Hàm insertAfter ( ) sẽ nhận vào một node để làm prev_node, và một giá trị int mà node đó sẽ chứa. Hàm insertAfter ( ) sẽ thực thi chèn thêm một node mới vào phía sau node được cho .
1. Kiểm tra xem prev_node nhận vào có NULL hay không, nếu NULL thì return luôn .
2. Cấp phát bộ nhớ cho node mới .
3. Truyền dữ liệu ( giá trị ) vào node mới
4. Làm cho con trỏ next của node mới trỏ đến ( bằng với ) con trỏ next của prev_node
5. Làm cho con trỏ next của prev_node trỏ đến ( bằng với ) node mới được chèn vào
6. Làm cho con trỏ prev của node mới được chèn vào trỏ đến ( bằng với node prev_node. Hay nói cách khác là làm cho prev_node trở thành node trước đó của new_node
7. Làm cho con trỏ prev của con trỏ next của new_node trỏ đến ( bằng với ) chính new_node
C
/* Given a node as prev_node, insert a new node after the given node */
void insertAfter(struct Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
/* 2. allocate new node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. Make the next of prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of new_node's next node */
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
Java
Xem thêm: Tìm hiểu về ngôn ngữ lập trình C++
/* Given a node as prev_node, insert a new node after the given node */
public void InsertAfter(Node prev_Node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_Node == null) {
System.out.println("The given previous node cannot be NULL ");
return;
}
/* 2. allocate node
* 3. put in the data */
Node new_node = new Node(new_data);
/* 4. Make next of new node as next of prev_node */
new_node.next = prev_Node.next;
/* 5. Make the next of prev_node as new_node */
prev_Node.next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node.prev = prev_Node;
/* 7. Change previous of new_node's next node */
if (new_node.next != null)
new_node.next.prev = new_node;
}
Python
# Given a node as prev_node, insert
# a new node after the given node
def insertAfter(self, prev_node, new_data):
# 1. check if the given prev_node is NULL
if prev_node is None:
print("This node doesn't exist in DLL")
return
#2. allocate node & 3. put in the data
new_node = Node(data = new_data)
# 4. Make next of new node as next of prev_node
new_node.next = prev_node.next
# 5. Make the next of prev_node as new_node
prev_node.next = new_node
# 6. Make prev_node as previous of new_node
new_node.prev = prev_node
# 7. Change previous of new_node's next node */
if new_node.next is not None:
new_node.next.prev = new_node
Có 5 trong 7 bước ở phía trên giống với 5 bước được sử dụng để chèn thêm một node mới vào phía sau một node đơn cử trong danh sách liên kết đơn ( singly linked list ). Cần thêm 2 bước bổ trợ để đổi khác con trỏ prev của new_node và biến hóa con trỏ prev của node next của new_node .
4.3. Chèn thêm một node mới vào cuối DLL (gồm 7 bước)
Trong trường hợp này, node mới sẽ luôn luôn được chèn thêm vào phía sau node sau cuối của DLL được cho. Ví dụ, nếu DLL được cho có dạng 5 -> 10 -> 15 -> 20 -> 25 và tất cả chúng ta chèn thêm một thành phần 30 vào cuối, lúc này DLL sẽ trở thành 5 -> 10 -> 15 -> 20 -> 25 -> 30 .
Bởi vì về cơ bản, danh sách liên kết kép hay danh sách liên kết nói chung đều được đại diện thay mặt bởi con trỏ head của chúng, vậy nên tất cả chúng ta sẽ phải duyệt từ đầu tới cuối danh sách và sau đó biến hóa con trỏ next của node ở đầu cuối để cho con trỏ next này trỏ đến node mới được chèn thêm vào .
Dưới dây là 7 bước để chèn thêm một node mới vào cuối danh sách liên kết kép .
Hàm append ( ) sẽ nhận vào một tham chiếu ( con trỏ trỏ đến con trỏ ) tới con trỏ head của một DLL và một giá trị int mà node đó sẽ chứa. Hàm append ( ) sẽ triển khai chèn thêm một node mới vào phần cuối của DLL .
1. Cấp phát bộ nhớ cho new_node
2. Truyền dữ liệu ( giá trị ) vào new_node
3. new_node sẽ trở thành node sau cuối của DLL, thế cho nên tất cả chúng ta phải làm cho con trỏ next của new_node trở thành / bằng với NULL
4. Nếu DLL đang trống, vậy thì ta sẽ làm cho new_node trở thành node head của DLL luôn, tức là làm cho con trỏ head của DLL trỏ đến new_node
5. Nếu DLL không trống, ta sẽ duyệt tới node sau cuối của DLL
6. Thay đổi con trỏ next của node sau cuối của DLL để cho con trỏ next này trỏ đến new_node
7. Làm cho node từng là sau cuối của DLL trở thành node trước đó của new_node, tức là làm cho con trỏ prev của new_node trỏ đến / bằng với node từng là ở đầu cuối của DLL .
C
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void append(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
Java
// Add a node at the end of the list
void append(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
/* 3. This new node is going to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
* node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
Python
# Add a node at the end of the DLL
def append(self, new_data):
# 1. allocate node 2. put in the data
new_node = Node(data = new_data)
last = self.head
# 3. This new node is going to be the
# last node, so make next of it as NULL
new_node.next = None
# 4. If the Linked List is empty, then
# make the new node as head
if self.head is None:
new_node.prev = None
self.head = new_node
return
# 5. Else traverse till the last node
while (last.next is not None):
last = last.next
# 6. Change the next of last node
last.next = new_node
# 7. Make last node as previous of new node */
new_node.prev = last
Có 6 trong 7 bước ở phía trên là giống với 6 bước được sử dụng để chèn thêm một node mới vào phía sau một node đơn cử trong singly linked list – danh sách liên kết đơn thường thì. Ở đây, tất cả chúng ta cần thêm 1 bước bổ trợ để biến hóa con trỏ prev của new_node .
3.4. Chèn thêm một node mới vào phía trước một node cụ thể
Trước hết, tất cả chúng ta sẽ có con trỏ trỏ đến node đơn cử này là next_node, và phần tài liệu của new_node sẽ được chèn thêm vào là new_data. Các bước :
1. Kiểm tra xem next_node có NULL hay không. Nếu next_node là NULL, tất cả chúng ta sẽ return luôn chính bới không hề chèn thêm bất kỳ node mới nào vào trước một node đang NULL .
2. Cấp phát bộ nhớ cho node mới cần được chèn thêm vào DLL, hãy gọi node mới này là new_node .
3. Thiết lập new_node -> data = new_data
4. Thiết lập con trỏ prev của new_node trỏ đến / bằng với con trỏ / node prev của next_node, bằng câu lệnh new_node -> prev = next_node -> prev
5. Thiết lập con trỏ prev của next_node trỏ đến / bằng với new_node, bằng câu lệnh next_node -> prev = new_node
6. Thiết lập con trỏ next của new_node trỏ đến / bằng với next_node, bằng câu lệnh new_node -> next = next_node
7. Nếu con trỏ prev của new_node không NULL, ta sẽ thiết lập con trỏ next của con trỏ / node prev này trỏ đến / bằng với new_node, bằng câu lệnh new_node -> prev -> next = new_node
8. Nếu con trỏ prev của new_node là NULL, nó sẽ trở thành node head mới, vậy thì ta sẽ làm cho nó trở thành như vậy bằng câu lệnh ( * head_ref ) = new_node .
Dưới đây là đoạn code thiết lập bằng ngôn từ C / C + + cho thuật toán trên :
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C / C + +
// A complete working C program to demonstrate all
// insertion before a given node
#include
#include
// A linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
/* Given a node as next_node, insert a new node before the given node */
void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data)
{
/*1. check if the given next_node is NULL */
if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
/* 2. allocate new node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make prev of new node as prev of next_node */
new_node->prev = next_node->prev;
/* 5. Make the prev of next_node as new_node */
next_node->prev = new_node;
/* 6. Make next_node as next of new_node */
new_node->next = next_node;
/* 7. Change next of new_node's previous node */
if (new_node->prev != NULL)
new_node->prev->next = new_node;
/* 8. If the prev of new_node is NULL, it will be
the new head node */
else
(*head_ref) = new_node;
}
// This function prints contents of linked list starting from the given node
void printList(struct Node* node)
{
struct Node* last;
printf("\nTraversal in forward direction \n");
while (node != NULL) {
printf(" %d ", node->data);
last = node;
node = node->next;
}
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
printf(" %d ", last->data);
last = last->prev;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 4);
// Insert 8, before 1. So linked list becomes 4->8->1->7->NULL
insertBefore(&head, head->next, 8);
printf("Created DLL is: ");
printList(head);
getchar();
return 0;
}
Kết quả in ra là :
Created DLL is:
Traversal in forward direction
4 8 1 7
Traversal in reverse direction
7 1 8 4
Cuối cùng, tất cả chúng ta sẽ cùng tìm hiểu thêm một đoạn chương trình hoàn hảo được viết bằng nhiều ngôn từ lập trình khác nhau, để kiểm tra những hàm tất cả chúng ta đã tìm hiểu và khám phá ở trên :
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C C++ JAVA PYTHON C#
C
// A complete working C program to demonstrate all insertion methods
#include
#include
// A linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
/* Given a node as prev_node, insert a new node after the given node */
void insertAfter(struct Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
/* 2. allocate new node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. Make the next of prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of new_node's next node */
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void append(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
// This function prints contents of linked list starting from the given node
void printList(struct Node* node)
{
struct Node* last;
printf("\nTraversal in forward direction \n");
while (node != NULL) {
printf(" %d ", node->data);
last = node;
node = node->next;
}
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
printf(" %d ", last->data);
last = last->prev;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// Insert 6. So linked list becomes 6->NULL
append(&head, 6);
// Insert 7 at the beginning. So linked list becomes 7->6->NULL
push(&head, 7);
// Insert 1 at the beginning. So linked list becomes 1->7->6->NULL
push(&head, 1);
// Insert 4 at the end. So linked list becomes 1->7->6->4->NULL
append(&head, 4);
// Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);
printf("Created DLL is: ");
printList(head);
getchar();
return 0;
}
C++
// A complete working C++ program to
// demonstrate all insertion methods
#include
using namespace std;
// A linked list node
class Node
{
public:
int data;
Node* next;
Node* prev;
};
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
/* Given a node as prev_node, insert a new node after the given node */
void insertAfter(Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL)
{
cout<<"the given previous node cannot be NULL";
return;
}
/* 2. allocate new node */
Node* new_node = new Node();
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. Make the next of prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of new_node's next node */
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void append(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL)
{
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
// This function prints contents of
// linked list starting from the given node
void printList(Node* node)
{
Node* last;
cout<<"\nTraversal in forward direction \n";
while (node != NULL)
{
cout<<" "<data<<" ";
last = node;
node = node->next;
}
cout<<"\nTraversal in reverse direction \n";
while (last != NULL)
{
cout<<" "<data<<" ";
last = last->prev;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
// Insert 6. So linked list becomes 6->NULL
append(&head, 6);
// Insert 7 at the beginning. So
// linked list becomes 7->6->NULL
push(&head, 7);
// Insert 1 at the beginning. So
// linked list becomes 1->7->6->NULL
push(&head, 1);
// Insert 4 at the end. So linked
// list becomes 1->7->6->4->NULL
append(&head, 4);
// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);
cout << "Created DLL is: ";
printList(head);
return 0;
}
Java
// A complete working Java program to demonstrate all
// Class for Doubly Linked List
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
// Adding a node at the front of the list
public void push(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_Node = new Node(new_data);
/* 3. Make next of new node as head and previous as NULL */
new_Node.next = head;
new_Node.prev = null;
/* 4. change prev of head node to new node */
if (head != null)
head.prev = new_Node;
/* 5. move the head to point to the new node */
head = new_Node;
}
/* Given a node as prev_node, insert a new node after the given node */
public void InsertAfter(Node prev_Node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_Node == null) {
System.out.println("The given previous node cannot be NULL ");
return;
}
/* 2. allocate node
* 3. put in the data */
Node new_node = new Node(new_data);
/* 4. Make next of new node as next of prev_node */
new_node.next = prev_Node.next;
/* 5. Make the next of prev_node as new_node */
prev_Node.next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node.prev = prev_Node;
/* 7. Change previous of new_node's next node */
if (new_node.next != null)
new_node.next.prev = new_node;
}
// Add a node at the end of the list
void append(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
/* 3. This new node is going to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
* node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// This function prints contents of linked list starting from the given node
public void printlist(Node node)
{
Node last = null;
System.out.println("Traversal in forward Direction");
while (node != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println();
System.out.println("Traversal in reverse direction");
while (last != null) {
System.out.print(last.data + " ");
last = last.prev;
}
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
/* Start with the empty list */
DLL dll = new DLL();
// Insert 6. So linked list becomes 6->NULL
dll.append(6);
// Insert 7 at the beginning. So linked list becomes 7->6->NULL
dll.push(7);
// Insert 1 at the beginning. So linked list becomes 1->7->6->NULL
dll.push(1);
// Insert 4 at the end. So linked list becomes 1->7->6->4->NULL
dll.append(4);
// Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL
dll.InsertAfter(dll.head.next, 8);
System.out.println("Created DLL is: ");
dll.printlist(dll.head);
}
}
Python
# A complete working Python program to demonstrate all
# insertion methods
# A linked list node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Class to create a Doubly Linked List
class DoublyLinkedList:
# Constructor for empty Doubly Linked List
def __init__(self):
self.head = None
# Given a reference to the head of a list and an
# integer, inserts a new node on the front of list
def push(self, new_data):
# 1. Allocates node
# 2. Put the data in it
new_node = Node(new_data)
# 3. Make next of new node as head and
# previous as None (already None)
new_node.next = self.head
# 4. change prev of head node to new_node
if self.head is not None:
self.head.prev = new_node
# 5. move the head to point to the new node
self.head = new_node
# Given a node as prev_node, insert a new node after
# the given node
def insertAfter(self, prev_node, new_data):
# 1. Check if the given prev_node is None
if prev_node is None:
print "the given previous node cannot be NULL"
return
# 2. allocate new node
# 3. put in the data
new_node = Node(new_data)
# 4. Make net of new node as next of prev node
new_node.next = prev_node.next
# 5. Make prev_node as previous of new_node
prev_node.next = new_node
# 6. Make prev_node ass previous of new_node
new_node.prev = prev_node
# 7. Change previous of new_nodes's next node
if new_node.next is not None:
new_node.next.prev = new_node
# Given a reference to the head of DLL and integer,
# appends a new node at the end
def append(self, new_data):
# 1. Allocates node
# 2. Put in the data
new_node = Node(new_data)
# 3. This new node is going to be the last node,
# so make next of it as None
new_node.next = None
# 4. If the Linked List is empty, then make the
# new node as head
if self.head is None:
new_node.prev = None
self.head = new_node
return
# 5. Else traverse till the last node
last = self.head
while(last.next is not None):
last = last.next
# 6. Change the next of last node
last.next = new_node
# 7. Make last node as previous of new node
new_node.prev = last
return
# This function prints contents of linked list
# starting from the given node
def printList(self, node):
print "\nTraversal in forward direction"
while(node is not None):
print " % d" %(node.data),
last = node
node = node.next
print "\nTraversal in reverse direction"
while(last is not None):
print " % d" %(last.data),
last = last.prev
# Driver program to test above functions
# Start with empty list
llist = DoublyLinkedList()
# Insert 6. So the list becomes 6->None
llist.append(6)
# Insert 7 at the beginning.
# So linked list becomes 7->6->None
llist.push(7)
# Insert 1 at the beginning.
# So linked list becomes 1->7->6->None
llist.push(1)
# Insert 4 at the end.
# So linked list becomes 1->7->6->4->None
llist.append(4)
# Insert 8, after 7.
# So linked list becomes 1->7->8->6->4->None
llist.insertAfter(llist.head.next, 8)
print "Created DLL is: ",
llist.printList(llist.head)
C#
// A complete working C# program to demonstrate all
using System;
// Class for Doubly Linked List
public class DLL
{
Node head; // head of list
/* Doubly Linked list Node*/
public class Node
{
public int data;
public Node prev;
public Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
public Node(int d)
{
data = d;
}
}
// Adding a node at the front of the list
public void push(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_Node = new Node(new_data);
/* 3. Make next of new node as
head and previous as NULL */
new_Node.next = head;
new_Node.prev = null;
/* 4. change prev of head node to new node */
if (head != null)
head.prev = new_Node;
/* 5. move the head to point to the new node */
head = new_Node;
}
/* Given a node as prev_node, insert
a new node after the given node */
public void InsertAfter(Node prev_Node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_Node == null)
{
Console.WriteLine("The given previous node cannot be NULL ");
return;
}
/* 2. allocate node
* 3. put in the data */
Node new_node = new Node(new_data);
/* 4. Make next of new node as next of prev_node */
new_node.next = prev_Node.next;
/* 5. Make the next of prev_node as new_node */
prev_Node.next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node.prev = prev_Node;
/* 7. Change previous of new_node's next node */
if (new_node.next != null)
new_node.next.prev = new_node;
}
// Add a node at the end of the list
void append(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
/* 3. This new node is going
to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty,
then make the new * node as head */
if (head == null)
{
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// This function prints contents of
// linked list starting from the given node
public void printlist(Node node)
{
Node last = null;
Console.WriteLine("Traversal in forward Direction");
while (node != null) {
Console.Write(node.data + " ");
last = node;
node = node.next;
}
Console.WriteLine();
Console.WriteLine("Traversal in reverse direction");
while (last != null) {
Console.Write(last.data + " ");
last = last.prev;
}
}
/* Driver code*/
public static void Main(String[] args)
{
/* Start with the empty list */
DLL dll = new DLL();
// Insert 6. So linked list becomes 6->NULL
dll.append(6);
// Insert 7 at the beginning.
// So linked list becomes 7->6->NULL
dll.push(7);
// Insert 1 at the beginning.
// So linked list becomes 1->7->6->NULL
dll.push(1);
// Insert 4 at the end. So linked list
// becomes 1->7->6->4->NULL
dll.append(4);
// Insert 8, after 7. So linked list
// becomes 1->7->8->6->4->NULL
dll.InsertAfter(dll.head.next, 8);
Console.WriteLine("Created DLL is: ");
dll.printlist(dll.head);
}
}
Kết quả in ra là :
Created DLL is:
Traversal in forward direction
1 7 8 6 4
Traversal in reverse direction
4 6 8 7 1
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
Nếu bạn thấy hay và có ích, bạn hoàn toàn có thể tham gia những kênh sau của cafedev để nhận được nhiều hơn nữa :
Chào thân ái và quyết thắng !
Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!
Source: https://final-blade.com
Category: Kiến thức Internet