Doubly linked list là gì?

Danh sách liên kết đơn (singly linked list) là một cấu trúc dữ liệu tuyến tính (linear data structure) bao gồm các nút (node) được liên kết với nhau theo một hướng. Mỗi nút chứa một thành viên dữ liệu (data member) chứa thông tin và một con trỏ (pointer) trỏ đến nút tiếp theo. Vấn đề với cấu trúc này là nó chỉ cho phép chúng ta duyệt (traverse) về phía trước, tức là chúng ta không thể duyệt về một nút trước đó nếu được yêu cầu. Do đó danh sách liên kết đôi (doubly linked list) sẽ giải quyết vấn đề này. Danh sách liên kết đôi (doubly linked list) là một phần mở rộng của danh sách liên kết (linked list) cơ bản với chỉ một điểm khác biệt. Danh sách liên kết đôi (doubly linked list)chứa một con trỏ đến nút tiếp theo cũng như nút trước đó. Điều này đảm bảo rằng danh sách có thể được duyệt theo cả hai hướng.

Từ định nghĩa ở trên, chúng ta có thể thấy rằng một nút của danh sách liên kết đôi (doubly linked list) có ba thành viên (member) cơ bản:

• Dữ liệu
• Một con trỏ đến nút tiếp theo
• Một con trỏ đến nút trước đó

Danh sách liên kết đôi (doubly linked list) tốn nhiều hơn về bộ nhớ do bao gồm một con trỏ đến nút trước đó. Tuy nhiên, phần thưởng cho việc này là việc duyệt trở nên hiệu quả hơn nhiều.

Độ phức tạp trong trường hợp xấu nhất (worst-case complexity) cho tìm kiếm, chèn và xóa là O(n). Việc chèn và xóa ở đầu danh sách có thể được thực hiện trong O(1).

Bên dưới là code tạo và duyệt danh sách liên kết đôi trong C++:

// C++ program to illustrate creation
// and traversal of Doubly Linked List
#include 
using namespace std;
 
// Doubly linked list node
class Node {
public:
    int data;
    Node* next;
    Node* prev;
};
 
// Function to push a new element in
// the Doubly Linked List
void push(Node** head_ref, int new_data)
{
    // Allocate node
    Node* new_node = new Node();
 
    // Put in the data
    new_node->data = new_data;
 
    // Make next of new node as
    // head and previous as NULL
    new_node->next = (*head_ref);
    new_node->prev = NULL;
 
    // Change prev of head node to
    // the new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // Move the head to point to
    // the new node
    (*head_ref) = new_node;
}
 
// Function to traverse the Doubly LL
// in the forward & backward direction
void printList(Node* node)
{
    Node* last;
 
    cout data next;
    }
 
    cout data prev;
    }
}
 
// Driver Code
int main()
{
    // Start with the empty list
    Node* head = NULL;
 
    // Insert 6.
    // So linked list becomes 6->NULL
    push(&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);
 
    cout 

Output:

Created DLL is: 
Traversal in forward direction 
 1  7  6 
Traversal in reverse direction 
 6  7  1