1.Cách thêm phần tử vào cuối danh sách liên kết đơn

Giả sử danh sách đơn ban đầu của tôi gồm các node (hay các phần tử) như hình minh họa bên dưới:

Bài trước ta đã tìm hiểu việc chèn node P vào đầu danh sách liên kết đơn, vấn đề đặt ra lần này tôi cần thêm một Node P vào danh sách liên kết đơn trên và đặt Node P này vào cuối danh sách liên kết đơn.

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

• Bước đầu tiên: Đặt con trỏ của phần tử pTail cuối danh sách vào Node P cần chèn: pTail->next = p;
• Bước thứ hai: Gán phần tử cuối pTail bằng Node P cần chèn cuối: pTail=p;

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

Tương tự như thêm phần tử vào đầu danh sách liên kết đơn. Nếu trường hợp danh sách đơn ban đầu là rỗng và không có node (phần tử) nào, để thực hiện việc thêm phần tử vào đầu danh sách rất đơn giản:

Ta chỉ việc đặt pHead (phần tử đầu) và pTail (phần tử cuối) bằng chính Node P cần chèn vào danh sách: ds.pHead = p; ds.pTail = p;

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

Hàm void ChenCuoi(LIST &ds, NODE *p) dưới đây nhận LIST &ds là danh sách cần thêm và NODE *p là phần tử hay Node cần chèn vào cuối danh sách:

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

3.Chương trình hoàn chỉnh thêm phần tử vào cuối 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 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;
    }
}

int main(){
    //khai bao mot danh sach
    LIST ds;
    //khoi tao danh sach
    KhoiTao(ds);
    //khai bao du lieu cua node
    int x = 10;
    //tao node p co du lieu la x
    NODE *p = new NODE;
    p = TaoNode(x);
    //them node p vao cuoi danh sach
    ChenCuoi(ds,p);
}

Chú ý:

• Một số hàm TaoNode(), KhoiTao(), KiemTraRong() đã được đề cập ở bài 1, bạn đọc quên vui lòng đọc lại!
• Danh sách ở trên là danh sách liên kết đơn với kiểu dữ liệu mẫu là int
• Để thực hiện kiểm tra phần tử vừa thêm vào danh sách vui lòng đọc đến bài duyệt phần tử trong danh sách liên kết đơn! (ở những bài tiếp theo)