Trong phần này, các phần tử của danh sách liên kết đơn được hiểu là các Node trong danh sách. Hãy đảm bảo rằng bạn đã đọc bài đầu tiên trước khi chuyển sang bài này!

1.Cách thêm phần tử vào đầu 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:

Vấn đề đặt ra rằng 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 đầu danh sách liên kết đơn.

Như các bạn đã biết, một Node sẽ gồm hai thành phần đó là data và con trỏ next và để thực hiện việc thêm node vào đầu danh sách tôi cần thực hiện hai bước:

• Bước đầu tiên: đặt con trỏ next của Node P vào Node hiện tại đang là phần tử đầu tiên của danh sách (ví dụ ở hình dưới phần tử A đang là phần tử đầu tiên): p->next = ds.pHead;
• Bước thứ hai: Đặt pHead của danh sách bằng Node P cần chèn đầu: ds.pHead = p;

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

Chú ý:

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 đầu danh sách liên kết đơn

Hàm void ChenDau(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 đầu danh sách:

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

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

Chương trình dưới đây bao gồm đầy đủ các hàm cần thiết để thực hiện việc thêm đầu vào 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;
    }
}

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 x
    NODE *p = new NODE;
    p = TaoNode(x);
    //them node p vao dau danh sach
    ChenDau(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)