Thêm phần từ vào giữa danh sách liên kết đơn thực chất là việc ta thêm một Node P vào sau một Node Q của danh sách liên kết đơn đó!

1.Cách thêm một phần tử vào sau Node Q có trong danh sách liên kết đơn

Giả sử danh sách liên kết đơn ban đầu của tôi được biểu diễn như hình dưới:

Một vấn đề đặt ra rằng, tôi cần thêm một Node P vào sau Node Q hiện có trong danh sách:

Để thực hiện được việc này, tôi cần thực hiện hai bước:

• Bước đầu tiên: Đặt con trỏ next của Node P bằng con trỏ next của Node Q: p->next = q->next;
• Bước thứ hai: Đặt con trỏ next của Node Q bằng Node P: q->next = p

Xem hình bên dưới để hiểu rõ hơn hai bước trên:

Chú ý:

Trong trường hợp không có Node Q trong danh sách (nghĩa là Q = NULL) thì ta gọi hàm ChenDau() để thêm Node P vào đầu danh sách. Trường hợp ngược lại nếu Node Q là phần tử cuối cùng của danh sách (nghĩa là Q = pTail) thì ta gọi hàm ChenCuoi() để thêm Node P vào cuối danh sách.

2.Hàm chèn một phần tử vào sau Node Q trong danh sách liên kết đơn

Hàm void ChenGiua(LIST &ds, NODE *q, NODE *p) dưới đây nhận LIST &ds là danh sách cần được chèn giữa tiếp theo là tham số NODE *q là phần tử cần được chèn sau và tham số NODE *p là phần tử sẽ chèn sau NODE *q

void ChenGiua(LIST &ds, NODE *q, NODE *p){
    //neu ton tai node q thi thuc hien chen giua
    if (q!=NULL){
        //gan con tro next node p bang con tro next node q
        p->next=q->next;
        //gan con tro next node q bang node p
        q->next=p;
        //neu q la phan tu cuoi cung thi chen node p vao cuoi
        if (q==ds.pTail){
            ds.pTail=p;
        }
    }
    //nguoc lai khong ton tai node q thi chen node p vao dau
    else{
        //goi ham chen dau
        ChenDau(ds, p);
    }
}

3.Chương trình hoàn chỉnh chèn phần tử vào sau Node Q có trong danh sách liên kết đơn

#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
    Node *next;
};
typedef struct Node NODE;

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

void KhoiTao(LIST &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(LIST 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
    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;
    //tra ve node p da tao
    return p;
}
void ChenDau(LIST &ds, NODE *p) {
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL){
        //chen dau va cuoi deu bang node p
        ds.pHead = p;
        ds.pTail = p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro next cua node p bang phan tu dang la dau tien cua danh sach
        p->next = ds.pHead;
        //gan pHead bang node p
        ds.pHead = p;
    }
}
void ChenCuoi (LIST &ds, NODE *p){
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL) {
        //chen dau va cuoi deu bang node p
        ds.pHead=p;
        ds.pTail=p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro cua phan tu cuoi trong danh sach bang node p
        ds.pTail->next=p;
        //gan pTail bang node p
        ds.pTail=p;
    }
}
void ChenGiua(LIST &ds, NODE *q, NODE *p){
    //neu ton tai node q thi thuc hien chen giua
    if (q!=NULL){
        //gan con tro next node p bang con tro next node q
        p->next=q->next;
        //gan con tro next node q bang node p
        q->next=p;
        //neu q la phan tu cuoi cung thi chen node p vao cuoi
        if (q==ds.pTail){
            ds.pTail=p;
        }
    }
    //nguoc lai khong ton tai node q thi chen node p vao dau
    else{
        //goi ham chen dau
        ChenDau(ds, p);
    }

}
int main(){
    //khai bao mot danh sach
    LIST ds;
    //khoi tao danh sach
    KhoiTao(ds);
    //khai bao du lieu cua cac node
    int x = 10;
    int y = 20;
    //tao node p co du lieu x
    NODE *p = new NODE;
    p = TaoNode(x);
    //tao node q can chen sau co du lieu y
    NODE *q = new NODE;
    q = TaoNode(y);
    //them node p vao dau danh sach
    ChenGiua(ds,q,p);
}

Chú ý:

• Hàm ChenGiua() sẽ cần sử dụng cả hài hàm ChenDau() và ChenCuoi()
• Trong thực tế người ta thưởng chỉ sử dụng chèn đầu hoặc chèn cuối là chủ yếu. Rất ít khi sử dụng chèn giữa. Bạn đọc có thể coi bài viết này là tham khảo!