Chào ace, bài này chúng ta sẽ tìm hiểu về Danh sách liên kết kép – Doubly Linked List trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các 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:
– 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 dữ 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ường) sẽ là những thành phần tạo nên một Doubly Linked List.
Dưới đây là đoạn code cài đặt một node của DLL bằng ngôn ngữ 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
Nội dung chính
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, chúng ta có thể thực hiện 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 quả hơn vì chúng ta có được con trỏ trỏ đến node cần xóa
3. Chúng ta có thể chèn thêm một node mới vào phía trước một node cụ thể nào đó, một cách nhanh chóng. Trong Linked List thông thường, để xóa một node, 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 khi chúng ta sẽ phải duyệt cả danh sách. Trong DLL, chúng ta 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 yêu cầu thêm không gian dành cho một con trỏ previous. Tuy nhiên ta vẫn có thể cài đặt DLL với một con trỏ duy nhất, vẫn có cách để làm được điều đó.
2. Tất cả các thao tác đều yêu cầu phải duy trì thêm một con trỏ là con trỏ previous. Ví dụ, khi thực hiện chèn thêm node mới vào trong DLL, chúng ta sẽ phải chỉnh sửa các con trỏ previous cùng với các con trỏ next. Ví dụ, trong các hàm chèn thêm node mới vào các vị trí khác nhau trên DLL, 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 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 cụ thể 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 cụ thể 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à chúng ta chèn thêm một phần tử 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ó chức nă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, bởi vì hàm push phải thay đổi 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ẽ thực hiện 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ổ sung duy nhất là thay đổi 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, 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 cụ thể 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 cụ thể 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 hiện 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
/* 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 cụ thể trong danh sách liên kết đơn (singly linked list). Cần thêm 2 bước bổ sung để thay đổi con trỏ prev của new_node và thay đổi 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 cuối cùng của DLL được cho. Ví dụ, nếu DLL được cho có dạng 5 -> 10 -> 15 -> 20 -> 25 và chúng ta chèn thêm một phần tử 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 bởi con trỏ head của chúng, vậy nên chúng ta sẽ phải duyệt từ đầu tới cuối danh sách và sau đó thay đổi con trỏ next của node cuối cùng để 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ẽ thực hiện 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 cuối cùng của DLL, vì vậy 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 cuối cùng của DLL
6. Thay đổi con trỏ next của node cuối cùng của DLL để cho con trỏ next này trỏ đến new_node
7. Làm cho node từng là cuối cùng 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à cuối cùng 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 cụ thể trong singly linked list – danh sách liên kết đơn thông thường. Ở đây, chúng ta cần thêm 1 bước bổ sung để thay đổi 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, chúng ta sẽ có con trỏ trỏ đến node cụ thể này là next_node, và phần dữ 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, chúng ta sẽ return luôn bởi vì không thể chèn thêm bất cứ 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 cài đặt bằng ngôn ngữ 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 <stdio.h>
#include <stdlib.h>
// 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, chúng ta sẽ cùng tham khảo một đoạn chương trình hoàn chỉnh được viết bằng nhiều ngôn ngữ lập trình khác nhau, để kiểm tra các hàm chúng ta đã tìm hiểu ở 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 <stdio.h>
#include <stdlib.h>
// 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 <bits/stdc++.h>
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<<" "<<node->data<<" ";
last = node;
node = node->next;
}
cout<<"\nTraversal in reverse direction \n";
while (last != NULL)
{
cout<<" "<<last->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 1Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các 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!
 và giải thuật){kind=link}