Trong danh sách liên kết đơn, để xóa một phần tử (hay một Node) trong danh sách sẽ có 4 trường hợp sảy rả ra:

Xóa phần tử ở đầu danh sách liên kết đơn
Xóa phần tử ở cuối danh sách liên kết đơn
Xóa phần tử có khóa k trong danh sách liên kết đơn
Hủy toàn bộ danh sách liên kết đơn

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

Danh sách đơn ban đầu của tôi bao gồm các phần tử (hay các node) bên dưới:

Để thực hiện xóa phần tử đầu tiên của danh sách trên ta chỉ cần thực hiện 3 bước:

Bước thứ nhất: Tạo một node p và gán bằng pHead hiện tại của danh sách: p = ds.pHead
Bước thứ hai: Đặt lại phần tử pHead của danh sách bằng phần tử kế sau pHead hiện tại của danh sách: ds.pHead = ds.pHead->next
Bước thứ ba: Gán node p được gán bằng pHead ở bước thứ nhất trỏ đến NULL: p->next = NULLL
Bước thứ tư: Xóa đi node p được gán bằng pHead ở bước thứ nhất: delete p

Để hiểu rõ hơn các bước trên, hãy xem hình dưới đây:

Hàm void XoaDau(LIST &ds) dưới đây thực hiện xóa phần tử (hay node) đầu tiên trong danh sách:

void XoaDau(LIST &ds){
    //tao node p
    NODE *p = new NODE;
    //gan p bang node pHead dau tien cua danh sach 
    p = ds.pHead;
    //thay doi lai pHead cua danh sach
    ds.pHead = ds.pHead->next;
    //gan node p ban dau tro den NULL
    p->next = NULL;
    //xoa node p
    delete p;
}

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

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

Bước đầu tiên: Tạo một node k và thực hiện duyệt toàn bộ phần tử có trong danh sách liên kết đơn
Bước thứ hai: Kiểm tra duyệt, nếu thực hiện duyệt đến phần tử cuối của danh sách nghĩa là k == ds.pTail thì thực hiện xóa phần tử đó: delete ds.pTail;
Bước thứ ba: Trỏ phần tử đứng trước pTail bằng NULL: k->next = NULL;
Bước thứ tư: Thay đổi lại pTail của danh sách bằng node k

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

Hàm void XoaCuoi(LIST &ds) dưới đây thực hiện xóa phần tử (hay node) đầu tiên trong danh sách:

void XoaCuoi(LIST &ds)
{
    //duyet cac phan tu co trong danh sach
    for(NODE *k = ds.pHead; k != NULL; k = k ->next)
    {
        //neu duyet den phan tu pTail cuoi trong danh sach
        if(k->next == ds.pTail)
        {
            //xoa phan tu cuoi
            delete ds.pTail;
            //tro phan tu truoc phan tu cuoi ve NULL
            k->next = NULL;
            //thay doi lai phan tu cuoi pTail cua danh sach
            ds.pTail = k;
        }
    }
}

3.Xóa phần tử có khóa k trong danh sách liên kết đơn

Ở phần 1 và phần 2 ta đã biết cách xóa đi phần tử đầu (pHead) hoặc phần tử cuối (pTail) trong danh sách liên kết đơn. Trong một số trường hợp ta sẽ cần xóa đi một node có một khóa bất kỳ trong danh sách (khóa ở đây ta có thể hiểu là một data nào đó của một node trong danh sách liên kết đơn)

Để xóa một phần tử (hay một node) theo khóa k trong danh sách liên kết đơn, ta sẽ cần thực hiện 3 bước sau:

Bước đầu tiên: Nhập một khóa k (hay có thể hiểu là data) vào để kiếm tra, tạo một node p và một node k: NODE *p, *k;
Bước thứ hai: Duyệt toàn bộ danh sách từ đầu đến cuối danh sách thông qua node k
Bước thứ ba: Nếu khóa k (hay data) nhập vào ở bước 1 trùng với data của node đang duyệt thì gán: p->next = k->next có thể hiểu bước này là gán con trỏ next của node trước khóa k bằng con trỏ next của khóa k. Sau đó thực hiện xóa đi node k: delete k;
Bước thứ tư: Gán lại node p bằng node k: p = k;

Chú ý:

Nếu k (hay data) nhập vào bằng với ds.pHead->data thì gọi hàm xóa đầu void XoaDau(ds), nếu k (hay data) nhập vào bằng với ds.pTail->data thì gọi hàm xóa cuối void XoaCuoi(ds)

Xem hình dưới đây để hiểu rõ hơn các bước trên:

Hàm void XoaKhoaK(LIST &ds, int k) dưới đây thực hiện xóa phần tử có khóa k trong danh sách liên kết đơn. Hàm này cần truyền tham chiếu vào LIST &ds và int data chính là dữ liệu nhập vào để xóa đi node có khóa k trùng với data đó:

void XoaKhoaK(LIST &ds, int data){
    //tao node p de luu tru phan tu truoc node k can xoa
    NODE *p = new NODE;
    //neu data dau vao bang voi pHead->data thi xoa dau
    if(ds.pHead->data == data){
        //goi ham xoa dau
        XoaDau(ds);
        //ket thuc ham
        return;
    }
    //neu data bang voi pTail->data thi xoa cuoi
    if(ds.pTail->data == data){
        //goi ham xoa cuoi
        XoaCuoi(ds);
        //ket thuc ham
        return;
    }
    //duyet qua cac phan tu co trong danh sach
    for(NODE *k = ds.pHead; k != NULL; k=k->next){
        //neu tim thay data trung voi k->data dang duyet
        if(k->data == data){
            //gan con tro next cua node p bang con tro next cua node k
            p->next = k->next;
            //xoa di node k
            delete k;
            //ket thuc ham
            return;
        }
        //gan node p bang node k de node p luon la node dung truoc node k
        p = k;
    }
}

4.Hủy toàn bộ danh sách liên kết đơn

Với 3 cách xóa ở trên, ta chỉ xóa đi một phần tử trong một lần chạy chương trình. Giả sử ta không cần sử dụng danh sách liên kết đơn nữa và ta cần xóa đi tất cả các node trong danh sách ta sẽ thực hiện hủy từng node có trong danh sách liên kết đơn đó.

Để thực hiện việc hủy danh sách, ta cần thực hiện 3 bước:

Bước đầu tiên: Duyệt toàn bộ danh sách từ đầu đến cuối danh sách
Bước thứ hai: Tạo một node p và gán bằng node đầu danh (pHead) sách: p = ds.pHead;
Bước thứ ba: gán phần tử đầu danh sách bằng node p trỏ đến next: ds.pHead = p->next
Bước thứ tư: Xóa đi node p ở bước 2: delete p; và gán phần tử cuối danh sách bằng NULL: ds.pTail = NULL;

Hàm void HuyDS(LIST &ds) dưới đây thực hiện việc xóa toàn bộ các node có trong danh sách liên kết đơn.

void HuyDS(LIST &ds){
    //duyet toan bo danh sach
    for(NODE *k = ds.pHead; k != NULL; k = k ->next)
    {
        //tao node p gan bang phan tu dau danh sach
        Node *p = ds.pHead;
        //gan phan tu dau danh sach bang p->next
        ds.pHead = p->next;
        //xoa di node p
        delete p;
    }
    //gan phan tu cuoi danh sach ve NULL
    ds.pTail = NULL;
}

Xóa phần tử trong danh sách liên kết đơn C/C++

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

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

3.Xóa phần tử có khóa k trong danh sách liên kết đơn

4.Hủy toàn bộ danh sách liên kết đơn