Việc xóa phần tử trong danh sách liên kết đôi để thực hiện loại một phần tử trong danh sách đó. Trong danh sách liên kết đôi ta có thể thực hiện 4 thao tác xóa phần tử đó là:

  • Xóa phần tử đầu danh sách liên kết đôi
  • Xóa phần tử cuối danh sách liên kết đôi
  • Xóa phần tử theo khóa K

1.Xóa phần tử đầu danh sách liên kết đôi

Với yêu cầu xóa phần tử ở đầu danh sách liên kết đôi ta có:

  • Đầu vào: Danh sách cần xóa cuối
  • Đầu ra: Danh sách sau khi đã xóa nút đầu.

Các bước để thực hiện xóa phần tử đầu tiên trong danh sách liên kết đôi:

  • B1:Tạo NODE *p và gán p = ds.pHead
  • B2: Thực hiện gán:
    • ds.pHead = ds.pHead->next;
    • ds.pHead->prev = NULL;
  • B3: if (ds.pHead==NULL) //danh sách rỗng
    • Đặt lại ds.pTail = NULL;
  • B4: Thực hiện xóa Node p ở bước 1: delete p;

Hàm xóa đầu trong danh sách liên kết đôi:

void XoaDau(DLIST &ds){
    //gan p bang phan tu dau danh sach
    NODE *p = ds.pHead;
    //thuc hien gan lai phan tu dau danh sach
    ds.pHead = ds.pHead->next;
    ds.pHead->prev = NULL;
    //neu khong ton tai phan tu dau danh sach
    if (ds.pHead==NULL){
        ds.pTail = NULL;
    }
    //thay doi con tro next ve NULL
    p->next = NULL;
    //xoa node p duoc gan bang phan tu dau danh sach
    delete p;
}

2.Xóa phần tử cuối danh sách liên kết đôi

Yêu cầu xóa phần tử xóa phần tử cuối cùng trong danh sách liên kết đôi:

  • Đầu vào: Danh sách liên kết đôi cần xóa đầu
  • Đầu ra: Danh sách sau khi đã xóa nút cuối.

Để thực hiện được các bước xóa cuối trong danh sách liên kết đôi, ta cần thực hiện các bước sau:

  • B1: Tạo NODE *p và gán p = ds.pTail
  • B2: Thực hiện gán
    • ds.pTail = ds.pTail->prev;
    • ds.pTail->next = NULL;
  • B3: if (ds.pTail==NULL) //danh sách rỗng
    • Đặt lại ds.pHead = NULL;
  • B4: Thực hiện xóa node p ở bước 1: delete p;

Hàm xóa phần tử cuối danh sách liên kết đôi:

void XoaCuoi (DLIST &ds){
    //tao node p va gan bang phan tu cuoi danh sach
    NODE *p = ds.pTail;
    //thuc hien gan lai phan tu cuoi danh sach
    ds.pTail = ds.pTail->prev;
    ds.pTail->next = NULL;
    //kiem tra phan tu cuoi neu rong
    if (ds.pTail==NULL){
        ds.pHead = NULL;
    }
    //thay doi con tro prev cua node p ve NULL
    p->prev = NULL;
    //xoa p duoc gan bang phan tu cuoi danh sach
    delete p;
}

3.Xóa phần tử có khóa K trong danh sách liên kết đôi

Với công việc xóa theo khóa K, ta có thể coi K là dữ liệu cần xóa đi trong danh sách liên kết đôi đó. Việc xóa theo khóa K ta cần sử dụng lại hàm void TimKiem() ở bài 4 để tìm phần tử có khóa K sau đó mới thực hiện xóa đi phần tử đó!

Với yêu cầu xóa theo khóa K ta có:

  • Đầu vào: Danh sách liên kết đôi cần xóa và khóa k (hay dữ liệu cần xóa)
  • Đầu ra: Danh sách sau khi đã loại bỏ phần tử có khóa K

Các bước thực hiện xóa phần tử có khóa K trong danh sách liên kết đôi:

  • B1: Tạo NODE *p và gán p = TimKiem(ds,k); (ds và K là đầu vào cần tìm kiếm theo khóa K)
  • B2: Kiểm tra if p!=NULL (nếu đã tìm thấy phần tử) thì thực hiện:
    • Kiểm tra if p->prev == NULL thì thực hiện xóa nút ở đầu danh sách
    • else if p->next ==NULL thì thực hiện xóa nút cuối danh sách
  • B3: Thực hiện gán
    • p->prev->next = p->next;
    • p->next->prev = p->prev;
  • B4: Thực hiện xóa node theo khóa k ở bước 1: delete p;

Hàm xóa phần tử theo khóa K trong danh sách liên kết đôi này có sử dụng hàm void TimKiem() vì thế bạn đọc hãy quay lại bài 4 để xem lại hàm void TimKiem();

void XoaTheoKhoaK(DLIST &ds, int k){
    //tim kiem theo du lieu x va gan vao node p
    NODE *p = TimKiem(ds, k);
    //neu tim thay ket qua
    if(p != NULL){
        //neu p->prev == NULL thuc hien xoa dau
        if (p->prev==NULL){
            XoaDau(ds);
            return;
        }
        //neu p->next == NULL thuc hien xoa cuoi
        if (p->next==NULL){
            XoaCuoi(ds);
            return;
        }
        //thay doi lai lien ket cua phan tu co khoa K can xoa
        p->prev->next = p->next;
        p->next->prev = p->prev;
        //gan con tro prev va next cua phan tu co khoa K can xoa ve null
        p->prev = NULL; 
        p->next = NULL;
        //xoa node p co phan tu la khoa k
        delete p;
    }
}

4.Chương trình xóa phần tử trong danh sách liên kết đôi hoàn chỉnh

Để thực hiện việc xóa đầu, xóa cuối hay xóa theo khóa K của một danh sách liên kết đôi. Trước tiên tôi sẽ cần nhập một vài dữ liệu vào trước sau đó mới thực hiện gọi hàm xóa!

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

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 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;
    }
}
void Nhap(DLIST &ds, int n){
    //duyet N lan
    for(int i = 0; i < n; i++){
        //nhap du lieu la so nguyen int x
        int x;
        printf("Nhap vao so %d: ",i);
        scanf("%d",&x);
        //tao node p
        NODE *p = new NODE;
        //dua du lieu vua nhap vao node p
        p = TaoNode(x);
        //dua node p vao ham them cuoi va truyen vao node p vua tao
        ThemCuoi(ds,p);
    }
}
void Xuat(DLIST ds){
    //khoi tao mot node
    NODE *p = new NODE;
    //duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
    for(p = ds.pHead; p!= NULL; p=p->next){
        //hien thi du lieu cua tung node
        printf("%d\n",p->data);
    }
}
NODE* TimKiem(DLIST ds, int x){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau danh sach
    p = ds.pHead;
    //su dung vong lap
    while ((p!=NULL) && (p->data!=x)){
        p=p->next;
    }
    //tra ve ket qua, neu NULL thi khong tim thay
    return p;
}
void XoaDau(DLIST &ds){
    //gan p bang phan tu dau danh sach
    NODE *p = ds.pHead;
    //thuc hien gan lai phan tu dau danh sach
    ds.pHead = ds.pHead->next;
    ds.pHead->prev = NULL;
    //neu khong ton tai phan tu dau danh sach
    if (ds.pHead==NULL){
        ds.pTail = NULL;
    }
    //thay doi con tro next ve NULL
    p->next = NULL;
    //xoa node p duoc gan bang phan tu dau danh sach
    delete p;
}
void XoaCuoi (DLIST &ds){
    //tao node p va gan bang phan tu cuoi danh sach
    NODE *p = ds.pTail;
    //thuc hien gan lai phan tu cuoi danh sach
    ds.pTail = ds.pTail->prev;
    ds.pTail->next = NULL;
    //kiem tra phan tu cuoi neu rong
    if (ds.pTail==NULL){
        ds.pHead = NULL;
    }
    //thay doi con tro prev cua node p ve NULL
    p->prev = NULL;
    //xoa p duoc gan bang phan tu cuoi danh sach
    delete p;
}
void XoaTheoKhoaK(DLIST &ds, int k){
    //tim kiem theo du lieu x va gan vao node p
    NODE *p = TimKiem(ds, k);
    //neu tim thay ket qua
    if(p != NULL){
        //neu p->prev == NULL thuc hien xoa dau
        if (p->prev==NULL){
            XoaDau(ds);
            return;
        }
        //neu p->next == NULL thuc hien xoa cuoi
        if (p->next==NULL){
            XoaCuoi(ds);
            return;
        }
        //thay doi lai lien ket cua phan tu co khoa K can xoa
        p->prev->next = p->next;
        p->next->prev = p->prev;
        //gan con tro prev va next cua phan tu co khoa K can xoa ve null
        p->prev = NULL; 
        p->next = NULL;
        //xoa node p co phan tu la khoa k
        delete p;
    }
}
int main(){
    //khai bao mot danh sach lien ket doi
    DLIST ds;
    //nhap n phan tu 
    int n;
    printf("NHAP N: ");
    scanf("%d",&n);
    //khoi tao danh sach
    KhoiTao(ds);
    //goi ham nhap tryuyen vao danh sach va N phan tu
    Nhap(ds,n);
    //goi ham xuat cac du lieu co trong danh sach
    printf("DANH SACH VUA NHAP\n");
    Xuat(ds);
    //Xoa dau va xoa cuoi
    XoaDau(ds);
    XoaCuoi(ds);
    //Xoa theo khoa K
    int k;
    printf("\nNHAP K: "); 
    scanf("%d",&k);
    XoaTheoKhoaK(ds,k);
    printf("\nDANH SACH SAU KHI XOA DAU, XOA CUOI VA XOA THEO KHOA K\n");
    Xuat(ds);
}
NHAP N: 5

Nhap vao so 0: 111

Nhap vao so 1: 112

Nhap vao so 2: 113

Nhap vao so 3: 114

Nhap vao so 4: 115

DANH SACH VUA NHAP

111

112

113

114

115

NHAP K: 113

DANH SACH SAU KHI XOA DAU, XOA CUOI VA XOA THEO KHOA K

112

114

Danh sách ban đầu được nhập vào chương trình là: 111,112,113,114,115

Danh sách sau khi gọi hàm xóa đầu và xóa cuối là:112,113,114

Danh sách sau khi gọi hàm xóa theo khóa K với K = 113 là: 112,114