Cài đặt danh sách liên kết đôi trong C/C++

Giới thiệu

Trong bài viết trước đây, chúng ta đã tìm hiểu về cách cài đặt danh sách liên kết đơn và các kiến thức cơ bản liên quan đến danh sách liên kết. Trong bài viết này, mình sẽ hướng dẫn bạn cách cài đặt danh sách liên kết đôi. Danh sách liên kết đôi cho phép sự liên kết 2 chiều giữa 2 phần tử liền kề trong khi danh sách liên kết đơn chỉ có liên kết 1 chiều.

Lý thuyết về danh sách liên kết đôi

Một Node trong danh sách liên kết đôi sẽ có cấu trúc như sau:

| | | | | PREV | DATA | NEXT | | | | |

Dưới đây là hình minh họa cho sự khác biệt giữa danh sách liên kết đơn và danh sách liên kết đôi:

Cài đặt danh sách liên kết đôi

Khai báo và khởi tạo

Khác với danh sách liên kết đơn, trong danh sách liên kết đôi chúng ta cần có một con trỏ prev để liên kết với Node trước đó. Data vẫn có kiểu int để đơn giản và dễ hiểu.

Sau khi khai báo, chúng ta sẽ khởi tạo Node đầu tiên của danh sách liên kết đôi.

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
struct Node* head; // Khởi tạo Node head global của danh sách liên kết đôi.

Tạo mới một Node

Thay vì chỉ đặt next = NULL và gán giá trị cho Node mới, chúng ta cũng phải đặt prev = NULL.

struct Node* GetNewNode(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Thêm Node

Thêm vào đầu

• Nếu head = NULL, ta sẽ đặt cả head và tail = newNode.
• Nếu head != NULL, ta sẽ cập nhật lại head mới là newNode. Trước khi cho newNode trở thành head mới, ta cần tạo liên kết giữa head hiện tại với newNode.

  void InsertAtHead(int x) {
    struct Node* newNode = GetNewNode(x);
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
  }

Ý tưởng thêm Node vào cuối cũng tương tự như thêm vào đầu trong danh sách liên kết đơn.

Thêm vào cuối

• Nếu head = NULL, newNode sẽ là head và tail cũng sẽ là newNode.
• Nếu head != NULL, cập nhật lại tail mới là newNode. Trước khi cho newNode trở thành tail mới, ta cần tạo liên kết giữa tail hiện tại với newNode.

  void InsertAtTail(int x) {
    struct Node* newNode = GetNewNode(x);
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
  }

Xóa Node

Xóa ở đầu

• Nếu head = NULL, không có gì để xóa.
• Nếu head != NULL, cho head mới là phần tử tiếp theo và cập nhật prev của nó = NULL (ngắt liên kết với phần tử head cũ).

  void DeleteAtHead() {
    if(head == NULL) {
        return;
    }
    head = head->next;
    head->prev = NULL;
  }

Xóa ở cuối

• Nếu head = NULL, không có gì để xóa.
• Nếu head != NULL, cho tail mới là phần tử trước nó và cập nhật next của nó = NULL (ngắt liên kết với phần tử tail cũ).

  void DeleteAtTail() {
    if(head == NULL) {
        return;
    }
    tail = tail->prev;
    tail->next = NULL;
  }

Duyệt danh sách liên kết

Duyệt từ đầu tới cuối

Ta sẽ duyệt từ Node head cho tới khi gặp Node NULL bằng cách sử dụng con trỏ next.

void Print() {
    struct Node* temp = head;
    printf("Duyệt từ đầu: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Duyệt từ cuối về đầu

Lần này, ta sẽ duyệt từ Node tail cho tới khi gặp Node NULL bằng cách sử dụng con trỏ prev.

void ReversePrint() {
    struct Node* temp = tail;
    if(temp == NULL)
        return;
    printf("Duyệt từ cuối: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

Full code danh sách liên kết đôi

/* Doubly Linked List implementation */
#include
#include

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
struct Node *head, *tail; // Khởi tạo Node head global của danh sách liên kết đôi.

// Tạo một Node mới và trả về con trỏ tới nó.
struct Node* GetNewNode(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Thêm một Node vào đầu danh sách liên kết đôi
void InsertAtHead(int x) {
    struct Node* newNode = GetNewNode(x);
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}

// Thêm một Node vào cuối danh sách liên kết đôi
void InsertAtTail(int x) {
    struct Node* newNode = GetNewNode(x);
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
}

// Xóa Node ở đầu danh sách liên kết đôi
void DeleteAtHead() {
    if(head == NULL) {
        return;
    }
    head = head->next;
    head->prev = NULL;
}

// Xóa Node ở cuối danh sách liên kết đôi
void DeleteAtTail() {
    if(head == NULL) {
        return;
    }
    tail = tail->prev;
    tail->next = NULL;
}

// In ra tất cả các phần tử trong danh sách liên kết đôi theo thứ tự từ đầu tới cuối
void Print() {
    struct Node* temp = head;
    printf("Duyệt từ đầu: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// In ra tất cả các phần tử trong danh sách liên kết đôi theo thứ tự từ cuối về đầu
void ReversePrint() {
    struct Node* temp = tail;
    if(temp == NULL)
        return;
    printf("Duyệt từ cuối: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

int main() {
    /*Driver code to test the implementation*/
    head = NULL; // danh sách rỗng. đặt head = NULL.

    // Thêm Node và in ra danh sách liên kết đôi theo cả hai hướng đầu và cuối.
    InsertAtTail(2);
    Print();
    ReversePrint();
    InsertAtTail(4);
    Print();
    ReversePrint();
    InsertAtHead(6);
    Print();
    ReversePrint();
    InsertAtTail(8);
    Print();
    ReversePrint();
    DeleteAtHead();
    Print();
    ReversePrint();
    DeleteAtTail();
    Print();
    ReversePrint();

    return 0;
}

Kết quả khi chạy:

Duyệt từ đầu: 2
Duyệt từ cuối: 2
Duyệt từ đầu: 2 4
Duyệt từ cuối: 4 2
Duyệt từ đầu: 6 2 4
Duyệt từ cuối: 4 2 6
Duyệt từ đầu: 6 2 4 8
Duyệt từ cuối: 8 4 2 6
Duyệt từ đầu: 2 4 8
Duyệt từ cuối: 8 4 2
Duyệt từ đầu: 2 4
Duyệt từ cuối: 4 2