Danh sách liên kết vòng một chiều chỉ có con trỏ next trỏ đến nút kế tiếp, với nút cuối cùng trỏ ngược về nút đầu để tạo thành vòng khép kín. Trong khi đó, danh sách hai chiều cung cấp khả năng di chuyển linh hoạt hơn nhờ mỗi nút chứa hai con trỏ: next (trỏ tới nút sau) và prev (trỏ tới nút trước). Điều này cho phép duyệt theo cả hai hướng, tối ưu hóa các thao tác chèn/xóa và phù hợp với các ứng dụng cần truy xuất ngược như chức năng undo.

Cấu trúc cơ bản của nút trong danh sách hai chiều:

typedef struct _dual_node {
    int data;
    struct _dual_node* forward;
    struct _dual_node* backward;
} DualNode, DualList;

Hàm hỗ trợ thao tác

Chèn một nút mới vào giữa hai nút đã có:

static void linkNodes(DualNode* inserted, DualNode* before, DualNode* after) {
    after->backward = inserted;
    inserted->forward = after;
    inserted->backward = before;
    before->forward = inserted;
}

Xóa một nút bằng cách nối trực tiếp nút trước và sau nó:

static void unlinkNodes(DualNode* before, DualNode* after) {
    after->backward = before;
    before->forward = after;
}

Khai báo giao diện

void initDualList(DualList* sentinel);
void prepend(DualList* sentinel, int value);
void append(DualList* sentinel, int value);
void removeNode(DualList* sentinel, int target);
void destroyList(DualList* sentinel);
void displayList(const DualList* sentinel);

Triển khai chức năng

Khởi tạo danh sách

void initDualList(DualList* sentinel) {
    sentinel->data = 0; // dùng làm bộ đếm số phần tử
    sentinel->forward = sentinel->backward = sentinel;
}

Chèn phần tử

Chèn vào đầu danh sách:

void prepend(DualList* sentinel, int value) {
    DualNode* fresh = malloc(sizeof(DualNode));
    fresh->data = value;
    linkNodes(fresh, sentinel, sentinel->forward);
    ++sentinel->data;
}

Chèn vào cuối danh sách:

void append(DualList* sentinel, int value) {
    DualNode* fresh = malloc(sizeof(DualNode));
    fresh->data = value;
    linkNodes(fresh, sentinel->backward, sentinel);
    ++sentinel->data;
}

Xóa phần tử

Xóa nút đầu tiên có giá trị khớp:

void removeNode(DualList* sentinel, int target) {
    DualNode* current = sentinel->forward;
    while (current != sentinel && current->data != target) {
        current = current->forward;
    }
    if (current != sentinel) {
        unlinkNodes(current->backward, current->forward);
        free(current);
        --sentinel->data;
    } else {
        printf("Không tìm thấy giá trị %d\n", target);
    }
}

Xóa toàn bộ danh sách:

void destroyList(DualList* sentinel) {
    DualNode* walker = sentinel->forward;
    while (walker != sentinel) {
        DualNode* to_free = walker;
        walker = walker->forward;
        unlinkNodes(to_free->backward, to_free->forward);
        free(to_free);
        --sentinel->data;
    }
}

Hiển thị nội dung

void displayList(const DualList* sentinel) {
    DualNode* cursor = sentinel->forward;
    while (cursor != sentinel) {
        printf("\t%d", cursor->data);
        cursor = cursor->forward;
    }
    printf("\n");
}