Danh sách liên kết đơn là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử (gọi là nút) được liên kết với nhau bằng các con trỏ. Mỗi nút chứa dữ liệu và một con trỏ trỏ đến nút tiếp theo trong danh sách. Nút cuối cùng có con trỏ trỏ đến NULL, biểu thị sự kết thúc của danh sách.

Để triển khai, trước tiên chúng ta cần định nghĩa cấu trúc cho một nút.

// Định nghĩa cấu trúc cho một nút của danh sách liên kết đơn
typedef struct Node {
    KieuDuLieu du_lieu;      // Trường dữ liệu, có thể là int, char, float, v.v.
    struct Node *con_tro_tiep_theo; // Con trỏ trỏ đến nút tiếp theo
} Node;

Trong định nghĩa trên, KieuDuLieu là một kiểu dữ liệu tùy ý, có thể là int, char, float hoặc thậm chí là một cấu trúc phức tạp.

Để làm việc với danh sách, chúng ta cần một con trỏ trỏ đến nút đầu tiên. Do đó, chúng ta định nghĩa một kiểu dữ liệu mới để đại diện cho danh sách.

typedef Node* DanhSachLienKet; // Định nghĩa kiểu con trỏ trỏ đến nút, đại diện cho danh sách

Node và DanhSachLienKet đều là các con trỏ đến cấu trúc Node. Tuy nhiên, Node nhấn mạnh một nút riêng lẻ, trong khi DanhSachLienKet nhấn mạnh toàn bộ danh sách.

Việc khởi tạo danh sách liên kết đơn có thể được thực hiện theo hai cách: có nút đầu (head node) hoặc không có nút đầu.

Khởi tạo danh sách không có nút đầu:

// Khởi tạo danh sách liên kết đơn không có nút đầu
bool KhoiTaoDanhSachKhongDau(DanhSachLienKet *ds) {
    *ds = NULL;
    return true;
}

Khởi tạo danh sách có nút đầu:

Phương pháp này thường được ưa chuộng vì nó giúp đơn giản hóa các thao tác sau này như chèn và xóa.

// Khởi tạo danh sách liên kết đơn có nút đầu
bool KhoiTaoDanhSach(DanhSachLienKet *ds) {
    *ds = (Node*)malloc(sizeof(Node)); // Cấp phát bộ nhớ cho nút đầu
    if (*ds == NULL) {
        return false; // Cấp phát thất bại
    }
    (*ds)->con_tro_tiep_theo = NULL; // Nút đầu trỏ đến NULL
    return true; // Khởi tạo thành công
}

Một cách phổ biến để tạo một danh sách liên kết đơn là sử dụng phương pháp chèn vào đầu. Phương pháp này bắt đầu bằng một danh sách rỗng, sau đó mỗi phần tử mới được chèn vào ngay sau nút đầu tiên.

// Tạo danh sách liên kết đơn bằng phương pháp chèn vào đầu
DanhSachLienKet TaoDanhSachBangChenDau() {
    DanhSachLienKet ds = NULL; // Ban đầu danh sách rỗng
    KieuDuLieu gia_tri;
    
    printf("Nhập các giá trị (nhập -1 để kết thúc): ");
    scanf("%d", &gia_tri);
    
    while (gia_tri != -1) { // Vòng lặp để nhập dữ liệu
        Node *moi_node = (Node*)malloc(sizeof(Node)); // Cấp phát bộ nhớ cho nút mới
        if (moi_node == NULL) {
            printf("Lỗi cấp phát bộ nhớ!\n");
            exit(1);
        }
        moi_node->du_lieu = gia_tri; // Gán dữ liệu cho nút mới
        
        // Chèn nút mới vào đầu danh sách
        moi_node->con_tro_tiep_theo = ds;
        ds = moi_node;
        
        scanf("%d", &gia_tri); // Nhập giá trị tiếp theo
    }
    return ds; // Trả về con trỏ đến nút đầu của danh sách
}