Chương trình C++ triển khai danh sách liên kết đôi (Doubly Linked List)

Danh sách liên kết đôi (Doubly Linked List) gồm các nút chứa: dữ liệu, con trỏ next (nút tiếp theo), con trỏ prev (nút trước). Chỉ cần con trỏ head (đầu) để truy cập toàn bộ. Nút cuối trỏ next = NULL. Có thể duyệt hai chiều.

Ví dụ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

struct Node* head = NULL;

void insert(int newdata) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if (head != NULL)
        head->prev = newnode;
    head = newnode;
}

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The doubly linked list is: ";
    display();
    return 0;
}

Kết quả

The doubly linked list is: 9 2 7 1 3

Cấu trúc Node

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

Hàm insert() - Thêm vào đầu

Tạo newnode, gán dữ liệu, prev = NULL, next = head. Nếu head không NULL thì head->prev = newnode. Cập nhật head = newnode.

void insert(int newdata) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if (head != NULL)
        head->prev = newnode;
    head = newnode;
}

Hàm display() - Hiển thị

Duyệt từ head theo next cho đến NULL.

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

Hàm main()

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The doubly linked list is: ";
    display();
    return 0;
}