Phương pháp chèn đầu và chèn đuôi trong danh sách liên kết đơn

1. Phương pháp chèn đầu (Head Insertion)

• Nguyên lý: Mỗi lần thêm nút mới vào đầu danh sách liên kết (trước nút head hiện tại).
• Đặc điểm:
  • Thứ tự chèn ngược với thứ tự cuối cùng của danh sách.
  • Độ phức tạp thời gian: O(1) (không cần duyệt).
• Ví dụ:
  • Thứ tự chèn: 1 → 2 → 3 → Thứ tự cuối cùng của danh sách: 3 → 2 → 1.

2. Phương pháp chèn đuôi (Tail Insertion)

• Nguyên lý: Mỗi lần thêm nút mới vào cuối danh sách liên kết (sau nút tail hiện tại).
• Đặc điểm:
  • Thứ tự chèn trùng với thứ tự cuối cùng của danh sách.
  • Độ phức tạp thời gian: O(1) nếu có con trỏ tail, ngược lại cần duyệt đến cuối O(n).
• Ví dụ:
  • Thứ tự chèn: 1 → 2 → 3 → Thứ tự cuối cùng của danh sách: 1 → 2 → 3.

Triển khai bằng C

Mã nguồn chèn đầu

#include <stdio.h>
#include <stdlib.h>

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

// Hàm chèn đầu
void themDau(Node** head, int giaTri) {
    Node* nutMoi = (Node*)malloc(sizeof(Node));
    nutMoi->data = giaTri;
    nutMoi->next = *head;  // Nút mới trỏ đến nút head cũ
    *head = nutMoi;        // Cập nhật con trỏ head
}

// In danh sách
void inDanhSach(Node* head) {
    Node* hienTai = head;
    while (hienTai != NULL) {
        printf("%d → ", hienTai->data);
        hienTai = hienTai->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;
    themDau(&head, 1);
    themDau(&head, 2);
    themDau(&head, 3);
    inDanhSach(head);  // Kết quả: 3 → 2 → 1 → NULL
    return 0;
}

Mã nguồn chèn đuôi

#include <stdio.h>
#include <stdlib.h>

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

// Hàm chèn đuôi (cần duy trì con trỏ tail)
void themDuoi(Node** head, Node** tail, int giaTri) {
    Node* nutMoi = (Node*)malloc(sizeof(Node));
    nutMoi->data = giaTri;
    nutMoi->next = NULL;

    if (*head == NULL) {  // Danh sách rỗng
        *head = nutMoi;
        *tail = nutMoi;
    } else {
        (*tail)->next = nutMoi;  // Nút tail cũ trỏ đến nút mới
        *tail = nutMoi;          // Cập nhật con trỏ tail
    }
}

// In danh sách
void inDanhSach(Node* head) {
    Node* hienTai = head;
    while (hienTai != NULL) {
        printf("%d → ", hienTai->data);
        hienTai = hienTai->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;
    Node* tail = NULL;
    themDuoi(&head, &tail, 1);
    themDuoi(&head, &tail, 2);
    themDuoi(&head, &tail, 3);
    inDanhSach(head);  // Kết quả: 1 → 2 → 3 → NULL
    return 0;
}

Tóm tắt các điểm chính

1. Chèn đầu: Thao tác trực tiếp trên con trỏ head, không cần duyệt.
2. Chèn đuôi: Cần duy trì con trỏ tail (hoặc duyệt đến cuối mỗi lần), hiệu quả hơn.
3. Lưu ý:
   • Trước khi chèn cần cấp phát bộ nhớ (malloc), khi xóa cần giải phóng (free).
   • Xử lý điều kiện biên với danh sách rỗng (khởi tạo con trỏ head/tail khi chèn lần đầu).

Biểu đồ so sánh: