Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++

struct Node {
    int data;
    Node* next;
};

struct Node {
    int data;
    Node* next;
    Node* prev;
};

// Hàm chèn một nút mới vào cuối danh sách liên kết
void insert (Node** head, int data) {
    // Tạo một nút mới và khởi tạo giá trị dữ liệu và con trỏ next của nó
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    // Nếu danh sách liên kết rỗng, thì đặt nút mới làm head
    if (*head == NULL) {
        *head = newNode;
    }
    else {
        // Tìm nút cuối cùng trong danh sách liên kết
        Node* lastNode = *head;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }

        // Chèn nút mới vào cuối danh sách liên kết
        lastNode->next = newNode;
    }
}

void insertAtBeginning(struct Node** head, int newData) {
    // Tạo một nút mới và gán giá trị của nó
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    newNode->next = *head;//Cho nút mới trỏ tới nút đầu tiên của danh sách

    // Cập nhật lại nút gốc là nút newNode
    *head = newNode;
}

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    // Nếu danh sách rỗng hoặc muốn chèn vào vị trí đầu tiên
    if (*head == NULL || position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* current = *head;
    Node* previous = NULL;
    int count = 1;

    // Duyệt đến vị trí cần chèn
    while (current != NULL && count < position) {
        previous = current;
        current = current->next;
        count++;
    }

    // Nếu vị trí chèn lớn hơn số lượng phần tử hiện tại của danh sách
    if (current == NULL && count < position) {
        cout << "Vị trí chèn lớn hơn số lượng phần tử hiện tại của danh sách." << endl;
        return;
    }

    // Chèn phần tử vào vị trí cần chèn
    previous->next = newNode;
    newNode->next = current;
}

//Hàm kiểm tra danh sách rỗng
bool isEmpty(Node* head) {
    return head == NULL; //Nếu head == NULL trả về 1, ngược lại trả về 0
}

//Hàm tính chiều dài danh sách liên kết
int length(Node* head) {
    int count = 0; // Khởi tạo biến đếm ban đầu bằng 0
    Node* current = head; // Khởi tạo con trỏ current trỏ đến đầu danh sách liên kết
    while (current != NULL) {  // Lặp lại việc tăng biến đếm cho tới khi con trỏ current trỏ đến 
        count++; // Tăng biến đếm lên một đơn vị
        current = current->next; // Di chuyển con trỏ current sang phần tử tiếp theo trong danh sách liên kết
    }
    return count;  // Trả về giá trị biến đếm sau khi đã tính được chiều dài của danh sách liên kết
}

// Hàm in ra các giá trị của danh sách liên kết đơn
// Input:
//      - head: con trỏ trỏ tới nút đầu tiên của danh sách liên kết đơn
void printList(Node* head) {
    Node* current = head; // Con trỏ current trỏ đến nút đầu tiên của danh sách liên kết đơn
    while (current != NULL) { // Vòng lặp sẽ thực hiện cho đến khi current trỏ đến NULL (cuối danh sách liên kết đơn)
        cout << current->data << " "; // In ra giá trị của nút hiện tại
        current = current->next; // Con trỏ current được di chuyển đến nút tiếp theo
    }
}

#include <iostream>
using namespace std;

// Khai báo cấu trúc Node
struct Node {
    int data;
    Node* next;
};

// Hàm chèn phần tử vào đầu danh sách
void insertAtBeginning(Node** head, int data) {
    Node* newNode = new Node; // Tạo một node mới
    newNode->data = data;
    newNode->next = *head; // Thiết lập con trỏ next của node mới trỏ đến head
    *head = newNode; // Cập nhật head để trỏ đến node mới
}

// Hàm xuất danh sách liên kết đơn
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
}

// Hàm main
int main() {
    Node* head = NULL; // Khởi tạo danh sách rỗng

    // Chèn các phần tử vào danh sách
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 15);
    insertAtBeginning(&head, 20);

    // Xuất danh sách liên kết đơn
    cout << "Danh sach lien ket don la: ";
    printList(head);

    return 0;
}