Trước khi tìm hiểu về danh sách liên kết đôi, bạn đọc hãy chắc chắn rằng bản thân đã thành thạo với danh sách liên kết đơn. Bởi lẽ, danh sách liên kết đôi cũng gần như có nhiều sự tương đồng với danh sách liên kết đơn. Nắm chắc danh sách liên kết đơn thì việc học danh sách liên kết đôi rất dễ dàng!

1.Danh sách liên kết đôi là gì?

Danh sách liên kết đôi (Doubly Linked List) là một dạng mở rộng của danh sách liên kết đơn. Trong danh sách liên kết đôi cũng bao gồm nhiều các Node (nút) và điều đặc biệt ở danh sách liên kết đôi là các Node liên kết với nhau với 2 con trỏ và theo hai chiều trước – sau. Nghĩa là một Node có thể trỏ đến địa chỉ của Node kế tiếp và cũng có thể trỏ đến địa chỉ của Node phía trước nó.

Qua hình miêu tả danh sách liên kết đôi ở trên ta thấy rằng:

Các node có 2 mối liên kết là trước và sau cũng chính là 2 con trỏ, previous và next.
Node đầu tiên của danh sách có previous = NULL (mũ tên trỏ về phần hình tròn màu đỏ là địa chỉ NULL).

2.Node trong danh sách liên kết đôi

Một Node (hay phần tử) trong danh sách liên kết đôi bao gồm 3 thành phần chính đó là:

Phần data: lưu trữ dữ liệu của node
Previous: Lưu trữ địa chỉ của node (hay phần tử) đứng trước. Trong trường hợp node này là node đầu tiên của danh sách thì sẽ có previous = NULL
Next: Lưu trữ địa chỉ của node (hay phần tử) đừng sau. Trong trường hợp node này là node cuối cùng của danh sách thì sẽ có next = NULL

Cách khai báo một Node trong danh sách liên kết đôi bằng C/C++:

struct Node
{
    //khai bao thanh phan du lieu co kieu int
    int data;
    //khai bao con tro next co kieu Node de chua dia chi phan tu sau
    Node *next;
    //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc
    Node *prev;
};
typedef struct Node NODE;

Trong đó:

int data: là dữ liệu của mỗi Node (ở đây dữ liệu này mang kiểu int, ta hoàn toàn có thể thay đổi thành float hay kiểu SinhVien tùy vào mục đích khác nhau)
Node *next: Là con trỏ mang chính kiểu dữ liệu Node và có chức năng trỏ đến địa chỉ của Node tiếp theo trong danh sách
Node *prev: là con trỏ mảng kiểu Node và có chức năng trỏ đến đại chỉ của node phía trước.
Từ khóa typedef struct để dễ dàng trong việc gọi và sử dụng NODE sau này!

3.Cài đặt danh sách liên kết đôi

Tương tự như danh sách liên kết đơn, các thư viện được dùng để cài đặt danh sách liên kết đôi vẫn là 2 thư viện:

#include <stdio.h>
#include <stdlib.h>

3.1 Khai báo một cấu trúc danh sách liên kết đôi

Tương tự như danh sách liên kết đôi, một cấu trúc của danh sách liên kết đơn ban đầu được khai báo mặc định cũng sẽ có 2 thành phần chính là hai Node là: pHead và pTail

Thành phần pHead sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách: NODE* pHead;
Thành phần pTail lưu địa chỉ phần tử cuối danh sách: NODE* pTail;

Cách khai báo một danh sách liên kết đôi ban đầu mặc định có hai Node là NODE* pHead; và NODE* pTail;

struct doulist{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct doulist DLIST;

Trong đó:

NODE* pHead; là node đầu tiên của danh sách liên kết đôi
NODE* pTail; là node cuối cùng của danh sách liên kết đôi
Từ khóa typedef struct doulist DLIST để viết ngắn gọi lại việc khai bảo một danh sách liên kết đôi

3.2 Hàm khởi tạo danh sách liên kết đôi

Danh sách liên kết đơn hay danh sách liên kết đôi ban đầu khi được khai báo sẽ hoàn toàn không có phần tử nào. Vì thế các thành phần NODE* pHead và NODE* pTail của danh sách được coi là rỗng (NULL). Vì vậy, hàm khởi tạo là thao tác gán giá trị con trỏ quản lý địa chỉ đầu (NODE* pHead) và cuối (NODE *pTail) của danh sách về con trỏ NULL.

Hàm void KhoiTao(DLIST &ds) dưới đây nhận đối số đầu vào là tham chiếu DLIST &ds sau đó thực hiện việc gán địa chỉ phần tử đầu danh sách và địa chỉ cuối danh sách về NULL

void KhoiTao(DLIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

Lưu ý: Hàm này có thể làm tương tự cho danh sách liên kết đơn.

3.3 Hàm kiểm tra rỗng trong danh sách liên kết đôi

Hàm kiểm tra rỗng thực hiện chức năng kiểm tra trạng thái của danh sách liên kết đôi đó xem danh sách đó có đang rỗng hay không? Việc kiểm tra rỗng này để thuận tiện hơn cho việc lấy ra phần tử trong danh sách hoặc thêm mới một phần tử vào danh sách.

int KiemTraRong(DLIST ds){
    //neu phan tu dau danh sach NULL
    if (ds.pHead == NULL){
        //tra ve 1 la co NULL
        return 1;
    }
    //truong hop nguoc lai tra ve khong null
    return 0;
}

3.4 Hàm tạo Node trong danh sách liên kết đơn

Giống như danh sách liên kết đơn, để thực hiện được việc thêm một node vào danh sách liên kết đôi ta cần có một hàm tạo node trước. Tuy nhiên điểm khác biệt của một node danh sách liên kết đôi đó chính là việc một node sẽ có 3 thành phần đó là: thành phần data, Next, Previous vì thế để tạo ra một node mới ta cần khai báo đủ 3 thành phần trên

Hàm NODE* TaoNode(int x) dưới đây có đầu vào là int x hàm này thực hiện việc tạo ra một NODE mới trong danh sách liên kết đơn với thành phần data = x và ban đầu khi khởi tạo node ta sẽ đặt thành phần next, previous của node đó đều trỏ đến NULL.

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho va ket thuc viec tao node
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //gan con tro prev = NULL
    p->prev = NULL;
    //tra ve node p da tao
    return p;
}

4.Chương trình cài đặt danh sách liên kết đôi hoàn chỉnh

Chương trình dưới đây cài đặt đầy đủ các hàm trên để khởi tạo một danh sách liên kết đôi hoàn chỉnh.

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    //khai bao thanh phan du lieu co kieu int
    int data;
    //khai bao con tro next co kieu Node de chua dia chi phan tu sau
    Node *next;
    //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc
    Node *prev;
};
typedef struct Node NODE;

struct doulist{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct doulist DLIST;

void KhoiTao(DLIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

int KiemTraRong(DLIST ds){
    //neu phan tu dau danh sach NULL
    if (ds.pHead == NULL){
        //tra ve 1 la co NULL
        return 1;
    }
    //truong hop nguoc lai tra ve khong null
    return 0;
}

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho va ket thuc viec tao node
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //gan con tro prev = NULL
    p->prev = NULL;
    //tra ve node p da tao
    return p;
}

int main(){
    //khai bao mot danh sach lien ket doi
    DLIST ds;
    //khoi tao danh sach
    KhoiTao(ds);
    //kiem danh sach co rong hay khong
    KiemTraRong(ds);
}

Chương trình trên đã thực hiện được bước đầu trong việc cài đặt danh sách liên kết đôi bằng C/C++, tuy nhiên ta vẫn cần thao tác với danh sách liên kết đôi ở trong những bài sau nữa. Vì thế, hay ghi nhớ các hàm: TaoNode(), KhoiTao(), KiemTraRong() và các struct list cũng như struct Node.

Nếu như bạn đã từng học danh sách liên kết đơn, thì có thể dễ dàng nhận thấy rằng danh sách liên kết đôi có các hàm gần như là tương tự danh sách liên kết đơn. Chúng chỉ co sự khác biệt chính là ở thành phần của node và hàm tạo node trong mỗi danh sách.

Cài đặt danh sách liên kết đôi C/C++ – Doubly Linked List