Trước khi thực hiện bất kỳ thao tác nào đó với danh sách liên kết, trước tiên ta hãy thực hiện thêm phần tử vào trong danh sách liên kết đó trước. Ở trong loạt bài về danh sách liên kết đôi thì việc gọi “phần tử” tương đương với một node có trong danh sách. Sẽ có 3 cách thêm phần tử vào danh sách liên kết đôi đó là: thêm đầu, thêm cuối và thêm vào giữa.

1.Thêm phần tử vào đầu danh sách liên kết đôi

Thêm phần tử vào đầu danh sách nghĩa là ta sẽ khởi tạo phần tử vào đặt chúng vào vị trí đầu tiên của danh sách liên kết đôi.

Ví dụ danh sách liên kết đôi ban đầu của tôi là:

Đặt vấn đề rằng tôi cần thêm Node có chứa dữ liệu X vào đầu danh sách liên kết đôi trên như vậy tôi cần điều chỉnh lại mối liên kết giữa các node (xem hình dưới)

Các bước thực hiện thêm một Node p vào đầu danh sách liên kết đôi.

  • Bước đầu tiên: Kiểm tra điều kiện nếu danh sách rỗng thì đặt pHead = pTail = p;
  • Bước thứ hai: Nếu danh sách không rỗng thì thực hiện điều chỉnh liên kết của node p cần thêm vào đầu danh sách:
    • p ->next = ds.pHead
    • ds.pHead ->prev = p;
    • ds.pHead = p;

Hàm thêm một phần tử hay một Node p mới vào đầu danh sách liên kết đôi bằng C/C++

void ThemDau(DLIST &ds, NODE *p) {
    //neu danh sach rong thi them vao node dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else {
        //dat con tro next cua node can them toi node dau danh sach
        p->next = ds.pHead;
        //dat con tro prev cua node dau ve node p 
        ds.pHead->prev = p;
        //gan lai node dau cua danh sach bang node p
        ds.pHead = p;
    }
}

2.Thêm phần tử vào cuối danh sách liên kết đôi

Việc thêm phần tử hay một node vào cuối danh sách sẽ là việc ngược lại so với thêm vào đầu. Lúc này ta sẽ phải khởi tạo một node và đặt chúng vào vị trí cuối trong danh sách liên kết đôi.

Giả sử tôi cần thêm node có chữa dữ liệu X vào cuối danh sách liên kết đôi ở phần trên tôi sẽ thực hiện thay đổi liên kết (xem hình dưới)

Các bước thực hiện thêm một Node p vào cuối danh sách liên kết đôi.

  • Bước đầu tiên: Kiểm tra điều kiện nếu danh sách rỗng thì đặt pHead = pTail = p;
  • Bước thứ hai: Nếu danh sách không rỗng thì thực hiện điều chỉnh liên kết của node p cần thêm vào đầu danh sách:
    • ds.pTail ->next = p
    • p->prev = ds.pTail;
    • ds.pTail = p;

Hàm thêm một phần tử hay một Node p mới vào cuối danh sách liên kết đôi bằng C/C++

void ThemCuoi (DLIST &ds, NODE*p){
    //kiem tra danh sach rong neu rong thi them vao dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else{
        //dat con tro next cua pTail hien tai vao p la node can them cuoi
        ds.pTail->next = p;
        //dat con tro prev cua node p ve phan tu cuoi danh sach
        p->prev = ds.pTail;
        //thay doi lai phan tu cuoi danh sach
        ds.pTail = p;
    }
}

3.Thêm phần tử vào giữa danh sách liên kết đôi

Việc thêm phần tử vào giữa danh sách liên kết đôi thực chất là thêm Node X vào ngay sau Node q đã có sẵn trong danh sách liên kết.

Hàm thêm giữa cần sự có mặt của cả hai hàm đó là thêm đầu và thêm cuối!

Vẫn sử dụng danh sách liên kết đôi ở trên, nhưng lần này sẽ là thêm node x vào sau node q đã có trong danh sách. (xem hình bên dưới)

Các bước thực hiện thêm một Node p vào sau node q trong sách liên kết đôi.

  • Bước đầu tiên: Kiểm tra điều kiện nếu Node q là node cuối nằm trong danh sách thì ta sẽ gọi hàm chèn cuối để thêm node p vào cuối danh sách
  • Bước thức hai: Nếu node q không phải là node cuối cùng của danh sách thì thực hiện thay đổi liên kết:
    • p ->next = q ->next;
    • q ->next ->prev = p;
    • q ->next = p;
    • p ->prev = q;

Hàm thêm một phần tử hay một Node p mới vào sau node q có trong danh sách liên kết đôi bằng C/C++

void ChenGiua(DLIST &ds, NODE *q, NODE *p) {
    //neu node q la node cuoi cua danh sach thi them node p vao cuoi danh sach
    if (q->next == NULL){
        q->next = p;
        p->prev = q;
        ds.pTail = p;
    }else{//nguoc lai thuc hien them node p sau node q
        p->next = q->next;
        q->next->prev = p;
        q->next = p;
        p->prev = q;
    }
}

3.Chương trình thêm phần tử vào danh sách liên kết đôi

Vì ta chỉ sử dụng chủ yếu là hàm thêm node vào đầu danh sách liên kết đôi và thêm node vào cuối danh sách liên kết đôi vì thế nên tôi sẽ không giải thích quá rõ về hàm void ThemGiua() ở trên! Tôi mong muốn rằng các bạn thực sự hiểu hàm void ThemDau() và void ThemCuoi() để phục vụ cho những bài tiếp theo!

#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;
}

void ThemDau(DLIST &ds, NODE *p) {
    //neu danh sach rong thi them vao node dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else {
        //dat con tro next cua node can them toi node dau danh sach
        p->next = ds.pHead;
        //dat con tro prev cua node dau ve node p 
        ds.pHead->prev = p;
        //gan lai node dau cua danh sach bang node p
        ds.pHead = p;
    }
}
void ThemCuoi (DLIST &ds, NODE*p){
    //kiem tra danh sach rong neu rong thi them vao dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else{
        //dat con tro next cua pTail hien tai vao p la node can them cuoi
        ds.pTail->next = p;
        //dat con tro prev cua node p ve phan tu cuoi danh sach
        p->prev = ds.pTail;
        //thay doi lai phan tu cuoi danh sach
        ds.pTail = 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);
    //tao bien x co gia tri 5
    int x = 5;
    //tao mot node moi va truyen vao du lieu x
    NODE *p = TaoNode(x);
    //goi ham them dau hoac them cuoi, truyen danh sach can them va node p vua tao
    ThemDau(ds,p);
    //ThemCuoi(ds,p);
}

Khi chạy chương trình trên, ta vẫn chưa nhận được kết quả nào hiển thị trên màn hình vì chưa có thao tác thực hiện duyệt danh sách và hiển thị danh sách. Thao tác này sẽ được đề cập ở bài sau. Tuy nhiên, hãy đảm bảo rằng bạn đã biết cách thêm đầu và thêm cuối trong danh sách liên kết đôi để phục vụ cho việc học những bài phía sau!