CHƯƠNG 3: CẤU TRÚC DANH SÁCH LIÊN KẾT

DSLK = Danh sách liên kết (tiếng Anh: Linked List).
Đây là viết tắt dùng xuyên suốt giáo trình, đề thi và thực hành. Khi thấy “DSLK đơn / kép / vòng”, hãy đọc là “danh sách liên kết đơn / kép / vòng”.

🎯 MỤC TIÊU CHƯƠNG 3

Sau khi học xong chương này, sinh viên có thể:

Giải thích được đối tượng dữ liệu con trỏ, phân biệt Stack/Heap, cấp phát và giải phóng bộ nhớ động.
Nêu định nghĩa danh sách liên kết, so sánh với mảng, và phân biệt các hình thức tổ chức (tuần tự / liên kết).
Tổ chức và cài đặt DSLK đơn theo cách cấp phát liên kết (NODE, LIST, pHead, pTail).
Thực hiện thành thạo các thao tác: khởi tạo, duyệt, tìm, thêm, xóa, hủy danh sách — kèm mã giả, code và độ phức tạp.
Sắp xếp DSLK bằng đổi chỗ trực tiếp (đúng đề thi), biết relink và Merge Sort; trộn hai danh sách đã sắp.
Cài đặt DSLK kép và DSLK vòng, nêu ưu nhược điểm và chọn đúng loại cho bài toán.
Áp dụng DSLK vào bài toán thực tế và giải bài tập từ cơ bản đến nâng cao.

📋 NỘI DUNG CHƯƠNG 3

3.1. Giới thiệu đối tượng dữ liệu con trỏ
3.2. Danh sách liên kết (DSLK)
     3.2.1. Định nghĩa DSLK
     3.2.2. Các hình thức tổ chức DSLK
3.3. DSLK đơn
     3.3.1. Tổ chức DSLK đơn theo cách cấp phát liên kết
     3.3.2. Các thao tác cơ bản trên DSLK đơn
     3.3.3. Sắp xếp danh sách
3.4. Một số DSLK khác
     3.4.1. DSLK kép
            A. Vì sao cần kép? Định nghĩa
            B. Tổ chức DNODE / DLIST, bất biến
            C. Dựng list và duyệt hai chiều
            D. Thêm đầu / thêm cuối
            E. Thêm sau / thêm trước / thêm tại vị trí
            F. Xóa nút đang cầm, xóa đầu, xóa cuối, xóa giá trị
            G. So sánh đơn–kép, ưu nhược, bẫy
            H. Ứng dụng: Back/Forward, Undo/Redo, LRU, deque
     3.4.2. DSLK vòng
            A. Vì sao cần vòng? Tổ chức chỉ giữ pTail
            B. Duyệt vòng (do-while) — không còn NULL
            C. Thêm đầu / thêm cuối (cùng 2 phép, khác pTail)
            D. Xóa đầu / xóa cuối / xóa giá trị / hủy
            E. Vòng kép
            F. Ứng dụng: round-robin, playlist, Josephus
            G. Ưu nhược, chọn loại
            H. Bảng bốn loại đơn / kép / vòng / vòng kép

Lưu ý cài đặt: Phần 3.1 dùng C để thấy rõ malloc/free (bản chất con trỏ). Từ mục 3.3 trở đi dùng C++ theo đúng mẫu giáo trình thực hành và đề thi: NODE, LIST, pHead, pTail, pNext. Con trỏ trong C và C++ là cùng một ý tưởng.

📖 CÁCH ĐỌC TÀI LIỆU NÀY (TỪ ZERO ĐẾN HERO)

Mốc	Đọc mục	Khi nào thì được sang bước sau
Nền	3.1 → 3.2	Vẽ được ô nhớ của `int *p = &a` và nói được DSLK khác mảng chỗ nào
Trọng tâm đề thi	3.3.1 → 3.3.2 → 3.3.3.A + 3.3.3.D	Tự viết `ThemDau`, `ThemCuoi`, `XoaDau`, `XoaCuoi`, `SapXep` (đổi chỗ trực tiếp), `Noi` không nhìn tài liệu
Mở rộng chương	3.4.1 → 3.4.2	Vẽ thêm/xóa kép (sửa đủ 4 liên kết); duyệt vòng bằng `do-while`; Josephus $n=5,k=2$
Cao cấp	3.5 → 3.6	Chỉ học khi đã code được 3.3; không cần thuộc để qua môn

Mỗi thao tác cơ bản được viết theo một khuôn: ý tưởng → sơ đồ trước/sau → mã giả → code → độ phức tạp → bẫy. Gặp chỗ đánh (nâng cao) thì có thể bỏ qua lần đọc đầu.

📚 BẢNG THUẬT NGỮ

Thuật ngữ / viết tắt	Nghĩa tiếng Việt	Ghi nhớ nhanh
DSLK	Danh sách liên kết	Dãy nút nắm tay nhau bằng con trỏ
Nút / NODE	Một phần tử của DSLK	Gồm `data` + con trỏ liên kết
`pHead`	Con trỏ đầu danh sách	Cửa vào của DSLK thẳng
`pTail`	Con trỏ cuối danh sách	Thêm cuối $O(1)$ ; vòng đơn chỉ cần `pTail` (`head = pTail->pNext`)
`pNext` / `pPrev`	Con trỏ nút sau / nút trước	Đơn chỉ có `pNext`; kép có cả hai
`NULL`	Không trỏ tới ô nhớ nào	Lính canh hết list thẳng; vòng không còn `NULL`
DSLK kép	Mỗi nút hai chiều	Đi lùi, xóa nút đang cầm, xóa cuối — $O(1)$
DSLK vòng	Đuôi nắm đầu	Dữ liệu tuần hoàn; duyệt bằng `do-while`
Bất biến	Điều luôn đúng sau mọi thao tác	Kép: hai chiều khớp; vòng: `pTail->pNext` là head
Cấp phát tuần tự	Lưu bằng mảng, ô nhớ kề nhau	Có `a[i]`
Cấp phát liên kết	Mỗi nút tự “ôm” địa chỉ nút kế	Không có `a[i]`
Heap	Vùng nhớ xin bằng `new`/`malloc`	Node sống đến khi `delete`/`free`
Stack (bộ nhớ)	Vùng nhớ biến cục bộ	Hết hàm là mất — không để node ở đây
Memory leak	Rò rỉ bộ nhớ	`new` mà quên `delete`
Dangling pointer	Con trỏ treo	Trỏ tới ô đã `delete`
ADT	Kiểu dữ liệu trừu tượng	“Danh sách là gì” trước khi cài bằng gì
Relink	Nối lại con trỏ	Đổi chỗ nút mà không copy `data`
Dummy / header node	Nút giả không chứa dữ liệu thật	Làm code thêm/xóa gọn hơn (khóa này không dùng)

3.1. GIỚI THIỆU ĐỐI TƯỢNG DỮ LIỆU CON TRỎ

Danh sách liên kết không tồn tại nếu không có con trỏ. Trước khi học DSLK, phải làm chủ bốn thứ:

Địa chỉ ô nhớ và biến con trỏ.
Toán tử & (lấy địa chỉ) và * (giải tham chiếu).
Con trỏ tới struct và toán tử ->.
Cấp phát / giải phóng bộ nhớ trên Heap.

Nếu bỏ qua mục này, các thao tác thêm/xóa node sẽ thành “copy code cho chạy” chứ không hiểu vì sao phải đổi con trỏ.

3.1.1. Bộ nhớ máy tính: biến, địa chỉ, giá trị

Mỗi biến khi chương trình chạy được hệ điều hành cấp một (hoặc nhiều) ô nhớ. Ô nhớ có:

Thành phần	Ý nghĩa	Ví dụ
Tên	Cách lập trình viên gọi biến	`a`
Kiểu	Cách diễn giải các bit	`int` (thường 4 byte)
Giá trị	Dữ liệu đang chứa	`10`
Địa chỉ	Vị trí ô nhớ trên RAM	`0x7ffe1234`

int a = 10;
printf("Gia tri a = %d\n", a);
printf("Dia chi a = %p\n", (void*)&a);   /* &a = dia chi cua a */

Ẩn dụ: Căn nhà có số nhà (địa chỉ) và người đang ở (giá trị). Muốn đến nhà đó, bạn cần số nhà, không cần nhớ người đang ở là ai.

3.1.2. Con trỏ là gì?

Định nghĩa: Con trỏ (pointer) là biến chuyên lưu địa chỉ của một biến (hoặc vùng nhớ) khác.

     a (int)                    p (int*)
   ┌────────┐                 ┌──────────┐
   │   10   │  <──────────────│  &a      │
   └────────┘                 └──────────┘
   địa chỉ: 0x100             địa chỉ: 0x200

Khai báo và hai toán tử bắt buộc

int  a = 10;
int *p = &a;     /* p luu dia chi cua a */

printf("%d\n", a);    /* 10  - gia tri cua a        */
printf("%p\n", (void*)p);   /* 0x100 - gia tri cua p (la dia chi) */
printf("%d\n", *p);   /* 10  - lay gia tri tai dia chi ma p dang tro */

Ký hiệu	Tên	Việc nó làm
`&x`	Address-of	Lấy địa chỉ của `x`
`*p`	Dereference / gián tiếp	Đọc/ghi giá trị tại ô nhớ mà `p` đang trỏ
`int *p`	Khai báo	`p` là con trỏ tới `int`

Quy tắc vàng:

p = địa chỉ.
*p = dữ liệu nằm ở địa chỉ đó.
Muốn đổi dữ liệu qua con trỏ: gán *p = ....
Muốn đổi chỗ đang trỏ: gán p = ....

int a = 10, b = 20;
int *p = &a;

*p = 99;     /* a thanh 99, p van tro toi a */
p  = &b;     /* p doi sang tro toi b, a van la 99 */
*p = 5;      /* b thanh 5 */

Đi từng dòng trên ô nhớ (địa chỉ minh họa). Đây là bài tập “zero” bắt buộc — đọc chậm:

Sau câu lệnh	`a`	`b`	`p` (chứa địa chỉ)	`*p` (giá trị tại chỗ p đang trỏ)
`int a = 10;`	10 tại `0x100`	—	—	—
`int b = 20;`	10	20 tại `0x104`	—	—
`int *p = &a;`	10	20	`0x100`	10
`*p = 99;`	99	20	`0x100` (không đổi)	99
`p = &b;`	99	20	`0x104`	20
`*p = 5;`	99	5	`0x104`	5

Hai thao tác không được lẫn:

*p = 99 = “vào nhà số p, đổi người đang ở”. Biến a đổi, bản thân p không đổi.
p = &b = “chuyển p sang giữ số nhà khác”. a không bị đụng.

Cách viết khai báo đều hợp lệ và cùng nghĩa: int *p, int* p, int * p. Giáo trình dùng NODE* p (kiểu nhìn rõ hơn).

3.1.3. Con trỏ `NULL` và con trỏ hoang

int *p = NULL;    /* p khong tro toi o nho hop le nao */

NULL (trong C++11 trở đi thường viết nullptr) nghĩa là “không trỏ tới đâu cả”. Đây là giá trị lính canh của DSLK: node cuối luôn có pNext = NULL.

Cấm tuyệt đối giải tham chiếu con trỏ NULL hoặc con trỏ chưa khởi tạo:

int *p;          /* wild pointer: chua gan, chua biet tro toi dau */
*p = 10;         /* UNDEFINED BEHAVIOR - co the crash */

int *q = NULL;
*q = 10;         /* crash: segmentation fault */

Trước khi dùng *p, luôn kiểm tra:

if (p != NULL) {
    printf("%d\n", *p);
}

3.1.4. Con trỏ và `struct` — toán tử `->`

Node của DSLK là một struct. Truy cập thành viên qua con trỏ dùng ->.

struct NODE {
    int data;
    struct NODE *pNext;
};

struct NODE n;
n.data = 5;
n.pNext = NULL;

struct NODE *p = &n;
p->data  = 7;          /* tuong duong (*p).data = 7  */
p->pNext = NULL;       /* tuong duong (*p).pNext = NULL */

Ghi nhớ:

p->data     ≡    (*p).data

Cả chương này, mọi thao tác DSLK đều là: đọc/ghi p->data và đổi p->pNext.

3.1.5. Stack và Heap — hai “kho” bộ nhớ

	Stack	Heap
Ai cấp phát?	Compiler, tự động khi vào hàm	Lập trình viên (`malloc` / `new`)
Thời gian sống	Hết hàm là mất	Sống đến khi `free` / `delete`
Tốc độ	Rất nhanh	Chậm hơn (phải tìm ô trống)
Kích thước	Cố định, nhỏ (vài MB)	Lớn, gần như RAM còn lại
Ví dụ	`int a = 10; int arr[100];`	Node của DSLK

#include <stdlib.h>
void f() {
    int x = 5;                 /* Stack: chet khi thoat f() */
    int *p = (int*)malloc(sizeof(int));
    if (p == NULL) return;
    *p = 5;
    free(p);
}

Vì sao DSLK phải dùng Heap? Vì số node không biết trước, và node phải tồn tại sau khi hàm tạo node kết thúc. Nếu cấp phát node trên Stack, khi hàm return thì node biến mất, con trỏ thành dangling.

3.1.6. Cấp phát động trong C: `malloc`, `calloc`, `free`

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

int main(void) {
    /* Xin 1 o int tren Heap */
    int *p = (int*)malloc(sizeof(int));
    if (p == NULL) {           /* BAT BUOC kiem tra: het RAM */
        printf("Khong cap phat duoc\n");
        return 1;
    }
    *p = 42;
    printf("%d\n", *p);
    free(p);                   /* Tra lai he dieu hanh */
    p = NULL;                  /* Tranh dangling pointer */
    return 0;
}

Hàm	Việc làm
`malloc(n)`	Xin `n` byte, không xóa rác trong ô nhớ
`calloc(k, sz)`	Xin `ksz` byte, điền 0*
`realloc(p, n)`	Đổi kích thước vùng nhớ (có thể copy sang chỗ mới)
`free(p)`	Trả vùng nhớ. Gọi 2 lần trên cùng `p` → double free (lỗi nặng)

Cấp phát một node (tư duy sẽ dùng suốt chương):

struct NODE *p = (struct NODE*)malloc(sizeof(struct NODE));
if (p == NULL) { /* xu ly loi */ }
p->data  = 10;
p->pNext = NULL;

3.1.7. Cấp phát động trong C++: `new` / `delete`

Giáo trình thực hành dùng C++:

NODE* p = new NODE;     // cap phat 1 node
p->data  = 10;
p->pNext = NULL;

delete p;               // giai phong 1 node
p = NULL;

C	C++
`malloc` + ép kiểu	`new NODE`
`free(p)`	`delete p`
Không gọi constructor	Có gọi constructor

Không lẫn: malloc đi với free, new đi với delete. Không free bộ nhớ new, không delete bộ nhớ malloc.

3.1.8. Bốn lỗi con trỏ “chết người” trong DSLK

1. Memory leak (rò rỉ bộ nhớ) — new mà quên delete:

NODE* p = new NODE;
p->data = 1;
p = new NODE;     // mat dia chi node cu → LEAK

2. Dangling pointer — xóa rồi vẫn dùng:

delete p;
p->data = 5;      // p tro toi o nho da tra lai HĐH

3. Mất liên kết — đổi pNext trước khi giữ địa chỉ node sau:

/* SAI: mat het phan duoi danh sach */
pHead = pHead->pNext;   // neu khong luu node cu thi khong delete duoc
                        // va neu day la node duy nhat con lai thi OK,
                        // nhung neu muon xoa node cu: phai giu temp

Cách đúng khi xóa đầu:

NODE* temp = l.pHead;
l.pHead = l.pHead->pNext;
delete temp;

4. Double free — delete cùng node hai lần.

3.1.9. Con trỏ cấp hai (`NODE**`) và truyền tham chiếu

Khi hàm cần đổi chính con trỏ pHead, phải truyền địa chỉ của con trỏ.

/* Cach 1: con tro cap 2 (C) */
void ThemDau(NODE **pHead, int x) {
    NODE* p = new NODE;
    p->data = x;
    p->pNext = *pHead;
    *pHead = p;            /* doi head o ben ngoai ham */
}

/* Cach 2: tham chieu C++ — dung trong giao trinh */
void ThemDau(LIST &l, NODE* p) {
    p->pNext = l.pHead;
    l.pHead = p;
}

Từ đây, giáo trình dùng cách 2: LIST &l. Dấu & ở đây là tham chiếu C++ (không phải lấy địa chỉ &a của mục 3.1.2): hàm sửa được pHead/pTail của người gọi.

Đoạn ThemDau phía trên cố ý rút gọn để chỉ ra ý “đổi được head”. Bản đủ (xét rỗng, cập nhật pTail) nằm ở mục 3.3.2.

3.1.10. Con trỏ và mảng (để đối chiếu với DSLK)

int a[5] = {1, 2, 3, 4, 5};
int *p = a;          /* ten mang chinh la dia chi phan tu dau */
printf("%d\n", *(p + 2));   /* 3  — so hoc con tro */
printf("%d\n", a[2]);       /* 3  — tuong duong */

Mảng: phần tử nằm liền nhau, nên p+1 nhảy đúng sizeof(int) byte.

DSLK: phần tử rải rác, p+1 không ra node kế. Muốn sang node sau bắt buộc p = p->pNext. Đây là lý do DSLK không truy cập ngẫu nhiên O(1) được.

3.1.11. Ví dụ tổng hợp: tạo 3 node rời rồi nối tay

Đọc ví dụ này xong là đã “nhìn thấy” DSLK.

#include <iostream>
using namespace std;

struct NODE {
    int data;
    NODE* pNext;
};

int main() {
    NODE* a = new NODE;  a->data = 10;  a->pNext = NULL;
    NODE* b = new NODE;  b->data = 20;  b->pNext = NULL;
    NODE* c = new NODE;  c->data = 30;  c->pNext = NULL;

    /* Noi: 10 -> 20 -> 30 -> NULL */
    a->pNext = b;
    b->pNext = c;

    NODE* p = a;
    while (p != NULL) {
        cout << p->data << " -> ";
        p = p->pNext;
    }
    cout << "NULL\n";

    delete a; delete b; delete c;
    return 0;
}

Sơ đồ bộ nhớ (địa chỉ minh họa) — khớp code a->pNext = b; b->pNext = c;:

              biến a
                │
                ▼
Heap:        0x10              0x50              0x90
          ┌────┬────┐      ┌────┬────┐      ┌────┬────┐
          │ 10 │  ●─┼─────►│ 20 │  ●─┼─────►│ 30 │  / │──► NULL
          └────┴────┘      └────┴────┘      └────┴────┘
             ▲
          pNext của 10 chứa 0x50, không phải “ô bên cạnh”

Ba node không nằm kề nhau (0x10, 0x50, 0x90). Chúng chỉ “biết nhau” nhờ pNext.

✅ Kiểm tra nhanh 3.1

Tự trả lời rồi lật đáp án ở dưới.

Khác nhau giữa p và *p?
Vì sao node DSLK không khai báo NODE n; trong hàm rồi return &n;?
malloc thất bại trả về gì? Phải làm gì?
Muốn xóa nút đầu: nếu viết delete pHead; rồi mới pHead = pHead->pNext thì sao? Nếu viết pHead = pHead->pNext mà không giữ nút cũ để delete thì sao?

Đáp án:

p là địa chỉ; *p là giá trị nằm tại địa chỉ đó.
n nằm trên Stack, chết khi hàm return → địa chỉ trả về thành dangling. Node phải new trên Heap.
Trả về NULL. Phải kiểm tra, không được p->data = .... (Còn new kiểu C++ chuẩn thì ném exception, không trả NULL; trong bài tập nhập môn vẫn hay kiểm tra NULL cho thống nhất tư duy “cấp phát có thể thất bại”.)
delete trước rồi đọc pHead->pNext = dùng ô nhớ đã trả (dangling, crash). Đổi pHead trước mà không delete nút cũ = leak. Cách đúng: temp = pHead; pHead = pHead->pNext; delete temp;.

3.2. DANH SÁCH LIÊN KẾT (DSLK)

DSLK chính là Danh sách liên kết. Phần này trả lời hai câu: nó là gì? và cài nó bằng cách nào?

3.2.1. Định nghĩa DSLK

A. Danh sách tuyến tính (ôn lại)

Danh sách tuyến tính (linear list) là tập hữu hạn các phần tử cùng kiểu, có thứ tự:

L = (a_0, a_1, a_2, \dots, a_{n-1})

$a_0$ là phần tử đầu, $a_{n-1}$ là phần tử cuối.
$a_i$ đứng trước $a_{i+1}$ , đứng sau $a_{i-1}$ .
Các thao tác trừu tượng (ADT List): khởi tạo rỗng, kiểm tra rỗng, lấy độ dài, lấy phần tử thứ $i$ , tìm, thêm, xóa, duyệt.

Mảng là một cách cài ADT này. DSLK là cách khác.

B. Định nghĩa danh sách liên kết

Danh sách liên kết là cấu trúc dữ liệu tuyến tính, trong đó:

Mỗi phần tử được đặt trong một nút (node / NODE).
Nút gồm hai phần: thông tin (data) và liên kết (con trỏ tới nút khác).
Các nút không cần nằm liên tục trong bộ nhớ. Thứ tự logic do con trỏ quyết định, không do địa chỉ vật lý.
Nút cuối trỏ tới NULL (DSLK thẳng) hoặc trỏ về nút đầu (DSLK vòng).

Ẩn dụ: Mảng là toa tàu hàn chết với nhau — muốn chèn toa giữa phải đẩy cả đoàn. DSLK là nhóm người nắm tay nhau — muốn chèn người mới chỉ cần hai người kề nhau buông tay rồi nắm tay người mới.

C. Nút (NODE) — viên gạch của DSLK

Mỗi nút là một hộp hai ngăn: ngăn trái chứa dữ liệu, ngăn phải chứa địa chỉ nút kế.

 ┌────────────┬────────────┐
 │    data    │   pNext    │
 │     10     │     ●──────┼──►  nút kế   (hoặc / = NULL nếu là nút cuối)
 └────────────┴────────────┘
   thông tin      liên kết

data: số nguyên, sinh viên, đơn hàng… — payload.
pNext: địa chỉ nút kế. Đây là thứ biến “đám node rời” thành “danh sách”.

D. So sánh mảng và DSLK (nắm để chọn đúng cấu trúc)

Tiêu chí	Mảng (cấp phát tuần tự)	DSLK (cấp phát liên kết)
Vị trí RAM	Liên tục	Rải rác
Kích thước	Cố định (hoặc phải `realloc`)	Tăng/giảm từng nút
Truy cập phần tử thứ $i$	$O(1)$	$O(n)$ — phải đi từ đầu
Thêm/xóa đầu	$O(n)$ — dồn mảng	$O(1)$
Thêm/xóa giữa (đã có sẵn con trỏ tới vị trí)	$O(n)$ — dồn	$O(1)$ — chỉ sửa 1–2 con trỏ
Thêm/xóa giữa (phải tìm vị trí)	$O(n)$	$O(n)$ tìm + $O(1)$ sửa
Bộ nhớ phụ	Chỉ dữ liệu	Thêm 1 con trỏ / nút (overhead)
Cục bộ cache	Tốt (nằm kề nhau)	Kém (nhảy lung tung trên RAM)
Tìm kiếm nhị phân	Làm được nếu đã sort	Không làm trực tiếp (không có chỉ số)

Khi nào chọn DSLK?

Không biết trước số phần tử.
Thêm/xóa đầu hoặc giữa diễn ra rất thường xuyên.
Không cần truy cập ngẫu nhiên a[i].
Cần cấu trúc linh hoạt: ngăn xếp, hàng đợi, đa thức, đồ thị (danh sách kề)…

Khi nào chọn mảng?

Cần a[i] thường xuyên.
Dữ liệu ít thay đổi kích thước.
Cần tận dụng cache CPU (xử lý số lớn, ma trận).

E. Định nghĩa hình thức (toán học) — có thể bỏ qua lần đọc đầu

Mục này dành cho ai muốn phát biểu “cho chặt”. Không cần thuộc để cài code.

DSLK đơn là bộ $(N, H)$ trong đó:

$N$ là tập nút; mỗi nút $x$ có trường data(x) và next(x) ∈ N ∪ {NULL}.
$H$ (head) là nút đầu, hoặc NULL nếu danh sách rỗng.
Mọi nút (trừ NULL) đều đến được từ $H$ bằng cách lặp next.
Không có chu trình (với DSLK thẳng): đi theo next luôn tới NULL.

3.2.2. Các hình thức tổ chức DSLK

Có hai cách lớn để cài một danh sách tuyến tính, và trong cách liên kết lại có vài biến thể.

A. Tổ chức tuần tự (sequential allocation)

Các phần tử nằm kề nhau trong một khối nhớ (mảng):

Chỉ số:   0     1     2     3     4
        ┌─────┬─────┬─────┬─────┬─────┐
        │  10 │  20 │  30 │  40 │     │
        └─────┴─────┴─────┴─────┴─────┘
        địa chỉ: 1000  1004  1008  1012  ...

Phần tử thứ $i$ ở địa chỉ:

\text{addr}(a_i) = \text{addr}(a_0) + i \times \text{sizeof}(a_0)

Đó là lý do truy cập $O(1)$ . Nhược điểm: chèn vào giữa phải dịch các phần tử bên phải.

 Chèn 25 vào giữa mảng [10, 20, 30, 40]:
 TRƯỚC     [ 10 | 20 | 30 | 40 |    ]
 CHÈN      [ 10 | 20 | 25 | 30 | 40 ]   ← 30 và 40 phải dời sang phải
                    ▲
                   chỗ mới: copy hàng loạt, O(n)

/* Chen x vao vi tri k trong mang a[0..n-1] */
for (int i = n; i > k; i--)
    a[i] = a[i - 1];
a[k] = x;
n++;

Độ phức tạp: $O(n)$ .

Trên DSLK, cùng việc chèn chỉ sửa hai con trỏ, không dời 30 và 40 (xem hình mục 3.2.2.B và thao tác ThemSau).

B. Tổ chức liên kết (linked allocation) — trọng tâm chương

Mỗi phần tử “ôm” địa chỉ phần tử kế:

  pHead
    │
    ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘
   0x10           0x88           0x24        (địa chỉ rải rác)
  data  next     data  next     data  NULL

Quy ước vẽ dùng suốt chương (học thuộc để đọc mọi hình sau):

 ┌────┬────┐
 │ 10 │  ●─┼───►     ●─┼───►  = con trỏ pNext đang trỏ tới nút kế
 └────┴────┘
 │ 30 │  / │──► NULL  /       = NULL (hết danh sách thẳng)

Không còn công thức địa chỉ theo chỉ số. Muốn tới phần tử thứ $i$ phải đi $i$ bước.

Ưu: chèn/xóa tại chỗ đã đứng chỉ sửa con trỏ, không dồn dữ liệu. Nhược: tốn RAM cho con trỏ; truy cập chậm; cache kém.

C. Danh sách liên kết tĩnh (cursor / mảng nút)

Khi ngôn ngữ không có con trỏ (Pascal cổ, Fortran) hoặc muốn quản lý bộ nhớ thủ công, dùng mảng các nút và liên kết bằng chỉ số nguyên:

struct StaticNode {
    int data;
    int next;     // chi so o mang, -1 = NULL
};

StaticNode pool[100];
int pHead = 0;    // nut dau o chi so 0
// pool[0] = {10, 2}
// pool[2] = {20, 5}
// pool[5] = {30, -1}

Đây vẫn là “tổ chức liên kết”, chỉ khác là liên kết bằng chỉ số chứ không bằng địa chỉ.

Đọc ví dụ pHead = 0, pool[0]={10,2}, pool[2]={20,5}, pool[5]={30,-1}:

 Chỉ số:     0              1      2              3   4      5
          ┌────┬────┐           ┌────┬────┐              ┌────┬────┐
          │ 10 │  2 │           │ 20 │  5 │              │ 30 │ -1 │
          └────┴────┘           └────┴────┘              └────┴────┘
            ▲    │                 ▲    │                   ▲
 pHead=0 ───┘    └── nhảy tới ô 2 ─┘    └── nhảy tới ô 5 ──┘  └── hết (-1)

 Thứ tự LOGIC:  10 → 20 → 30     (ô nhớ 0, 2, 5 không liền nhau)

Trong môn này ta dùng con trỏ thật (NODE*). Biết cursor để khi hỏi “ngôn ngữ không có con trỏ thì tổ chức liên kết thế nào?” vẫn trả lời được.

D. Phân loại theo chiều liên kết và hình dạng

                    DANH SÁCH LIÊN KẾT
                           │
         ┌─────────────────┼─────────────────┐
         │                 │                 │
      DSLK đơn          DSLK kép         DSLK vòng
    (1 con trỏ)      (2 con trỏ)      (đuôi nối đầu)
         │                 │                 │
         │                 │         ┌───────┴───────┐
         │                 │      vòng đơn        vòng kép

Loại	Con trỏ mỗi nút	Duyệt	Nút cuối trỏ tới
Đơn (singly)	`pNext`	Một chiều	`NULL`
Kép (doubly)	`pPrev`, `pNext`	Hai chiều	`pNext = NULL`, `pPrev` của đầu = `NULL`
Vòng đơn	`pNext`	Một chiều, không gặp `NULL`	Nút đầu
Vòng kép	`pPrev`, `pNext`	Hai chiều khép kín	Đầu ↔ cuối

Bốn hình — nhìn là phân biệt được:

1. DSLK đơn (thẳng):

  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

2. DSLK kép (thẳng, hai chiều):

  pHead                                         pTail
    │                                             │
    ▼                                             ▼
 ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
 │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │──► NULL
 └────┴────┴────┘   └─▲──┴────┴────┘   └─▲──┴────┴────┘
    ▲                 │                  │
    └─────────────────┴──────────────────┘
         pPrev (mỗi nút nhớ cả người đứng trước)
  NULL◄── ngăn prev của nút đầu

Cột trái = pPrev, cột giữa = data, cột phải = pNext.

3. DSLK vòng đơn (đuôi nắm đầu, không còn NULL):

          ┌──────────────────────────────────────────┐
          ▼                                          │
        ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    │
        │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼────┘
        └────┴────┘    └────┴────┘    └────┴────┘
            ▲                               ▲
          head                            pTail
          (head = pTail->pNext)

4. DSLK vòng kép (khép kín hai chiều):

     ┌─────────────────────────────────────────────────┐
     ▼                                                 │
 ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐│
 │  ● │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  ●─┼┘
 └────┴────┴────┘   └─▲──┴────┴────┘   └─▲──┴────┴────┘
     ▲                │                  │
     └────────────────┴──────────────────┘
  head->pPrev == pTail     pTail->pNext == head

E. Biến thể tổ chức: có / không có nút giả (dummy / header node)

Không dummy (giáo trình dùng cách này):

  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

Danh sách rỗng: pHead == NULL. Mọi hàm thêm/xóa phải xét riêng trường hợp rỗng và trường hợp 1 nút.

Có dummy (nâng cao, code gọn hơn):

  pHead                         pTail
    │                             │
    ▼                             ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │  - │  ●─┼───►│ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘
   dummy
  (không chứa dữ liệu có nghĩa)

Dummy không chứa dữ liệu có nghĩa. Danh sách “rỗng” vẫn còn 1 nút giả ⇒ thêm đầu luôn là ThemSau(dummy, p), không cần if (pHead == NULL).

Khóa này theo giáo trình: không dùng dummy, luôn xử lý rỗng / 1 nút tường minh. Biết dummy để đọc tài liệu tiếng Anh không bị bỡ ngỡ.

F. Tổ chức quản lý danh sách: chỉ `pHead` hay thêm `pTail`?

struct LIST {
    NODE* pHead;    // bat buoc
    NODE* pTail;    // khuyen dung
};

	Chỉ `pHead`	`pHead` + `pTail`
Thêm đầu	$O(1)$	$O(1)$
Thêm cuối	$O(n)$	$O(1)$
Xóa đầu	$O(1)$	$O(1)$
Xóa cuối	$O(n)$	$O(n)$ với DSLK đơn (vẫn phải tìm nút trước tail)
Bộ nhớ	1 con trỏ	2 con trỏ

Đề thi và thực hành dùng cả pHead lẫn pTail. Phải cập nhật pTail mỗi khi thêm/xóa ảnh hưởng nút cuối, nếu quên thì danh sách hỏng âm thầm.

✅ Kiểm tra nhanh 3.2

DSLK viết tắt của gì? Khác mảng ở chỗ nào về vị trí RAM?
Vì sao truy cập phần tử thứ $i$ của DSLK là $O(n)$ ?
Tổ chức tuần tự và tổ chức liên kết khác nhau thế nào?
Có pTail rồi, xóa cuối DSLK đơn có $O(1)$ không? Vì sao?

Đáp án: (1) Danh sách liên kết; nút rải rác, mảng liền kề. (2) Không có công thức địa chỉ, phải đi $i$ bước từ pHead. (3) Tuần tự = mảng kề nhau; liên kết = mỗi nút giữ địa chỉ (hoặc chỉ số) nút kế. (4) Không — không có pPrev, phải tìm nút kế cuối.

3.3. DSLK ĐƠN

Đã có định nghĩa và các hình thức tổ chức. Từ đây cài một loại cụ thể: danh sách liên kết đơn, cấp phát động bằng con trỏ — đúng trọng tâm đề thi.

DSLK đơn (Singly Linked List): mỗi nút chỉ biết nút đứng sau. Không đi ngược được.

  pHead                                         pTail
    │                                             │
    ▼                                             ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘

 Đứng ở nút 30: biết 40, KHÔNG biết 20  →  muốn xóa 40 phải đi lại từ pHead

Tính chất:

Đi từ pHead theo pNext sẽ thăm hết nút, kết thúc ở NULL.
Từ một nút không biết nút trước — muốn biết phải duyệt lại từ đầu. Đây là lý do xóa cuối / thêm trước nút $p$ tốn $O(n)$ .

3.3.1. Tổ chức DSLK đơn theo cách cấp phát liên kết

A. Khai báo cấu trúc — học thuộc, viết đúng trong mọi bài

#include <iostream>
#include <climits>
using namespace std;

struct NODE {
    int data;        // thong tin
    NODE* pNext;     // lien ket toi nut ke
};

struct LIST {
    NODE* pHead;     // nut dau
    NODE* pTail;     // nut cuoi
};

Mỗi lần new NODE là một lần cấp phát liên kết: hệ điều hành tìm một chỗ trống trên Heap, trả về địa chỉ, ta cất địa chỉ đó vào pNext của nút trước.

 struct NODE                  struct LIST
 ┌────┬────┐                  ┌────────┬────────┐
 │data│pNext│                 │ pHead  │ pTail  │
 └────┴────┘                  └────────┴────────┘
      ▲                            │         │
      │                            │         └──► nút cuối
      └── new NODE                 └──────────► nút đầu

B. Khởi tạo danh sách rỗng

  LIST l
  ┌────────┬────────┐
  │ pHead  │ pTail  │
  └───┬────┴───┬────┘
      │        │
      ▼        ▼
     NULL     NULL     ← chưa có nút nào trên Heap

Mã giả:

THUẬT TOÁN KhoiTao(l)
Vào:  l — danh sách
Ra:   l rỗng
1. l.pHead ← NULL
2. l.pTail ← NULL

void KhoiTao(LIST &l) {
    l.pHead = l.pTail = NULL;
}

bool IsEmpty(LIST l) {
    return l.pHead == NULL;
}

C. Tạo một nút — đơn vị cấp phát

Mã giả:

THUẬT TOÁN TaoNode(x) → p
p ← cấp phát một NODE
Nếu p = NULL thì báo lỗi, dừng
p.data  ← x
p.pNext ← NULL      // nut moi chua noi vao ai
Trả về p

NODE* TaoNode(int x) {
    NODE* p = new NODE;   // het RAM: C++ nem bad_alloc, khong tra NULL
    p->data  = x;
    p->pNext = NULL;      // bat buoc truoc khi noi vao list
    return p;
}

Giáo trình thực hành cũng viết như trên (không kiểm NULL). Muốn new trả NULL khi hết RAM: NODE* p = new (nothrow) NODE; rồi mới if (p == NULL).

Quy tắc: nút mới luôn có pNext = NULL trước khi gắn vào danh sách. Gắn xong mới nối.

  TaoNode(10) trả về p:

    p
    │
    ▼
 ┌────┬────┐
 │ 10 │  / │──► NULL     ← hộp đứng một mình, chưa ai nắm, chưa nắm ai
 └────┴────┘

D. Mô hình cấp phát khi thêm lần lượt 10, 20, 30 vào cuối

Bước 0 — rỗng:

 pHead ──► NULL     pTail ──► NULL

Bước 1 — thêm 10 (danh sách rỗng: head = tail = nút mới):

 pHead, pTail
      │
      ▼
   ┌────┬────┐
   │ 10 │  / │──► NULL
   └────┴────┘

Bước 2 — thêm 20: pTail->pNext = p rồi pTail = p

 pHead          pTail
   │              │
   ▼              ▼
 ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  / │──► NULL
 └────┴────┘    └────┴────┘

Bước 3 — thêm 30:

 pHead                    pTail
   │                        │
   ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

Trên RAM, ba nút có thể ở 0x1A00, 0x20F8, 0x0C10 — không liền kề. Logic vẫn là 10→20→30 vì ta gán con trỏ, không phải vì địa chỉ tăng dần.

E. Duyệt danh sách — thao tác nền của mọi thuật toán

Muốn “nhìn” hết danh sách, chỉ có một cách: đi từ pHead đến khi gặp NULL.

Mã giả:

THUẬT TOÁN Duyet(l)
p ← l.pHead
while p ≠ NULL
    xử lý p.data        // in, dem, so sanh...
    p ← p.pNext
hết

void Xuat(LIST l) {
    NODE* p = l.pHead;
    cout << "Danh sach: ";
    while (p != NULL) {
        cout << p->data << " -> ";
        p = p->pNext;
    }
    cout << "NULL\n";
}

int DemSoPhanTu(LIST l) {
    int dem = 0;
    for (NODE* p = l.pHead; p != NULL; p = p->pNext)
        dem++;
    return dem;
}

	Thời gian	Không gian
Duyệt / Đếm / Xuất	$O(n)$	$O(1)$

Lỗi kinh điển khi duyệt:

while (p != NULL) {
    cout << p->data;
    /* quen p = p->pNext  → vong lap vo han */
}

while (p->pNext != NULL) {   // SAI neu muon xu ly ca nut cuoi
    cout << p->data;
    p = p->pNext;
}

Điều kiện p != NULL thì thăm mọi nút. Điều kiện p->pNext != NULL thì bỏ nút cuối — chỉ dùng khi cố ý dừng ở nút trước cuối (ví dụ xóa cuối).

F. Hai cách “cầm” danh sách trong hàm

void Xuat(LIST l);        // copy 2 con tro head/tail, khong sua duoc danh sach goc
void ThemDau(LIST &l, NODE* p);  // sua duoc pHead, pTail

In/đếm/tìm: truyền LIST l. Thêm/xóa/sắp xếp: truyền LIST &l.

3.3.2. Các thao tác cơ bản trên DSLK đơn

Thứ tự logic khi học (và khi viết chương trình):

Tạo rỗng → Tạo nút → Thêm (đầu/cuối) → Xuất
       → Tìm / Đếm / Min-max
       → Thêm giữa / Xóa
       → Hủy

Mục 3.3.1 đã xong khối “tạo rỗng, tạo nút, xuất”. Dưới đây lần lượt: tìm → thêm → xóa → thống kê → hủy. Mỗi thao tác: ý tưởng → sơ đồ → mã giả → code → độ phức tạp → bẫy.

Muốn thử ngay: gõ KhoiTao + ThemCuoi + Xuat trước, rồi mới học xóa. Đừng học xóa khi chưa dựng được một list.

① Tìm kiếm theo giá trị

Ý tưởng: duyệt tuyến tính, so sánh data. DSLK không binary search được — không có chỉ số, không nhảy giữa list được.

Ví dụ: tìm 30 trong 10 → 20 → 30 → 40. Con trỏ p đi từng hộp, không nhảy:

  pHead
    │
    ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘
    ▲                ▲              ▲
  B1: 10≠30       B2: 20≠30      B3: 30=30  → trả về p

Không tìm thấy: p đi tới NULL, trả về NULL (không phải -1 như trên mảng — vì không có chỉ số).

Mã giả:

THUẬT TOÁN Tim(l, x) → p
p ← l.pHead
while p ≠ NULL
    nếu p.data = x thì trả về p
    p ← p.pNext
trả về NULL

NODE* Tim(LIST l, int x) {
    NODE* p = l.pHead;
    while (p != NULL) {
        if (p->data == x) return p;
        p = p->pNext;
    }
    return NULL;
}

Trường hợp	Độ phức tạp
Tốt nhất (nút đầu)	$O(1)$
Trung bình / xấu nhất	$O(n)$

② Thêm vào đầu — $O(1)$ — thao tác “rẻ” nhất của DSLK đơn

Ý tưởng: nút mới trỏ tới head cũ, rồi head trỏ tới nút mới.

Trường hợp rỗng:

 Trước:  pHead ──► NULL    pTail ──► NULL

 Sau:    pHead, pTail
              │
              ▼
           ┌────┬────┐
           │  5 │  / │──► NULL
           └────┴────┘

Trường hợp đã có nút — đúng thứ tự ① rồi ②:

 TRƯỚC                         p (nút mới, chưa nối)
  pHead          pTail           │
    │              │             ▼
    ▼              ▼          ┌────┬────┐
 ┌────┬────┐    ┌────┬────┐   │  5 │  / │
 │ 10 │  ●─┼───►│ 20 │  / │   └────┴────┘
 └────┴────┘    └────┴────┘

 ①  p->pNext = l.pHead     (5 nắm lấy 10 — PHẢI làm trước)
 ②  l.pHead  = p           (cửa vào chuyển sang 5)
     pTail không đổi

 SAU
  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │  5 │  ●─┼───►│ 10 │  ●─┼───►│ 20 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

Sai nếu đảo ② trước ①: pHead = p khi p->pNext còn NULL → mất đường tới 10 và 20 (rò rỉ cả list cũ).

Mã giả:

THUẬT TOÁN ThemDau(l, p)
nếu l.pHead = NULL
    l.pHead ← p
    l.pTail ← p
ngược lại
    p.pNext ← l.pHead
    l.pHead ← p

void ThemDau(LIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pHead == NULL) {
        l.pHead = l.pTail = p;
    } else {
        p->pNext = l.pHead;
        l.pHead  = p;
    }
}

void ThemDauGiaTri(LIST &l, int x) {
    ThemDau(l, TaoNode(x));
}

Thứ tự gán bắt buộc: phải p->pNext = l.pHead trước, rồi mới l.pHead = p. Đảo ngược thì mất cả danh sách cũ.

Độ phức tạp: $O(1)$ — không duyệt.

③ Thêm vào cuối — $O(1)$ nhờ `pTail`

Không có pTail: phải duyệt đến nút cuối rồi nối → $O(n)$ . Có pTail: nối thẳng vào tail → $O(1)$ .

 TRƯỚC
  pHead          pTail              p (nút mới)
    │              │                │
    ▼              ▼                ▼
 ┌────┬────┐    ┌────┬────┐      ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  / │      │ 30 │  / │
 └────┴────┘    └────┴────┘      └────┴────┘

 ①  l.pTail->pNext = p     (20 nắm lấy 30)
 ②  l.pTail = p            (cửa cuối chuyển sang 30)

 SAU
  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

Mã giả:

THUẬT TOÁN ThemCuoi(l, p)
nếu l.pHead = NULL
    l.pHead ← p
    l.pTail ← p
ngược lại
    l.pTail.pNext ← p
    l.pTail ← p

void ThemCuoi(LIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pHead == NULL) {
        l.pHead = l.pTail = p;
    } else {
        l.pTail->pNext = p;
        l.pTail = p;
    }
}

Bẫy: sau ThemCuoi, p->pNext phải là NULL (đã làm trong TaoNode). Nếu p đang là một chuỗi nút, cả chuỗi sẽ bị gắn vào — hữu ích khi nối hai list, nguy hiểm nếu quên.

Độ phức tạp: $O(1)$ với pTail, $O(n)$ nếu chỉ có pHead.

④ Thêm sau một nút `q` cho trước — $O(1)$

Đã cầm sẵn con trỏ q thì không cần tìm.

 TRƯỚC  (q đang cầm nút 20)
  pHead          q                         pTail
    │            │                           │
    ▼            ▼                           ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

 p = nút 30. Thứ tự BẮT BUỘC:
 ①  p->pNext = q->pNext     (30 nắm 40 — giữ phần sau trước khi cắt)
 ②  q->pNext = p            (20 nắm 30)
     nếu q == pTail thì pTail = p

 SAU
  pHead          q              p            pTail
    │            │              │              │
    ▼            ▼              ▼              ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘

Mã giả:

THUẬT TOÁN ThemSau(l, q, p)
Vào: q ≠ NULL, p là nút mới
1. p.pNext ← q.pNext
2. q.pNext ← p
3. nếu q là l.pTail thì l.pTail ← p

void ThemSau(LIST &l, NODE* q, NODE* p) {
    if (q == NULL || p == NULL) return;
    p->pNext = q->pNext;
    q->pNext = p;
    if (q == l.pTail)
        l.pTail = p;
}

Thứ tự hai dòng 1–2 không được đảo: nếu gán q->pNext = p trước thì mất liên kết tới phần sau.

⑤ Thêm trước một nút `q` — $O(n)$ trên DSLK đơn

DSLK đơn không có pPrev, nên phải tìm nút đứng trước q.

Mã giả:

THUẬT TOÁN ThemTruoc(l, q, p)
nếu q = l.pHead thì ThemDau(l, p); return
t ← l.pHead
while t ≠ NULL và t.pNext ≠ q
    t ← t.pNext
nếu t ≠ NULL thì ThemSau(l, t, p)

void ThemTruoc(LIST &l, NODE* q, NODE* p) {
    if (q == NULL || p == NULL) return;
    if (q == l.pHead) {
        ThemDau(l, p);
        return;
    }
    NODE* t = l.pHead;
    while (t != NULL && t->pNext != q)
        t = t->pNext;
    if (t != NULL)
        ThemSau(l, t, p);
}

Độ phức tạp: $O(n)$ vì phải tìm nút trước. Trên DSLK kép thao tác này là $O(1)$ .

Sơ đồ (thêm 15 trước nút 20 — q cầm 20):

 TRƯỚC
  pHead          q
    │            │
    ▼            ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

 Không có pPrev → phải đi từ pHead tìm t sao cho t->pNext == q
  t cầm nút 10. Rồi ThemSau(l, t, p) như mục ④.

 SAU
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 15 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘

Bẫy: nếu q không thuộc list, vòng while đi tới NULL rồi không thêm — phải kiểm tra t != NULL.

⑥ Thêm tại vị trí `k` (k đếm từ 0)

k = 0          → ThemDau
k = số phần tử → ThemCuoi
0 < k < n      → đứng ở nút k-1, ThemSau
k không hợp lệ → báo lỗi, không thêm

void ThemTaiViTri(LIST &l, int k, int x) {
    int n = DemSoPhanTu(l);
    if (k < 0 || k > n) {
        cout << "Vi tri khong hop le!\n";
        return;
    }
    NODE* p = TaoNode(x);
    if (k == 0) { ThemDau(l, p); return; }
    NODE* q = l.pHead;
    for (int i = 0; i < k - 1; i++)
        q = q->pNext;
    ThemSau(l, q, p);
}

Thời gian: $O(n)$ (đi tới vị trí). Việc gắn nút: $O(1)$ .

Ví dụ chạy tay: list 10 → 20 → 30 ( $n = 3$ ).

$k$	Ý nghĩa	Kết quả
0	Thêm đầu	`x → 10 → 20 → 30`
1	Đứng ở nút 0, thêm sau	`10 → x → 20 → 30`
3	Thêm cuối ( $k = n$ )	`10 → 20 → 30 → x`
4	Không hợp lệ	Không thêm

⑥b. Lấy phần tử thứ $k$ (truy cập)

Không có a[k]. Phải đi $k$ bước từ pHead.

NODE* LayTaiViTri(LIST l, int k) {
    if (k < 0) return NULL;
    NODE* p = l.pHead;
    int i = 0;
    while (p != NULL && i < k) {
        p = p->pNext;
        i++;
    }
    return p;   // NULL nếu k >= n
}

$O(k)$ , xấu nhất $O(n)$ . Đây là lý do DSLK thua mảng khi cần lấy phần tử giữa thường xuyên.

⑦ Xóa đầu — $O(1)$

 TRƯỚC
  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

 temp = pHead (giữ 10 để delete)
 pHead = pHead->pNext  (cửa vào nhảy sang 20)
 delete temp

 SAU
                pHead          pTail
                  │              │
                  ▼              ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │    │    │ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘
   đã delete

Mã giả:

THUẬT TOÁN XoaDau(l)
nếu l.pHead = NULL thì return          // rong
p ← l.pHead
l.pHead ← l.pHead.pNext
nếu l.pHead = NULL thì l.pTail ← NULL  // vua xoa nut duy nhat
delete p

void XoaDau(LIST &l) {
    if (l.pHead == NULL) return;
    NODE* p = l.pHead;
    l.pHead = l.pHead->pNext;
    if (l.pHead == NULL)
        l.pTail = NULL;
    delete p;
}

Bẫy 1: quên cập nhật pTail khi xóa nút duy nhất → pTail dangling. Bẫy 2: delete rồi mới pHead = pHead->pNext → đọc ô nhớ đã giải phóng.

⑧ Xóa cuối — $O(n)$ trên DSLK đơn

Phải tìm nút kế cuối (nút có pNext == pTail). Có pTail không giúp xóa cuối xuống $O(1)$ , vì không có pPrev. Muốn $O(1)$ phải dùng DSLK kép.

Vì sao phải tìm nút kế cuối? Xóa nút cuối rồi, nút đứng trước nó phải trỏ NULL và trở thành pTail mới. DSLK đơn không đi lùi được nên phải đi từ đầu.

 TRƯỚC
  pHead                    pTail
    │                        │
    ▼                        ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘
                  p              (p->pNext == pTail)

 p đi từ đầu đến nút KẾ CUỐI (20).
 delete pTail (30)
 p->pNext = NULL
 pTail = p

 SAU
  pHead          pTail
    │              │
    ▼              ▼
 ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  / │──► NULL
 └────┴────┘    └────┴────┘

Ba trường hợp bắt buộc:

List	Cách xử lý
Rỗng	Không làm gì
1 nút (`pHead == pTail`)	`delete` nút đó, cả hai con trỏ về `NULL`
≥ 2 nút	Tìm kế cuối như sơ đồ

Mã giả:

THUẬT TOÁN XoaCuoi(l)
nếu rỗng thì return
nếu chỉ 1 nút thì XoaDau(l); return
p ← l.pHead
while p.pNext ≠ l.pTail
    p ← p.pNext          // p dung o nut ke cuoi
delete l.pTail
p.pNext ← NULL
l.pTail ← p

void XoaCuoi(LIST &l) {
    if (l.pHead == NULL) return;
    if (l.pHead == l.pTail) {
        delete l.pHead;
        l.pHead = l.pTail = NULL;
        return;
    }
    NODE* p = l.pHead;
    while (p->pNext != l.pTail)
        p = p->pNext;
    delete l.pTail;
    p->pNext = NULL;
    l.pTail = p;
}

⑨ Xóa sau nút `q` — $O(1)$ nếu đã có `q`

 TRƯỚC  (q cầm 20, xóa nút SAU q)
  pHead          q              p=q->pNext     pTail
    │            │              │                │
    ▼            ▼              ▼                ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘

 ①  q->pNext = p->pNext     (20 nhảy cóc sang 40)
 ②  nếu p == pTail thì pTail = q
 ③  delete p

 SAU
  pHead          q                         pTail
    │            │                           │
    ▼            ▼                           ▼
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘

Mã giả:

THUẬT TOÁN XoaSau(l, q)
nếu q = NULL hoặc q.pNext = NULL thì return   // khong co nut sau de xoa
p ← q.pNext
q.pNext ← p.pNext
nếu p = l.pTail thì l.pTail ← q
delete p

void XoaSau(LIST &l, NODE* q) {
    if (q == NULL || q->pNext == NULL) return;
    NODE* p = q->pNext;       // nut bi xoa
    q->pNext = p->pNext;
    if (p == l.pTail)
        l.pTail = q;
    delete p;
}

Bẫy: quên dòng 4 khi xóa đúng nút cuối → pTail treo. Không được XoaSau khi muốn xóa chính q — hàm này xóa nút đứng sau q.

⑩ Xóa theo giá trị (nút đầu tiên có `data == x`)

Hai nhánh: xóa đầu, hoặc tìm nút trước nút cần xóa rồi XoaSau.

 List: xóa x = 30
 ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
 │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼───►│ 40 │  / │──► NULL
 └────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘
                  q              q->pNext->data == 30
                                 → XoaSau(l, q)

Nếu x nằm ở đầu: không có nút trước → gọi XoaDau.

void XoaNodeTheoGiaTri(LIST &l, int x) {
    if (l.pHead == NULL) return;
    if (l.pHead->data == x) {
        XoaDau(l);
        return;
    }
    NODE* q = l.pHead;
    while (q->pNext != NULL && q->pNext->data != x)
        q = q->pNext;
    if (q->pNext != NULL)
        XoaSau(l, q);
    else
        cout << "Khong tim thay " << x << "\n";
}

Hàm XoaMin (xóa phần tử nhỏ nhất — hay ra đề) = tìm min rồi gọi hàm này; xem mục ⑪.

⑩b. Xóa tại vị trí $k$ (đếm từ 0)

Đề bài và bài tập thường hỏi hàm này. Tư duy giống thêm tại vị trí, nhưng gọi xóa.

k = 0      → XoaDau
k > 0      → đứng ở nút k-1, XoaSau
k không hợp lệ (k < 0 hoặc k ≥ n) → không xóa

void XoaTaiViTri(LIST &l, int k) {
    int n = DemSoPhanTu(l);
    if (k < 0 || k >= n) {
        cout << "Vi tri khong hop le!\n";
        return;
    }
    if (k == 0) {
        XoaDau(l);
        return;
    }
    NODE* q = l.pHead;
    for (int i = 0; i < k - 1; i++)
        q = q->pNext;
    XoaSau(l, q);
}

$O(n)$ . Lưu ý: thêm tại $k$ cho phép $k = n$ (thêm sau phần tử cuối); xóa tại $k$ không cho $k = n$ vì không có phần tử đó.

void XoaTatCaGiaTri(LIST &l, int x) {
    while (Tim(l, x) != NULL)
        XoaNodeTheoGiaTri(l, x);
}

Độ phức tạp: $O(n)$ một lần xóa; $O(n^2)$ nếu xóa hết bản sao theo cách naive ở trên. Cách một lần duyệt $O(n)$ :

void XoaTatCaGiaTri_O_n(LIST &l, int x) {
    while (l.pHead != NULL && l.pHead->data == x)
        XoaDau(l);
    NODE* q = l.pHead;
    while (q != NULL && q->pNext != NULL) {
        if (q->pNext->data == x)
            XoaSau(l, q);     // q dung yen, vi nut sau da doi
        else
            q = q->pNext;
    }
}

⑪ Tìm min / max, thống kê — mẫu đề thi

int TimMin(LIST l) {
    if (l.pHead == NULL) return INT_MAX;
    int m = l.pHead->data;
    for (NODE* p = l.pHead->pNext; p != NULL; p = p->pNext)
        if (p->data < m) m = p->data;
    return m;
}

NODE* TimNodeMax(LIST l) {
    if (l.pHead == NULL) return NULL;
    NODE* mx = l.pHead;
    for (NODE* p = l.pHead->pNext; p != NULL; p = p->pNext)
        if (p->data > mx->data) mx = p;
    return mx;
}

bool LaSoNguyenTo(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int DemSoNguyenTo(LIST l) {
    int dem = 0;
    for (NODE* p = l.pHead; p != NULL; p = p->pNext)
        if (LaSoNguyenTo(p->data)) dem++;
    return dem;
}

void LietKeSoChan(LIST l) {
    for (NODE* p = l.pHead; p != NULL; p = p->pNext)
        if (p->data % 2 == 0) cout << p->data << " ";
    cout << "\n";
}

Tất cả $O(n)$ .

void XoaMin(LIST &l) {          // mau de thi
    if (l.pHead == NULL) return;
    XoaNodeTheoGiaTri(l, TimMin(l));
}

Hai lần duyệt: một lần tìm min, một lần xóa → vẫn $O(n)$ .

Vì sao TimMin bắt đầu từ pHead->pNext? Vì m đã lấy pHead->data làm mốc. So sánh lại nút đầu là thừa, không sai.

⑫ Tách danh sách theo điều kiện (mẫu đề thi)

Tách l thành l1 (số nguyên tố) và l2 (còn lại). Không phá l gốc nếu đề yêu cầu — tạo node mới.

Ví dụ: l = 7 → 4 → 9 → 2 → 8

 l gốc (không bị phá):
 ┌────┬────┐   ┌────┬────┐   ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
 │  7 │  ●─┼──►│  4 │  ●─┼──►│  9 │  ●─┼──►│  2 │  ●─┼──►│  8 │  / │
 └────┴────┘   └────┴────┘   └────┴────┘   └────┴────┘   └────┴────┘

 l1 nguyên tố:     ┌────┬────┐   ┌────┬────┐
                   │  7 │  ●─┼──►│  2 │  / │
                   └────┴────┘   └────┴────┘
 l2 không:         ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
                   │  4 │  ●─┼──►│  9 │  ●─┼──►│  8 │  / │
                   └────┴────┘   └────┴────┘   └────┴────┘

void Tach(LIST l, LIST &l1, LIST &l2) {
    KhoiTao(l1);
    KhoiTao(l2);
    for (NODE* p = l.pHead; p != NULL; p = p->pNext) {
        NODE* q = TaoNode(p->data);
        if (LaSoNguyenTo(p->data)) ThemCuoi(l1, q);
        else                       ThemCuoi(l2, q);
    }
}

$O(n)$ . Nếu được phép di chuyển node (không new lại) thì phải cắt/nối pNext cẩn thận và cập nhật 3 cái tail.

⑬ Hủy toàn bộ danh sách — chống memory leak

THUẬT TOÁN HuyDanhSach(l)
1. while l.pHead ≠ NULL
2.     XoaDau(l)

void HuyDanhSach(LIST &l) {
    while (l.pHead != NULL)
        XoaDau(l);
}

$O(n)$ . Sau khi hủy: pHead = pTail = NULL.

Sai: delete l.pHead một lần rồi thôi — chỉ giải phóng nút đầu, $n-1$ nút leak.

⑭ Bảng tổng hợp độ phức tạp DSLK đơn (`pHead` + `pTail`)

Thao tác	Thời gian	Ghi chú
Khởi tạo / Rỗng?	$O(1)$
Truy cập thứ $i$	$O(n)$	Không có `a[i]`
Tìm theo giá trị	$O(n)$
Thêm/Xóa đầu	$O(1)$
Thêm cuối	$O(1)$	Nhờ `pTail`
Xóa cuối	$O(n)$	Phải tìm nút kế cuối
Thêm/Xóa sau nút `q`	$O(1)$	Đã có `q`
Thêm/Xóa trước nút `q`	$O(n)$	Phải tìm nút trước
Thêm/Xóa vị trí $k$	$O(n)$	`ThemTaiViTri` / `XoaTaiViTri`
Duyệt / Đếm / Hủy	$O(n)$
Không gian	$O(n)$	Thêm 1 con trỏ / nút

⑮ Ví dụ chạy tay cả chuỗi thao tác (đọc để “thấy” pHead / pTail)

Bắt đầu list rỗng. Theo dõi từng thay đổi — đây là cách debug DSLK trên giấy trước khi gõ code.

Bước	Thao tác	Danh sách	pHead	pTail
0	`KhoiTao`	(rỗng)	`NULL`	`NULL`
1	`ThemCuoi(5)`	`5`	5	5
2	`ThemDau(2)`	`2 → 5`	2	5
3	`ThemCuoi(9)`	`2 → 5 → 9`	2	9
4	`XoaDau`	`5 → 9`	5	9
5	`ThemTaiViTri(1, 7)`	`5 → 7 → 9`	5	9
6	`XoaCuoi`	`5 → 7`	5	7
7	`XoaNodeTheoGiaTri(5)`	`7`	7	7
8	`XoaDau`	(rỗng)	`NULL`	`NULL`

Bước 8 là chỗ hay quên: xóa nút duy nhất phải đưa cả pHead và pTail về NULL. Nếu quên pTail, lần ThemCuoi sau sẽ ghi vào ô nhớ đã delete → crash.

⑯ Chương trình tối thiểu — copy, biên dịch, chạy được

Ghép các hàm đã học: KhoiTao, TaoNode, ThemDau, ThemCuoi, Xuat, XoaDau, SapXep, HuyDanhSach. Lưu dslk.cpp, chạy:

c++ -std=c++11 -o dslk dslk.cpp && ./dslk

#include <iostream>
using namespace std;

struct NODE {
    int data;
    NODE* pNext;
};
struct LIST {
    NODE* pHead;
    NODE* pTail;
};

void KhoiTao(LIST &l) { l.pHead = l.pTail = NULL; }

NODE* TaoNode(int x) {
    NODE* p = new NODE;
    p->data = x;
    p->pNext = NULL;
    return p;
}

void ThemDau(LIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pHead == NULL) l.pHead = l.pTail = p;
    else { p->pNext = l.pHead; l.pHead = p; }
}

void ThemCuoi(LIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pHead == NULL) l.pHead = l.pTail = p;
    else { l.pTail->pNext = p; l.pTail = p; }
}

void Xuat(LIST l) {
    for (NODE* p = l.pHead; p != NULL; p = p->pNext)
        cout << p->data << " -> ";
    cout << "NULL\n";
}

void XoaDau(LIST &l) {
    if (l.pHead == NULL) return;
    NODE* p = l.pHead;
    l.pHead = l.pHead->pNext;
    if (l.pHead == NULL) l.pTail = NULL;
    delete p;
}

void SapXep(LIST &l) {
    if (l.pHead == NULL || l.pHead == l.pTail) return;
    for (NODE* p = l.pHead; p != NULL; p = p->pNext)
        for (NODE* q = p->pNext; q != NULL; q = q->pNext)
            if (p->data > q->data) {
                int t = p->data; p->data = q->data; q->data = t;
            }
}

void HuyDanhSach(LIST &l) {
    while (l.pHead != NULL) XoaDau(l);
}

int main() {
    LIST l;
    KhoiTao(l);
    ThemCuoi(l, TaoNode(40));
    ThemCuoi(l, TaoNode(10));
    ThemCuoi(l, TaoNode(30));
    ThemCuoi(l, TaoNode(20));
    ThemDau(l, TaoNode(5));
    cout << "Truoc sort: "; Xuat(l);     // 5 -> 40 -> 10 -> 30 -> 20 -> NULL
    SapXep(l);
    cout << "Sau sort:   "; Xuat(l);     // 5 -> 10 -> 20 -> 30 -> 40 -> NULL
    XoaDau(l);
    cout << "Sau xoa dau:"; Xuat(l);     // 10 -> 20 -> 30 -> 40 -> NULL
    HuyDanhSach(l);
    return 0;
}

Kết quả kỳ vọng:

Truoc sort: 5 -> 40 -> 10 -> 30 -> 20 -> NULL
Sau sort:   5 -> 10 -> 20 -> 30 -> 40 -> NULL
Sau xoa dau:10 -> 20 -> 30 -> 40 -> NULL

3.3.3. Sắp xếp danh sách

Sắp xếp trên DSLK khác sắp xếp trên mảng:

Trên mảng	Trên DSLK
`a[i]`, `a[j]` $O(1)$	Không có chỉ số — Quick Sort “chia theo pivot index” khó viết
Swap 2 phần tử $O(1)$	Swap giá trị $O(1)$ ; swap nút (relink) phức tạp hơn
Merge Sort tốn mảng phụ $O(n)$	Merge Sort rất hợp: trộn bằng sửa con trỏ, không cần mảng phụ

Hai chiến lược:

Hoán đổi data — đúng đề thi và giáo trình thực hành (“sắp xếp bằng hoán đổi giá trị”). Nút đứng yên, số bên trong đổi chỗ.
Relink nút — đổi dây pNext, không copy data. Dùng khi data là struct lớn.

A. Đổi chỗ trực tiếp — hàm `SapXep` đúng giáo trình / đề thi

Đây không phải Selection Sort. Giáo trình lồng hai vòng: với mỗi p, so với mọi q phía sau; hễ p->data > q->data thì đổi ngay.

Ý tưởng tiếng Việt: “Người đứng ở p nhìn hết những người phía sau. Gặp ai nhỏ hơn mình thì đổi số với người đó, rồi nhìn tiếp.”

Mã giả:

THUẬT TOÁN SapXep(l)                       // tang dan, doi cho truc tiep
nếu rỗng hoặc 1 nút thì return
p ← l.pHead
while p ≠ NULL
    q ← p.pNext
    while q ≠ NULL
        nếu p.data > q.data thì hoán đổi p.data ↔ q.data
        q ← q.pNext
    p ← p.pNext

void SapXep(LIST &l) {     // dung dung ten + dung dung giai thuat giao trinh
    if (l.pHead == NULL || l.pHead == l.pTail) return;
    NODE* p = l.pHead;
    while (p != NULL) {
        NODE* q = p->pNext;
        while (q != NULL) {
            if (p->data > q->data) {
                int temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->pNext;
        }
        p = p->pNext;
    }
}

Chạy tay 40 → 10 → 30 → 20 — bắt buộc nhớ: sau mỗi lần đổi, p->data đã đổi, vòng trong so tiếp với giá trị mới:

Ban đầu:  40 → 10 → 30 → 20

Vòng `p` (nút, không phải số)	Việc xảy ra trong vòng trong	List sau vòng
Nút 1 (đang 40)	40>10 đổi → nút 1 thành 10; 10>30? không; 10>20? không	10 → 40 → 30 → 20
Nút 2 (đang 40)	40>30 đổi → 30; 30>20 đổi → 20	10 → 20 → 40 → 30
Nút 3 (đang 40)	40>30 đổi	10 → 20 → 30 → 40
Nút 4 (đang 40)	không còn `q`	10 → 20 → 30 → 40

Sai nếu viết “nút 1 đổi với cả 10, 30 và 20”: sau lần đổi đầu, nút 1 đã là 10, không còn là 40.

Thời gian $O(n^2)$ , không gian $O(1)$ .
Giảm dần: đổi > thành <.
Nút không bị cắt/nối; pHead/pTail giữ nguyên địa chỉ.

Khác Selection Sort: Selection tìm một min rồi swap một lần mỗi vòng ngoài. Đổi chỗ trực tiếp có thể swap nhiều lần trong một vòng. Đề thi yêu cầu bản đổi chỗ trực tiếp ở trên — đừng nộp nhầm Selection trừ khi đề nói “chọn phần tử nhỏ nhất”.

void SapXepChon(LIST &l) {          // bien the: selection, khong phai de mau
    for (NODE* p = l.pHead; p != NULL; p = p->pNext) {
        NODE* min = p;
        for (NODE* q = p->pNext; q != NULL; q = q->pNext)
            if (q->data < min->data) min = q;
        if (min != p) {
            int tmp = p->data; p->data = min->data; min->data = tmp;
        }
    }
}

B. Bubble Sort trên DSLK

Ý tưởng: chỉ so hai nút kề nhau. Số lớn “nổi” dần về cuối, giống bọt nước. Khác mục A: mục A so p với cả đoạn sau; Bubble chỉ so p với p->pNext.

Mỗi lượt duyệt: nếu p->data > p->pNext->data thì đổi. Lặp đến khi một lượt không còn đổi nào.

void BubbleSort(LIST &l) {
    if (l.pHead == NULL) return;
    bool swapped;
    do {
        swapped = false;
        for (NODE* p = l.pHead; p->pNext != NULL; p = p->pNext) {
            if (p->data > p->pNext->data) {
                int tmp = p->data;
                p->data = p->pNext->data;
                p->pNext->data = tmp;
                swapped = true;
            }
        }
    } while (swapped);
}

$O(n^2)$ , ổn định nếu chỉ swap khi >. Dùng để hiểu; thi thì viết SapXep mục A.

C. Insertion Sort bằng relink nút — $O(n^2)$ , hợp DSLK

Ý tưởng: dựng một list sorted ban đầu rỗng. Mỗi lần cắt nút đầu của list gốc, cắm vào đúng chỗ trong sorted (như sắp bài trên tay).

Gốc:     30 → 10 → 40 → 20
sorted:  (rỗng)

Lấy 30:  sorted = 30
Lấy 10:  10 nhỏ hơn 30 → cắm đầu → 10 → 30
Lấy 40:  40 lớn hơn 30 → cắm cuối → 10 → 30 → 40
Lấy 20:  10 < 20 < 30 → cắm giữa → 10 → 20 → 30 → 40

Chèn nút đã cầm sẵn chỉ $O(1)$ phép gán con trỏ; thời gian chủ yếu là tìm chỗ $O(n)$ .

void InsertionSortRelink(LIST &l) {
    NODE* sorted = NULL;
    NODE* cur = l.pHead;
    while (cur != NULL) {
        NODE* next = cur->pNext;
        if (sorted == NULL || cur->data <= sorted->data) {
            cur->pNext = sorted;
            sorted = cur;
        } else {
            NODE* p = sorted;
            while (p->pNext != NULL && p->pNext->data < cur->data)
                p = p->pNext;
            cur->pNext = p->pNext;
            p->pNext = cur;
        }
        cur = next;
    }
    l.pHead = sorted;
    l.pTail = sorted;
    if (l.pTail != NULL) {
        while (l.pTail->pNext != NULL)
            l.pTail = l.pTail->pNext;
    }
}

Ổn định. Rất tốt khi dữ liệu gần như đã sắp.

D. Trộn hai danh sách đã sắp — $O(n+m)$ (mẫu đề thi)

l1:  ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
     │  1 │  ●─┼───►│  4 │  ●─┼───►│  7 │  / │
     └────┴────┘    └────┴────┘    └────┴────┘
l2:  ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
     │  2 │  ●─┼───►│  3 │  ●─┼───►│  8 │  / │
     └────┴────┘    └────┴────┘    └────┴────┘

So từng cặp đầu list: 1≤2 lấy 1; 4>2 lấy 2; 4>3 lấy 3; 4≤8 lấy 4; 7≤8 lấy 7; còn 8.

l3:  ┌───┬──┐ ┌───┬──┐ ┌───┬──┐ ┌───┬──┐ ┌───┬──┐ ┌───┬──┐
     │ 1 │●─┼►│ 2 │●─┼►│ 3 │●─┼►│ 4 │●─┼►│ 7 │●─┼►│ 8 │/ │
     └───┴──┘ └───┴──┘ └───┴──┘ └───┴──┘ └───┴──┘ └───┴──┘

Mã giả (tạo list mới, không phá l1, l2):

THUẬT TOÁN Noi(l1, l2, l3)
KhoiTao(l3)
p ← l1.pHead, q ← l2.pHead
while p ≠ NULL và q ≠ NULL
    nếu p.data ≤ q.data
        ThemCuoi(l3, TaoNode(p.data)); p ← p.pNext
    ngược lại
        ThemCuoi(l3, TaoNode(q.data)); q ← q.pNext
while p ≠ NULL: ThemCuoi(l3, TaoNode(p.data)); p ← p.pNext
while q ≠ NULL: ThemCuoi(l3, TaoNode(q.data)); q ← q.pNext

void Noi(LIST l1, LIST l2, LIST &l3) {
    KhoiTao(l3);
    NODE* p = l1.pHead;
    NODE* q = l2.pHead;
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            ThemCuoi(l3, TaoNode(p->data));
            p = p->pNext;
        } else {
            ThemCuoi(l3, TaoNode(q->data));
            q = q->pNext;
        }
    }
    while (p != NULL) { ThemCuoi(l3, TaoNode(p->data)); p = p->pNext; }
    while (q != NULL) { ThemCuoi(l3, TaoNode(q->data)); q = q->pNext; }
}

Nếu đề cho phép tái sử dụng nút (không TaoNode), dùng relink: mỗi bước cắt nút nhỏ hơn gắn vào l3. $O(1)$ phụ, nhưng l1/l2 bị rỗng sau khi trộn.

E. Merge Sort trên DSLK — thuật toán “cao cấp” nên dùng thật

Trên mảng, Merge Sort tốn mảng phụ. Trên DSLK, trộn bằng con trỏ nên đây là lựa chọn $O(n \log n)$ tự nhiên nhất.

Chia — trị — trộn, ví dụ 40 → 10 → 30 → 20:

            40 → 10 → 30 → 20
           /                  \
      40 → 10              30 → 20
      /      \              /     \
    40        10          30       20
      \      /              \     /
      10 → 40              20 → 30
           \                  /
            10 → 20 → 30 → 40

Chia: tìm nút giữa bằng hai con trỏ chậm/nhanh (slow đi 1, fast đi 2), cắt mid->pNext = NULL. Trị: gọi đệ quy từng nửa. Trộn: giống mục D nhưng relink nút, không TaoNode lại.

NODE* TimGiua(NODE* head) {
    NODE* slow = head;
    NODE* fast = head;
    while (fast->pNext != NULL && fast->pNext->pNext != NULL) {
        slow = slow->pNext;
        fast = fast->pNext->pNext;
    }
    return slow;
}

NODE* MergeRelink(NODE* a, NODE* b) {
    if (a == NULL) return b;
    if (b == NULL) return a;
    NODE dummy;
    NODE* tail = &dummy;
    dummy.pNext = NULL;
    while (a != NULL && b != NULL) {
        if (a->data <= b->data) {
            tail->pNext = a;
            a = a->pNext;
        } else {
            tail->pNext = b;
            b = b->pNext;
        }
        tail = tail->pNext;
    }
    tail->pNext = (a != NULL) ? a : b;
    return dummy.pNext;
}

NODE* MergeSortNodes(NODE* head) {
    if (head == NULL || head->pNext == NULL) return head;
    NODE* mid  = TimGiua(head);
    NODE* half = mid->pNext;
    mid->pNext = NULL;
    NODE* left  = MergeSortNodes(head);
    NODE* right = MergeSortNodes(half);
    return MergeRelink(left, right);
}

void MergeSortList(LIST &l) {
    l.pHead = MergeSortNodes(l.pHead);
    l.pTail = l.pHead;
    if (l.pTail != NULL)
        while (l.pTail->pNext != NULL)
            l.pTail = l.pTail->pNext;
}

	Thời gian	Không gian (stack đệ quy)
Selection / Bubble / Insertion	$O(n^2)$	$O(1)$
Merge Sort	$O(n \log n)$	$O(\log n)$

Không dùng binary search sau khi sort DSLK: mỗi lần “lấy phần tử giữa” đã tốn $O(n)$ → tổng trở thành $O(n)$ chẳng hơn linear search.

F. Ưu / nhược khi sắp xếp trên DSLK

Ưu: Merge Sort không cần mảng phụ; insertion bằng relink không dồn phần tử.

Nhược: không Quick Sort-index; không Heap Sort (heap cần truy cập cha/con theo chỉ số); cache kém nên $O(n \log n)$ trên DSLK thường chậm hơn $O(n \log n)$ trên mảng.

Kiểm tra đã tăng dần (bài tập thực hành hay hỏi):

bool DaTangDan(LIST l) {
    if (l.pHead == NULL) return true;
    for (NODE* p = l.pHead; p->pNext != NULL; p = p->pNext)
        if (p->data > p->pNext->data) return false;
    return true;
}

$O(n)$ . Một cặp lệch là đủ kết luận “chưa sort”.

✅ Kiểm tra nhanh 3.3

ThemDau phải gán p->pNext = pHead trước hay pHead = p trước? Vì sao?
Có pTail thì thêm cuối $O(?)$ , xóa cuối $O(?)$ .
Đề thi SapXep dùng thuật toán nào: đổi chỗ trực tiếp hay Selection?
Noi yêu cầu hai list đầu vào điều kiện gì?

Đáp án: (1) Gán p->pNext trước, không thì mất list cũ. (2) $O(1)$ và $O(n)$ . (3) Đổi chỗ trực tiếp (hai vòng, gặp lớn hơn thì swap ngay) — đúng code giáo trình. (4) Cả hai đã sắp cùng chiều.

3.4. MỘT SỐ DSLK KHÁC

DSLK đơn (mục 3.3) đủ cho gần hết bài tập và đề thi. Nó còn hai hạn chế, mỗi hạn chế sinh ra một biến thể:

Hạn chế của DSLK đơn	Hệ quả cụ thể	Biến thể giải quyết
Mỗi nút chỉ biết nút sau (`pNext`)	Không đi lùi; xóa cuối $O(n)$ ; thêm/xóa trước một nút đang cầm phải duyệt lại từ `pHead`	DSLK kép — thêm `pPrev`
Nút cuối trỏ `NULL` — list thẳng, có điểm dừng	Không mô tả dữ liệu tuần hoàn; muốn “đi hết một vòng rồi quay lại” phải tự nhảy về `pHead`	DSLK vòng — nút cuối trỏ về đầu

Lộ trình học 3.4 (đừng nhảy cóc):

3.4.1 kép   =  DSLK đơn + một con trỏ ngược   (vẫn thẳng, vẫn có NULL)
3.4.2 vòng  =  đổi điều kiện dừng              (đuôi nắm đầu, không còn NULL)
vòng kép    =  ghép cả hai ý trên

Khuôn mỗi thao tác giống 3.3: ý tưởng → sơ đồ trước/sau → mã giả → code → $O$ → bẫy.

Học kép trước vì cấu trúc nút đổi, nhưng điều kiện duyệt vẫn là p != NULL. Học vòng sau vì cấu trúc nút không đổi so với đơn, nhưng điều kiện duyệt đổi hẳn — chỗ này dễ vòng lặp vô hạn nếu hấp tấp.

3.4.1. DSLK kép (Doubly Linked List)

A. Vì sao cần kép? Định nghĩa

Ẩn dụ. DSLK đơn như hàng người chỉ nắm vai người phía trước: biết ai đứng sau, không biết ai đứng trước. Muốn xóa người cuối, phải đi từ đầu hàng hỏi từng người “bạn có phải người áp chót không?”.

DSLK kép như hàng người nắm hai tay: tay phải nắm người sau (pNext), tay trái nắm người trước (pPrev). Đứng ở bất kỳ chỗ nào cũng bước tới hoặc bước lùi được một bước.

Định nghĩa. Danh sách liên kết kép là danh sách liên kết trong đó mỗi nút chứa:

data — thông tin.
pNext — địa chỉ nút đứng sau (giống DSLK đơn).
pPrev — địa chỉ nút đứng trước (điểm mới).

Hai đầu danh sách thẳng vẫn kết thúc bằng NULL:

Nút đầu: pPrev = NULL (không có ai đứng trước).
Nút cuối: pNext = NULL (không có ai đứng sau).

      pHead                                              pTail
        │                                                  │
        ▼                                                  ▼
   ┌────┬────┬────┐     ┌────┬────┬────┐     ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼────►│  ● │ 20 │  ●─┼────►│  ● │ 30 │  / │────► NULL
   │    │    │    │◄────┼─●  │    │    │◄────┼─●  │    │    │
   └────┴────┴────┘     └────┴────┴────┘     └────┴────┴────┘
     prev data next       prev data next       prev data next
     ▲
     └── NULL (không có nút trước 10)

 Quy ước vẽ xuyên 3.4.1:
   cột trái  = pPrev     cột giữa = data     cột phải = pNext
   mũi tên ──► đi xuôi     mũi tên ◄── đi ngược
   /  nghĩa là NULL

Quy tắc đối xứng (thuộc lòng):

Nếu  A.pNext = B     thì bắt buộc     B.pPrev = A
Nếu  B.pPrev = A     thì bắt buộc     A.pNext = B

Một chiều đứt, chiều kia còn → list hỏng, duyệt xuôi ra một thứ, duyệt ngược ra thứ khác. Đây là nguồn bug số 1 của DSLK kép.

Ba việc DSLK đơn làm kém, kép làm tốt:

Việc	DSLK đơn (đã cầm con trỏ tới nút)	DSLK kép
Đi lùi một bước	Không — phải duyệt lại từ `pHead`	`p = p->pPrev` — $O(1)$
Xóa chính nút đang cầm	Phải tìm nút trước → $O(n)$	Sửa 2 liên kết → $O(1)$
Xóa cuối (có `pTail`)	Phải tìm nút áp chót → $O(n)$	`pTail->pPrev` chính là áp chót → $O(1)$

Giá phải trả: mỗi nút thêm một con trỏ; mỗi thao tác sửa nhiều liên kết hơn.

B. Tổ chức `DNODE` / `DLIST` và bất biến

Khai báo cùng phong cách NODE / LIST của mục 3.3, chỉ thêm pPrev. Tên DNODE/DLIST để khỏi lẫn với đơn khi cả hai cùng nằm trong một file.

struct DNODE {
    int data;
    DNODE* pPrev;    // nut dung truoc — NULL neu la dau
    DNODE* pNext;    // nut dung sau  — NULL neu la cuoi
};

struct DLIST {
    DNODE* pHead;
    DNODE* pTail;
};

 struct DNODE                         struct DLIST
 ┌──────┬──────┬──────┐               ┌────────┬────────┐
 │pPrev │ data │pNext │               │ pHead  │ pTail  │
 └──────┴──────┴──────┘               └────────┴────────┘
     ▲       ▲      ▲                      │         │
     │       │      └── giống DSLK đơn     │         └──► nút cuối
     │       └── thông tin                 └──────────► nút đầu
     └── CHỈ CÓ Ở KÉP

Khởi tạo rỗng và tạo nút — nút mới đứng một mình: cả hai con trỏ đều NULL.

THUẬT TOÁN KhoiTaoD(l)
l.pHead ← NULL
l.pTail ← NULL

THUẬT TOÁN TaoDNode(x) → p
p ← cấp phát một DNODE
p.data  ← x
p.pPrev ← NULL
p.pNext ← NULL
Trả về p

void KhoiTaoD(DLIST &l) {
    l.pHead = l.pTail = NULL;
}

bool IsEmptyD(DLIST l) {
    return l.pHead == NULL;
}

DNODE* TaoDNode(int x) {
    DNODE* p = new DNODE;
    p->data  = x;
    p->pPrev = p->pNext = NULL;   // nut moi chua noi ai, chua ai noi
    return p;
}

  TaoDNode(10) trả về p:

    p
    │
    ▼
 ┌────┬────┬────┐
 │ /  │ 10 │  / │     ← hộp đứng một mình
 └────┴────┴────┘
  prev data next

Bốn bất biến (invariant) — phải đúng sau MỌI thao tác:

#	Bất biến	Ý nghĩa
1	Rỗng ⇔ `pHead == NULL` và `pTail == NULL`	Không được một bên NULL, một bên còn trỏ
2	Nếu không rỗng: `pHead->pPrev == NULL`	Đầu không có người trước
3	Nếu không rỗng: `pTail->pNext == NULL`	Cuối không có người sau
4	Với mọi cặp kề: `a->pNext == b` ⇔ `b->pPrev == a`	Hai chiều luôn khớp

Hàm kiểm tra (dùng khi debug, không cần thuộc để thi):

bool HopLeKep(DLIST l) {
    if (l.pHead == NULL)
        return l.pTail == NULL;          // bat bien 1
    if (l.pTail == NULL) return false;
    if (l.pHead->pPrev != NULL) return false;   // bat bien 2
    if (l.pTail->pNext != NULL) return false;   // bat bien 3

    DNODE* p = l.pHead;
    while (p->pNext != NULL) {
        if (p->pNext->pPrev != p) return false; // bat bien 4
        p = p->pNext;
    }
    return p == l.pTail;                 // di xuoi phai dung dung pTail
}

Quy tắc vàng khi sửa kép: mỗi lần “cắt–nối”, hãy hỏi: mình đã sửa đủ cả hai phía của mỗi mối nối chưa? Một mối nối $A \leftrightarrow B$ cần hai phép gán: A->pNext = B và B->pPrev = A.

C. Dựng list và duyệt hai chiều

Dựng [10]↔[20]↔[30] bằng thêm cuối — nhìn từng bước để thuộc pHead/pTail.

Bước 0 — rỗng:

 pHead ──► NULL     pTail ──► NULL

Bước 1 — thêm 10 (list rỗng: đầu = cuối = nút mới, hai con trỏ vẫn NULL):

      pHead, pTail
           │
           ▼
      ┌────┬────┬────┐
      │ /  │ 10 │  / │──► NULL
      └────┴────┴────┘

Bước 2 — thêm 20 (nối hai chiều giữa 10 và 20, dời pTail):

      pHead              pTail
        │                  │
        ▼                  ▼
   ┌────┬────┬────┐   ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼──►│  ● │ 20 │  / │──► NULL
   │    │    │    │◄──┼─●  │    │    │
   └────┴────┴────┘   └────┴────┴────┘

Bước 3 — thêm 30:

      pHead                                 pTail
        │                                     │
        ▼                                     ▼
   ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │──► NULL
   │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
   └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘

Trên RAM ba nút không cần liền kề. Logic 10↔20↔30 nhờ hai con trỏ mỗi cặp, không nhờ địa chỉ tăng dần.

Duyệt xuôi — giống DSLK đơn, từ pHead theo pNext đến NULL.

Duyệt ngược — việc đơn không làm được (trừ khi dùng stack phụ): từ pTail theo pPrev đến NULL.

THUẬT TOÁN XuatXuoi(l)
p ← l.pHead
while p ≠ NULL
    in p.data
    p ← p.pNext

THUẬT TOÁN XuatNguoc(l)
p ← l.pTail
while p ≠ NULL
    in p.data
    p ← p.pPrev

void XuatXuoi(DLIST l) {
    cout << "Xuoi : ";
    for (DNODE* p = l.pHead; p != NULL; p = p->pNext)
        cout << p->data << " ";
    cout << "\n";
}

void XuatNguoc(DLIST l) {
    cout << "Nguoc: ";
    for (DNODE* p = l.pTail; p != NULL; p = p->pPrev)
        cout << p->data << " ";
    cout << "\n";
}

int DemSoPhanTuKep(DLIST l) {
    int dem = 0;
    for (DNODE* p = l.pHead; p != NULL; p = p->pNext)
        dem++;
    return dem;
}

DNODE* TimKep(DLIST l, int x) {
    for (DNODE* p = l.pHead; p != NULL; p = p->pNext)
        if (p->data == x) return p;
    return NULL;
}

List [10]↔[20]↔[30]:

 XuatXuoi  →  10  20  30
 XuatNguoc →  30  20  10

Thao tác	Thời gian	Không gian
Xuôi / ngược / đếm / tìm	$O(n)$	$O(1)$

Tìm kiếm vẫn $O(n)$ . Có pPrev không giúp nhảy giữa list; không có a[i].

Bẫy duyệt:

Dùng p->pNext != NULL khi muốn in mọi nút → bỏ nút cuối (giống đơn).
Duyệt ngược nhưng xuất phát từ pHead rồi p = p->pPrev → vòng không chạy (head.prev đã NULL) hoặc crash nếu quên kiểm tra rỗng.
Tìm từ hai đầu “cho nhanh” vẫn $O(n)$ — chỉ giảm hằng số, đề thi không đòi.

D. Thêm đầu / thêm cuối — cả hai $O(1)$

① Thêm đầu — $O(1)$

Ý tưởng. Nút mới trở thành người đứng đầu hàng: nó nắm pHead cũ bằng pNext; pHead cũ nắm nó bằng pPrev; cửa pHead chuyển sang nút mới.

Trường hợp rỗng — không có “head cũ” để sửa pPrev:

 Trước:  pHead ──► NULL    pTail ──► NULL

 Sau (thêm 10):
      pHead, pTail
           │
           ▼
      ┌────┬────┬────┐
      │ /  │ 10 │  / │
      └────┴────┴────┘

Trường hợp đã có nút — 4 phép, đúng thứ tự ①② rồi mới ③④:

 TRƯỚC                    p (nút 10, chưa nối)
      pHead    pTail         │
        │        │           ▼
        ▼        ▼        ┌────┬────┬────┐
   ┌────┬────┬────┐  ┌────┬────┬────┐  │ /  │ 10 │  / │
   │ /  │ 20 │  ●─┼─►│  ● │ 30 │  / │  └────┴────┴────┘
   │    │    │    │◄─┼─●  │    │    │
   └────┴────┴────┘  └────┴────┴────┘

 ① p->pNext = pHead      (10 nắm 20 — GIỮ list cũ trước khi dời cửa)
 ② p->pPrev = NULL       (10 là đầu mới, không ai đứng trước)
 ③ pHead->pPrev = p      (20.prev nhớ 10 — ĐÂY LÀ PHÉP ĐƠN KHÔNG CÓ)
 ④ pHead = p             (cửa vào chuyển sang 10)
    pTail không đổi

 SAU
      pHead                                 pTail
        │                                     │
        ▼                                     ▼
   ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │
   │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
   └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘

Mã giả:

THUẬT TOÁN ThemDauKep(l, p)
Vào: p là nút mới, pPrev = pNext = NULL
nếu l.pHead = NULL
    l.pHead ← p
    l.pTail ← p
    return
p.pNext ← l.pHead
p.pPrev ← NULL
l.pHead.pPrev ← p      // head cũ nhớ người mới đứng trước
l.pHead ← p

void ThemDauKep(DLIST &l, DNODE* p) {
    if (p == NULL) return;
    if (l.pHead == NULL) {
        l.pHead = l.pTail = p;
        return;
    }
    p->pNext = l.pHead;       // ①
    p->pPrev = NULL;          // ②  (TaoDNode da lam, ghi lai cho ro)
    l.pHead->pPrev = p;       // ③
    l.pHead = p;              // ④
}

void ThemDauKepGiaTri(DLIST &l, int x) {
    ThemDauKep(l, TaoDNode(x));
}

Bẫy: quên bước ③ → duyệt xuôi 10 → 20 → 30 đúng, duyệt ngược từ 20 đi về gặp NULL thay vì 10. “Nửa list”.
Bẫy: làm ④ trước ① → mất địa chỉ head cũ, rò rỉ cả list (giống bẫy ThemDau đơn).

$O(1)$ — không duyệt.

② Thêm cuối — $O(1)$

Ý tưởng. Đối xứng thêm đầu: nắm pTail thay vì pHead. Nút mới đứng sau người cuối; người cuối nắm nó bằng pNext; nó nắm người cuối bằng pPrev; cửa pTail chuyển sang nút mới.

 TRƯỚC
      pHead          pTail              p (nút 30)
        │              │                │
        ▼              ▼                ▼
   ┌────┬────┬────┐   ┌────┬────┬────┐     ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼──►│  ● │ 20 │  / │     │ /  │ 30 │  / │
   │    │    │    │◄──┼─●  │    │    │     └────┴────┴────┘
   └────┴────┴────┘   └────┴────┴────┘

 ① p->pPrev = pTail      (30 nắm 20)
 ② p->pNext = NULL       (30 là cuối mới)
 ③ pTail->pNext = p      (20 nắm 30)
 ④ pTail = p             (cửa cuối chuyển sang 30)

 SAU
      pHead                                 pTail
        │                                     │
        ▼                                     ▼
   ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
   │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │
   │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
   └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘

THUẬT TOÁN ThemCuoiKep(l, p)
nếu l.pTail = NULL
    l.pHead ← p
    l.pTail ← p
    return
p.pPrev ← l.pTail
p.pNext ← NULL
l.pTail.pNext ← p
l.pTail ← p

void ThemCuoiKep(DLIST &l, DNODE* p) {
    if (p == NULL) return;
    if (l.pTail == NULL) {
        l.pHead = l.pTail = p;
        return;
    }
    p->pPrev = l.pTail;
    p->pNext = NULL;
    l.pTail->pNext = p;
    l.pTail = p;
}

Nhìn đối xứng để nhớ, đừng học vẹt hai hàm rời:

	Thêm đầu	Thêm cuối
Nút mới nắm phía list	`p->pNext = pHead`	`p->pPrev = pTail`
Nút mới phía còn lại	`p->pPrev = NULL`	`p->pNext = NULL`
Nút cũ nhớ nút mới	`pHead->pPrev = p`	`pTail->pNext = p`
Dời cửa	`pHead = p`	`pTail = p`

$O(1)$ với pTail. Không có pTail thì thêm cuối vẫn $O(n)$ — phải đi đến nút có pNext == NULL.

E. Thêm sau / thêm trước / thêm tại vị trí

③ Thêm sau nút `q` — $O(1)$ nếu đã cầm `q`

Ý tưởng. Chèn p vào khe giữa q và q->pNext. Bốn mối nối: $q \leftrightarrow p$ và $p \leftrightarrow$ (nút sau cũ). Nếu q đang là tail thì không có nút sau → p thành tail mới.

 TRƯỚC   q cầm 20, thêm p = 25
      ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │
      │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
      └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘
                           q

 ┌─────────────────────────────────────────────────────────────────┐
 │  HIỂU CÚ PHÁP TRƯỚC KHI ĐỌC CÁC BƯỚC                         │
 │                                                                 │
 │  p->pNext = q->pNext  đọc từ PHẢI sang TRÁI:                   │
 │                                                                 │
 │    q->pNext  =  "lấy địa chỉ đang chứa trong ô pNext của q"   │
 │                  → q là nút 20, q->pNext đang GIỮ địa chỉ 30  │
 │                                                                 │
 │    p->pNext  =  "ghi địa chỉ đó vào ô pNext của p"            │
 │                  → p là nút 25 mới, pNext của 25 = địa chỉ 30 │
 │                                                                 │
 │  Kết quả: cả 20 và 25 đều "biết" chỗ của 30.                  │
 │  (Không viết p->pNext = 30 vì 30 là giá trị dữ liệu,          │
 │   địa chỉ của nút 30 chỉ q->pNext mới đang giữ.)              │
 │                                                                 │
 │  Hình dung: A(20) đang cầm số ĐT của C(30).                   │
 │  B(25) mới vào → hỏi A: "cho tao số C" = p->pNext = q->pNext  │
 │  Bây giờ cả A và B đều có số của C.                            │
 │  Sau đó A xóa số C, lưu số B = q->pNext = p  (bước ③)        │
 │  B vẫn còn số C → chuỗi không bị đứt.                         │
 └─────────────────────────────────────────────────────────────────┘

 Cách nhớ: "nút MỚI (25) lo xong việc của mình TRƯỚC,
 rồi mới bảo các nút CŨ cập nhật lại":

   Bước ①②  → nút 25 tự nối hai đầu của mình vào đúng vị trí
   Bước ③④  → nút 20 và nút 30 "quay sang" nhận 25 là hàng xóm mới

 Vì sao ① phải trước ③?
   Nếu làm ③ trước (q->pNext = p), thì q->pNext bị ghi đè = 25,
   mất luôn địa chỉ 30. Bước ① không còn biết 30 ở đâu → chuỗi đứt.
   → Luôn "cầm địa chỉ 30" (①) trước khi "cắt dây 20→30" (③).

 Thứ tự BẮT BUỘC — giữ 30 trước khi cắt 20.next:

 Trạng thái ban đầu:     10 ←→ [20] ←→ 30       p=25 lơ lửng
                                  q

 ① p->pNext = q->pNext   10 ←→ [20] ←→ 30
   (25 nắm địa chỉ 30)            q        ↑
                                  [25]─────┘   25.next → 30

 ② p->pPrev = q          10 ←→ [20] ←→ 30
   (25.prev = địa chỉ 20)         q        ↑
                         20 ←─ [25]────────┘   25 hai chiều xong

 ③ q->pNext = p          10 ←→ [20] ──► [25] ──► 30
   (20 trỏ sang 25)               q       p     20 đã trỏ 25

 ④ p->pNext->pPrev = p   10 ←→ [20] ←→ [25] ←→ 30   ✓ hoàn chỉnh
   (30.prev = địa chỉ 25)         q       p

 SAU
      ┌────┬────┬────┐  ┌────┬────┬────┐  ┌────┬────┬────┐  ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼─►│  ● │ 20 │  ●─┼─►│  ● │ 25 │  ●─┼─►│  ● │ 30 │  / │
      │    │    │    │◄─┼─●  │    │    │◄─┼─●  │    │    │◄─┼─●  │    │    │
      └────┴────┴────┘  └────┴────┴────┘  └────┴────┴────┘  └────┴────┴────┘
                          q                 p

THUẬT TOÁN ThemSauKep(l, q, p)
Vào: q ≠ NULL, p là nút mới
p.pNext ← q.pNext
p.pPrev ← q
q.pNext ← p
nếu p.pNext ≠ NULL
    p.pNext.pPrev ← p
ngược lại
    l.pTail ← p

void ThemSauKep(DLIST &l, DNODE* q, DNODE* p) {
    if (q == NULL || p == NULL) return;
    p->pNext = q->pNext;
    p->pPrev = q;
    q->pNext = p;
    if (p->pNext != NULL)
        p->pNext->pPrev = p;
    else
        l.pTail = p;
}

Bẫy: làm ③ trước ① → mất địa chỉ 30, không gán được ④, đứt đuôi.
Bẫy: quên nhánh else pTail = p khi chèn sau tail → pTail còn trỏ 20, xuất xuôi in được 25 nhưng các hàm dựa vào pTail (thêm cuối, xóa cuối, xuất ngược) sai.

④ Thêm trước nút `q` — $O(1)$ ← thắng lợi so với đơn $O(n)$

Ý tưởng. DSLK đơn không có pPrev nên phải tìm nút đứng trước q ( $O(n)$ ). Kép đã cầm q->pPrev sẵn: thêm trước q = thêm sau q->pPrev. Nếu q là head thì gọi ThemDauKep.

 TRƯỚC   q cầm 20, thêm p = 15  (chèn giữa 10 và 20)
      ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │
      │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
      └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘
         q->pPrev              q

  q không phải head  →  ThemSauKep(l, q->pPrev, p)
  tức là ThemSau(10, 15)

 SAU
      ┌────┬────┬────┐  ┌────┬────┬────┐  ┌────┬────┬────┐  ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼─►│  ● │ 15 │  ●─┼─►│  ● │ 20 │  ●─┼─►│  ● │ 30 │  / │
      │    │    │    │◄─┼─●  │    │    │◄─┼─●  │    │    │◄─┼─●  │    │    │
      └────┴────┴────┘  └────┴────┴────┘  └────┴────┴────┘  └────┴────┴────┘

THUẬT TOÁN ThemTruocKep(l, q, p)
nếu q = NULL thì return
nếu q = l.pHead thì ThemDauKep(l, p); return
ThemSauKep(l, q.pPrev, p)

void ThemTruocKep(DLIST &l, DNODE* q, DNODE* p) {
    if (q == NULL || p == NULL) return;
    if (q == l.pHead) {
        ThemDauKep(l, p);
        return;
    }
    ThemSauKep(l, q->pPrev, p);
}

Có thể viết bung 4 phép (đối xứng ThemSauKep) nếu đề thi bắt “không gọi hàm khác”:

 p.pPrev ← q.pPrev
 p.pNext ← q
 q.pPrev.pNext ← p     // 10 nắm 15  (an toàn vì q không phải head)
 q.pPrev ← p           // 20.prev = 15

Phân tích: tìm q nếu chỉ biết giá trị vẫn $O(n)$ ; chèn khi đã cầm q mới là $O(1)$ . Đề bài “thêm trước nút có data = x” = tìm $O(n)$ + chèn $O(1)$ .

⑤ Thêm tại vị trí $k$ (đếm từ 0)

THUẬT TOÁN ThemTaiViTriKep(l, k, p)
nếu k ≤ 0 thì ThemDauKep(l, p); return
q ← l.pHead; i ← 0
while q ≠ NULL và i < k - 1
    q ← q.pNext; i ← i + 1
nếu q = NULL thì ThemCuoiKep(l, p)     // k vượt độ dài
ngược lại ThemSauKep(l, q, p)

void ThemTaiViTriKep(DLIST &l, int k, DNODE* p) {
    if (p == NULL) return;
    if (k <= 0 || l.pHead == NULL) {
        ThemDauKep(l, p);
        return;
    }
    DNODE* q = l.pHead;
    int i = 0;
    while (q != NULL && i < k - 1) {
        q = q->pNext;
        i++;
    }
    if (q == NULL)
        ThemCuoiKep(l, p);
    else
        ThemSauKep(l, q, p);
}

Tìm vị trí $O(k)$ , chèn $O(1)$ → tổng $O(n)$ xấu nhất. Kép không làm ThemTaiViTri xuống $O(1)$ — vẫn phải đi bộ tới chỗ $k$ .

F. Xóa — lý do kép tồn tại

⑥ Xóa một nút `p` đang cầm sẵn — $O(1)$

Ý tưởng. Nút trước p và nút sau p nắm lấy nhau, bỏ p ra khỏi chuỗi, rồi delete p. Không cần tìm nút trước (đơn bắt buộc phải tìm).

Bốn nhánh, vẽ trên giấy trước khi gõ:

Nhánh	Nhận ra bằng	Việc làm
List 1 nút	`p == pHead && p == pTail`	`pHead = pTail = NULL`
Xóa đầu	`p == pHead`	`pHead = p->pNext`; `pHead->pPrev = NULL`
Xóa cuối	`p == pTail`	`pTail = p->pPrev`; `pTail->pNext = NULL`
Xóa giữa	còn lại	`p->pPrev->pNext = p->pNext`; `p->pNext->pPrev = p->pPrev`

Xóa giữa (minh họa chính):

 TRƯỚC  xóa nút 20 (đã cầm p)
      ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  / │
      │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
      └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘
                           p

 ① p->pPrev->pNext = p->pNext     (10.next ← 30)
 ② p->pNext->pPrev = p->pPrev     (30.prev ← 10)
    delete p

 SAU
      ┌────┬────┬────┐                     ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼────────────────────►│  ● │ 30 │  / │
      │    │    │    │◄────────────────────┼─●  │    │    │
      └────┴────┴────┘                     └────┴────┴────┘
        pHead                                pTail

Xóa đầu (list ≥ 2 nút):

 TRƯỚC  p = pHead = 10
      ┌────┬────┬────┐   ┌────┬────┬────┐
      │ /  │ 10 │  ●─┼──►│  ● │ 20 │  ...
      │    │    │    │◄──┼─●  │    │    │
      └────┴────┴────┘   └────┴────┴────┘
        p=pHead

  pHead = 20
  pHead->pPrev = NULL     // 20 không còn nhớ 10
  delete 10

 SAU
      pHead
        │
        ▼
   ┌────┬────┬────┐
   │ /  │ 20 │  ...
   │    │    │    │   (pPrev = NULL = /)
   └────┴────┴────┘

Xóa cuối — đối xứng, $O(1)$ (đơn phải $O(n)$ ):

 TRƯỚC  p = pTail = 30, list 10↔20↔30

  pTail = 20              // p->pPrev
  pTail->pNext = NULL     // 20 không còn nắm 30
  delete 30

THUẬT TOÁN XoaNodeKep(l, p)
nếu p = NULL hoặc list rỗng thì return
nếu p là head VÀ tail          // 1 nút
    pHead ← pTail ← NULL
ngược lại nếu p là head
    pHead ← p.pNext
    pHead.pPrev ← NULL
ngược lại nếu p là tail
    pTail ← p.pPrev
    pTail.pNext ← NULL
ngược lại
   p.pPrev.pNext ← p.pNext
   p.pNext.pPrev ← p.pPrev
delete p

void XoaNodeKep(DLIST &l, DNODE* p) {
    if (p == NULL || l.pHead == NULL) return;

    if (p == l.pHead && p == l.pTail) {
        l.pHead = l.pTail = NULL;
    } else if (p == l.pHead) {
        l.pHead = p->pNext;
        l.pHead->pPrev = NULL;
    } else if (p == l.pTail) {
        l.pTail = p->pPrev;
        l.pTail->pNext = NULL;
    } else {
        p->pPrev->pNext = p->pNext;
        p->pNext->pPrev = p->pPrev;
    }
    delete p;
}

void XoaDauKep(DLIST &l)  { XoaNodeKep(l, l.pHead); }
void XoaCuoiKep(DLIST &l) { XoaNodeKep(l, l.pTail); }   // O(1) !

Bẫy thứ tự if: phải xét 1 nút trước xóa đầu/cuối. Nếu viết if (p == pHead) { pHead = p->pNext; pHead->pPrev = NULL; } khi list 1 nút thì pHead thành NULL rồi NULL->pPrev → crash.

Bẫy: delete p rồi còn dùng p->pNext → dangling pointer.

Bẫy: xóa giữa mà chỉ sửa pPrev->pNext, quên pNext->pPrev → xuất xuôi đúng, xuất ngược đứt.

Xóa đầu / xóa cuối khi đã có con trỏ là $O(1)$ . Xóa theo giá trị vẫn phải tìm trước.

⑦ Xóa theo giá trị (nút đầu tiên có `data == x`) — $O(n)$

Tìm $O(n)$ + xóa nút đang cầm $O(1)$ .

void XoaGiaTriKep(DLIST &l, int x) {
    DNODE* p = TimKep(l, x);
    if (p != NULL)
        XoaNodeKep(l, p);
}

void XoaTaiViTriKep(DLIST &l, int k) {
    if (k < 0) return;
    DNODE* p = l.pHead;
    int i = 0;
    while (p != NULL && i < k) {
        p = p->pNext;
        i++;
    }
    if (p != NULL)
        XoaNodeKep(l, p);
}

⑧ Hủy toàn bộ — chống memory leak

void HuyDanhSachKep(DLIST &l) {
    while (l.pHead != NULL)
        XoaDauKep(l);
}

$O(n)$ . Mỗi XoaDauKep là $O(1)$ , lặp $n$ lần. Sau hàm: pHead == pTail == NULL.

Có thể viết tay không gọi XoaDauKep: giữ pNext trước khi delete, vì sau delete không được đọc p->pNext.

void HuyDanhSachKep2(DLIST &l) {
    DNODE* p = l.pHead;
    while (p != NULL) {
        DNODE* t = p->pNext;
        delete p;
        p = t;
    }
    l.pHead = l.pTail = NULL;
}

⑨ Ví dụ chạy tay cả chuỗi (kép)

List rỗng. Thực hiện: ThemCuoi 20, ThemDau 10, ThemCuoi 40, ThemSau(20, 30), XoaCuoi, XoaNode(20).

rỗng
ThemCuoi 20     →  [20]
ThemDau 10      →  [10]↔[20]
ThemCuoi 40     →  [10]↔[20]↔[40]
ThemSau(20,30)  →  [10]↔[20]↔[30]↔[40]
XoaCuoi         →  [10]↔[20]↔[30]     (O(1), đơn phải đi tìm 20)
XoaNode(20)     →  [10]↔[30]           (O(1), đơn phải đi tìm 10)
 XuatXuoi  = 10 30
 XuatNguoc = 30 10

G. So sánh đơn–kép, ưu nhược, bẫy

Bảng giá (đã cầm con trỏ tới nút cần đụng, có pHead + pTail):

Thao tác	DSLK đơn	DSLK kép
Thêm/xóa đầu	$O(1)$	$O(1)$
Thêm cuối	$O(1)$	$O(1)$
Xóa cuối	$O(n)$	$O(1)$
Thêm/xóa sau một nút	$O(1)$	$O(1)$
Thêm/xóa trước một nút	$O(n)$	$O(1)$
Xóa chính nút đang cầm	$O(n)$	$O(1)$
Duyệt xuôi	Có	Có
Duyệt ngược	Không	Có
Tìm theo giá trị / lấy thứ $k$	$O(n)$	$O(n)$
RAM mỗi nút (máy 64-bit, xấp xỉ)	~16 byte	~24 byte

Ưu điểm

Duyệt hai chiều — in ngược, so palindrome tại chỗ, đi lùi playlist.
Xóa nút đang cầm $O(1)$ — LRU, editor, kernel (struct có thể nằm trong list).
Xóa cuối $O(1)$ — deque, cache “bỏ phần tử cũ nhất”.
Thêm trước một nút $O(1)$ .
Cài deque (hai đầu) tự nhiên: mọi thao tác đầu/cuối đều $O(1)$ .

Nhược điểm

Thêm một con trỏ pPrev → tốn RAM (~+8 byte/nút trên máy 64-bit). 1000 int: đơn ~16 KB, kép ~24 KB (xem 3.5.2).
Mỗi thao tác sửa nhiều con trỏ hơn → dễ gán sai, khó debug. Một chiều đứt, chiều kia còn.
Vẫn không truy cập ngẫu nhiên $O(1)$ ; tìm kiếm vẫn $O(n)$ ; cache CPU kém hơn mảng.

Khi nào chọn kép, khi nào đủ đơn?

Chọn kép khi…	Đủ đơn khi…
Cần Back/Forward, Undo/Redo	Chỉ thêm/xóa đầu, duyệt một chiều
Cần xóa cuối / xóa nút đang cầm rất nhiều	List ngắn, RAM eo hẹp (vi điều khiển)
Cài `std::list`-like, deque, LRU	Bài tập/đề thi chỉ yêu cầu DSLK đơn

Bảng bẫy thường gặp:

Bẫy	Triệu chứng	Cách tránh
Quên sửa chiều ngược	Xuôi đúng, ngược sai	Sau mỗi thao tác chạy `HopLeKep` / `XuatNguoc`
Xét xóa đầu trước nhánh 1 nút	Crash `NULL->pPrev`	`if (head == tail)` đứng đầu
Đảo thứ tự gán khi thêm	Mất phần sau / leak	Giữ `next`/`prev` cũ trước khi ghi đè
Quên cập nhật `pTail` khi chèn/xóa cuối	Thêm cuối lần sau ghi đè sai chỗ	Mỗi nhánh đụng nút cuối phải đụng `pTail`
`delete` rồi còn đọc `p->…`	Dangling	Lưu `pNext`/`pPrev` ra biến tạm trước

H. Ứng dụng: Back/Forward, Undo/Redo, LRU, deque

Không học thuộc tên cho oai. Mỗi ứng dụng dưới đây dùng đúng một thế mạnh của kép.

1. Lịch sử trình duyệt — Back / Forward

Mỗi trang là một nút. current là trang đang xem. Back = đi pPrev, Forward = đi pNext.

Chạy tay:

 Visit A          current → [A]
 Visit B          [A]↔[B]                  current = B
 Visit C          [A]↔[B]↔[C]              current = C
 Back             current lùi về B         (không xóa C — còn Forward)
 Back             current lùi về A
 Visit D          cắt nhánh Forward (xóa C), nối D sau A
                  [A]↔[D]                  current = D
                  (B, C bị hủy — giống trình duyệt thật)

 Tại sao kép?  Back/Forward là đi lùi/tới một bước O(1).
 Visit trang mới khi đang đứng giữa: XoaNode từ current->pNext đến cuối
 rồi ThemCuoi — xóa từng nút đang cầm O(1).

2. Undo / Redo trong editor

Mỗi hành động gõ/xóa là một nút. current = trạng thái hiện tại.

 Gõ "a"           [a]                         current = a
 Gõ "b"           [a]↔[b]                     current = b
 Undo             current lùi về a            (b vẫn còn để Redo)
 Gõ "c"           cắt nhánh redo (xóa b), nối c
                  [a]↔[c]                     current = c

Cùng hình học với trình duyệt: đi lùi/tới $O(1)$ + cắt đuôi $O(\text{số nút bị bỏ})$ .

3. Deque (hàng đợi hai đầu)

Cần cả bốn thao tác $O(1)$ : thêm đầu, thêm cuối, xóa đầu, xóa cuối. DSLK đơn thất bại ở xóa cuối. DSLK kép làm đủ.

  PushFront(x)  = ThemDauKep
  PushBack(x)   = ThemCuoiKep
  PopFront()    = XoaDauKep
  PopBack()     = XoaCuoiKep     ← chỗ đơn không O(1)

std::list trong C++ STL là DSLK kép. std::deque thường là khối mảng, nhưng ADT deque cài bằng kép là cách giáo khoa.

4. LRU Cache — case study (nâng cao, nắm ý là đủ)

Bài toán. Cache dung lượng $k$ . get(key) / put(key) phải $O(1)$ . Khi đầy, vứt phần tử lâu nhất chưa dùng (Least Recently Used).

Cấu trúc: HashMap key → DNODE* (tìm nút $O(1)$ ) + DSLK kép lưu thứ tự “mới dùng”:

 pHead = MỚI dùng nhất          pTail = CŨ nhất (nạn nhân khi đầy)
    │                               │
    ▼                               ▼
  [trang X] ↔ [trang Y] ↔ [trang Z]

Ba thao tác nguyên thủy của kép, mỗi cái $O(1)$ :

Sự kiện	Làm gì trên kép
`get` trúng / `put` key đã có	`XoaNodeKep` nút đó rồi `ThemDauKep` (đưa lên đầu)
`put` key mới, cache chưa đầy	`ThemDauKep`
`put` key mới, cache đầy	`XoaCuoiKep` (vứt LRU) rồi `ThemDauKep`

Chạy tay $k = 3$ :

 put(1)     [1]                          map: 1
 put(2)     [2]↔[1]                      map: 1, 2
 put(3)     [3]↔[2]↔[1]                  đầy
 get(1)     đưa 1 lên đầu → [1]↔[3]↔[2]
 put(4)     đầy, vứt tail=2, thêm 4     [4]↔[1]↔[3]
            map xóa 2, thêm 4

 get(2) → miss (đã vứt)
 get(1) → hit, đưa 1 lên đầu            [1]↔[4]↔[3]

Không cần code HashMap trong chương này. Ý cần nắm: kép cho phép di chuyển một nút đang cầm tới đầu list trong $O(1)$ — đơn không làm được vì không biết nút trước.

5. Playlist “bài trước / bài sau”

Nút = một bài hát. current->pNext = bài sau, current->pPrev = bài trước. Nút Prev trên UI chính là pPrev. Nếu muốn hết danh sách quay lại bài đầu → nâng thành vòng kép (mục 3.4.2.E).

3.4.2. DSLK vòng (Circular Linked List)

A. Vì sao cần vòng? Tổ chức chỉ giữ `pTail`

Ẩn dụ. DSLK đơn/kép thẳng như hàng người có người đầu và người cuối; người cuối không nắm ai (NULL). DSLK vòng như người ngồi quanh bàn: người cuối nắm vai người đầu. Đi mãi sẽ gặp lại chỗ xuất phát — không có “điểm dừng NULL”.

Dữ liệu nào cần vòng? Thứ tự tuần hoàn, không có “phần tử cuối” về nghĩa logic:

CPU chia time-slice cho $P_1, P_2, \ldots, P_n$ rồi quay lại $P_1$ (round-robin).
Playlist bật “lặp danh sách”.
Trò chơi đi vòng quanh bàn, bài toán Josephus.
Token ring: token đi hết trạm rồi về trạm 0.

Ép những bài này vào DSLK thẳng cũng được, nhưng mỗi lần hết list phải tự viết p = pHead — dễ quên, và không còn tính chất “đứng ở nút bất kỳ cũng đi được hết vòng”.

Định nghĩa vòng đơn. Mỗi nút vẫn chỉ có pNext (như DSLK đơn). Khác một điểm:

Nút cuối không trỏ NULL mà trỏ về nút đầu.

          ┌──────────────────────────────────────────┐
          ▼                                          │
        ┌────┬────┐    ┌────┬────┐    ┌────┬────┐    │
        │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  ●─┼────┘
        └────┴────┘    └────┴────┘    └────┴────┘
            ▲                               ▲
          head                            pTail

  head = pTail->pNext
  Không còn ô nào chứa NULL  →  while (p != NULL) sẽ CHẠY MÃI

Ba hình dạng phải thuộc (rỗng / 1 nút / nhiều nút):

 RỖNG                         MỘT NÚT (tự trỏ mình)
 pTail ──► NULL                    pTail
                                     │
                                     ▼
                                  ┌────┬────┐
                               ┌─►│ 10 │  ●─┼─┐
                               │  └────┴────┘ │
                               └──────────────┘
                                  p->pNext = p
                                  head = pTail = p

 NHIỀU NÚT (n = 3)
          ┌──────────────────────────────┐
          ▼                              │
        [10] ──► [20] ──► [30] ──────────┘
          ▲                 ▲
        head              pTail

Vì sao chỉ giữ pTail, không giữ pHead?

Đây là mẹo tổ chức then chốt — học thuộc lý do, không chỉ thuộc code.

Chỉ giữ	Thêm đầu	Thêm cuối	Lý do
`pHead`	Muốn nối `last->pNext = nút mới` nhưng không có `last` → phải đi vòng $O(n)$	Phải tìm last $O(n)$	Mất đúng hai thao tác “rẻ”
`pTail`	Nút mới chèn ngay sau tail (tức ngay trước head) — $O(1)$	Cùng chỗ chèn, rồi dời `pTail` — $O(1)$	`pTail->pNext` chính là head, luôn sẵn

 head = pTail->pNext     ← không cần biến pHead riêng

 Giữ cả pHead lẫn pTail trên vòng cũng được, nhưng thừa:
 pHead luôn bằng pTail->pNext, thêm một bất biến phải bảo trì.
 Giáo trình / đề thi: một con trỏ pTail là đủ.

struct CLIST {
    NODE* pTail;     // NULL ⇔ rỗng;  pTail->pNext = head
};

void KhoiTaoC(CLIST &l) { l.pTail = NULL; }

bool IsEmptyC(CLIST l) { return l.pTail == NULL; }

Dùng lại NODE / TaoNode của DSLK đơn (mục 3.3.1) — cấu trúc nút không đổi. Đổi cách nối đuôi với đầu, và đổi điều kiện dừng khi duyệt.

Bất biến vòng đơn:

#	Bất biến
1	Rỗng ⇔ `pTail == NULL`
2	Một nút ⇔ `pTail->pNext == pTail`
3	Nhiều nút: đi từ `pTail->pNext` theo `pNext` sẽ quay lại `pTail->pNext` sau đúng $n$ bước; không gặp `NULL`
4	`pTail` luôn là nút đứng trước head (người cuối bàn)

B. Duyệt vòng — không viết `while (p != NULL)`

Vì không còn NULL, vòng while (p != NULL) không bao giờ kết thúc. Đây là bug số 1 khi mới học vòng.

Ý tưởng. Xuất phát tại head (pTail->pNext), in, tiến, lặp đến khi gặp lại head.

List 1 nút: head.next = chính head. Nếu dùng while (p != head) trước khi in thì thân vòng không chạy → bỏ sót nút duy nhất. Vì vậy phải làm rồi mới kiểm tra → do-while.

THUẬT TOÁN XuatVong(l)
nếu pTail = NULL thì return          // rỗng
p ← pTail.pNext                      // head
lặp
    in p.data
    p ← p.pNext
until p = pTail.pNext                // đã quay về head

 List 10 → 20 → 30 → (về 10)

 p bắt đầu = 10
   in 10, p = 20     20 ≠ head  → tiếp
   in 20, p = 30     30 ≠ head  → tiếp
   in 30, p = 10     10 = head  → dừng
 In: 10 20 30  (đúng một vòng, không lặp vô hạn)

void XuatVong(CLIST l) {
    if (l.pTail == NULL) return;
    NODE* p = l.pTail->pNext;    // head
    do {
        cout << p->data << " -> ";
        p = p->pNext;
    } while (p != l.pTail->pNext);
    cout << "(quay ve dau)\n";
}

int DemSoPhanTuVong(CLIST l) {
    if (l.pTail == NULL) return 0;
    int dem = 0;
    NODE* p = l.pTail->pNext;
    do {
        dem++;
        p = p->pNext;
    } while (p != l.pTail->pNext);
    return dem;
}

NODE* TimVong(CLIST l, int x) {
    if (l.pTail == NULL) return NULL;
    NODE* p = l.pTail->pNext;
    do {
        if (p->data == x) return p;
        p = p->pNext;
    } while (p != l.pTail->pNext);
    return NULL;
}

Bảng đối chiếu điều kiện dừng (thuộc để không lẫn 3.3 / 3.4.1 / 3.4.2):

Loại list	Xuất phát	Điều kiện lặp	Gặp `NULL`?
Đơn thẳng	`pHead`	`while (p != NULL)`	Có, ở nút cuối
Kép thẳng xuôi	`pHead`	`while (p != NULL)`	Có
Kép thẳng ngược	`pTail`	`while (p != NULL)` theo `pPrev`	Có, ở nút đầu
Vòng đơn	`pTail->pNext`	`do { … p = p->pNext; } while (p != head)`	Không

Bẫy duyệt:

Code sai	Chuyện gì xảy ra
`while (p != NULL)`	Treo máy / timeout
`while (p != head) { in; p = p->pNext; }` với `p` xuất phát tại head	Không in gì — kể cả list 1 nút lẫn $n$ nút
`for (p = head; p != head; p = p->pNext)`	Cùng lỗi: điều kiện sai ngay từ đầu
Quên nhánh `pTail == NULL` rồi đọc `pTail->pNext`	Crash trên list rỗng
Dùng `p != pTail` làm điều kiện dừng khi muốn in hết	Bỏ nút cuối (tail không được in)

$O(n)$ thời gian, $O(1)$ phụ — giống duyệt thẳng, chỉ khác điều kiện dừng.

C. Thêm đầu / thêm cuối — cùng 2 phép, khác `pTail`

Ý tưởng then chốt của cả mục 3.4.2:

Trên vòng, nút mới luôn được chèn ngay sau pTail (khe giữa đuôi và đầu).

Thêm cuối: chèn xong, dời pTail sang nút mới → nút mới thành đuôi.

Thêm đầu: chèn xong, không dời pTail → nút mới đứng ngay sau đuôi, tức là thành head mới (head = pTail->pNext).

Hai hàm gần như giống nhau. Nhầm một dòng pTail = p là đổi đầu thành cuối.

          khe chèn luôn ở đây
          ┌──────────┐
          │          ▼
        tail        head
          │          │
        [30] ──► [10] ──► [20] ──► (về 30)
                    ▲
                    └── thêm đầu: nút mới ngồi vào khe, pTail đứng yên
          thêm cuối: nút mới ngồi vào khe, rồi pTail nhảy sang nút mới

① Thêm cuối — $O(1)$

List rỗng: nút tự trỏ tới chính nó (hình “một nút” mục A). Đây là nhánh bắt buộc — không có pTail->pNext để đọc.

      pTail
        │
        ▼
     ┌────┬────┐
  ┌─►│ 30 │  ●─┼─┐
  │  └────┴────┘ │
  └──────────────┘
   p->pNext = p

List đã có nút — 3 phép, không được đảo ① và ②:

 TRƯỚC  head = 10, pTail = 30, thêm p = 40
          ┌────────────────────────────────┐
          ▼                                │
        ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
        │ 10 │  ●─┼──►│ 20 │  ●─┼──►│ 30 │  ●─┼┘
        └────┴────┘   └────┴────┘   └────┴────┘
            ▲                           ▲
          head                        pTail

 ① p->pNext = pTail->pNext     (40 nắm head = 10 — GIỮ head trước khi cắt)
 ② pTail->pNext = p            (30 nắm 40)
 ③ pTail = p                   (40 thành đuôi)

 SAU   head vẫn 10, pTail = 40
          ┌──────────────────────────────────────────┐
          ▼                                          │
        [10] ──► [20] ──► [30] ──► [40] ─────────────┘
          ▲                          ▲
        head                       pTail

THUẬT TOÁN ThemCuoiVong(l, p)
nếu pTail = NULL
    pTail ← p
    p.pNext ← p              // 1 nút tự trỏ mình
    return
p.pNext ← pTail.pNext        // p nắm head cũ
pTail.pNext ← p              // tail cũ nắm p
pTail ← p                    // p thành đuôi

void ThemCuoiVong(CLIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pTail == NULL) {
        l.pTail = p;
        p->pNext = p;
        return;
    }
    p->pNext = l.pTail->pNext;   // ① giữ head
    l.pTail->pNext = p;          // ②
    l.pTail = p;                 // ③
}

Bẫy: đảo ① và ② → pTail->pNext = p trước, lúc đó p->pNext còn NULL (nếu TaoNode) hoặc rác; mất địa chỉ head, list đứt + rò rỉ.
Bẫy: quên p->pNext = p khi rỗng → nút không khép vòng, duyệt do-while không bao giờ gặp lại head (hoặc crash).

② Thêm đầu — $O(1)$

Cùng ①② với thêm cuối, bỏ bước ③.

 TRƯỚC  head = 10, pTail = 30, thêm p = 5

 ① p->pNext = pTail->pNext     (5 nắm 10)
 ② pTail->pNext = p            (30 nắm 5)
    pTail KHÔNG đổi            (đuôi vẫn 30)

 SAU   head mới = pTail->pNext = 5
          ┌──────────────────────────────────────────┐
          ▼                                          │
        [5] ──► [10] ──► [20] ──► [30] ──────────────┘
          ▲                            ▲
        head                         pTail

void ThemDauVong(CLIST &l, NODE* p) {
    if (p == NULL) return;
    if (l.pTail == NULL) {
        l.pTail = p;
        p->pNext = p;
        return;
    }
    p->pNext = l.pTail->pNext;
    l.pTail->pNext = p;
    /* pTail khong doi — chi khac ThemCuoiVong dung 1 dong nay */
}

Bảng nhớ 1 dòng:

Hàm	Chèn sau `pTail`	Có `pTail = p`?	Nút mới thành
`ThemDauVong`	Có	Không	Head
`ThemCuoiVong`	Có	Có	Tail

Nhánh rỗng của hai hàm giống hệt: một nút vừa là đầu vừa là cuối.

$O(1)$ cả hai. Đây là lý do chọn giữ pTail.

③ Thêm sau một nút `q` — $O(1)$

Giống DSLK đơn: p->pNext = q->pNext; q->pNext = p. Nếu q == pTail thì đây chính là thêm cuối → phải dời pTail.

void ThemSauVong(CLIST &l, NODE* q, NODE* p) {
    if (q == NULL || p == NULL) return;
    p->pNext = q->pNext;
    q->pNext = p;
    if (q == l.pTail)
        l.pTail = p;
}

Thêm trước q trên vòng đơn vẫn $O(n)$ : không có pPrev, phải đi tìm nút t sao cho t->pNext == q (đi nhiều nhất một vòng). Muốn $O(1)$ thì dùng vòng kép.

④ Dựng vòng `[10]→[20]→[30]` bằng thêm cuối

rỗng:     pTail = NULL
+10:      [10]↺                 pTail = 10,  10.next = 10
+20:      [10]→[20]↺            pTail = 20,  20.next = 10
+30:      [10]→[20]→[30]↺       pTail = 30,  30.next = 10

So với dựng DSLK đơn: bước 1 khác (tự trỏ mình, không trỏ NULL); mỗi bước sau chèn vào khe tail–head thay vì “nối vào NULL”.

D. Xóa đầu / xóa cuối / xóa giá trị / hủy

⑤ Xóa đầu — $O(1)$

Head luôn là pTail->pNext. Cắt head ra = cho tail nắm nút sau head.

Một nút: sau khi xóa, list rỗng → pTail = NULL.

 TRƯỚC  xóa head = 10, pTail = 30
          ┌────────────────────────────────┐
          ▼                                │
        [10] ──► [20] ──► [30] ────────────┘
          ▲                 ▲
        head              pTail

  headMoi = 20
  pTail->pNext = 20
  delete 10

 SAU
          ┌──────────────────┐
          ▼                  │
        [20] ──► [30] ───────┘
          ▲        ▲
        head     pTail

THUẬT TOÁN XoaDauVong(l)
nếu pTail = NULL thì return
head ← pTail.pNext
nếu pTail = head              // 1 nút
    delete head
    pTail ← NULL
    return
pTail.pNext ← head.pNext      // tail nắm head mới
delete head

void XoaDauVong(CLIST &l) {
    if (l.pTail == NULL) return;
    NODE* head = l.pTail->pNext;
    if (l.pTail == head) {
        delete head;
        l.pTail = NULL;
        return;
    }
    l.pTail->pNext = head->pNext;
    delete head;
}

Bẫy: quên nhánh 1 nút → pTail->pNext = head->pNext nhưng head->pNext == head (đã delete) → pTail trỏ vùng nhớ chết.

⑥ Xóa cuối — $O(n)$ trên vòng đơn

Đây là chỗ hay hiểu sai.

Có pTail không biến xóa cuối thành $O(1)$ trên vòng đơn.
Xóa tail cần nút đứng trước tail (prev->pNext = head, rồi pTail = prev).
Vòng đơn không lưu pPrev → phải đi gần một vòng từ head đến khi p->pNext == pTail.

 TRƯỚC  xóa tail = 30, cần tìm prev = 20
          [10] → [20] → [30] ↺
            ▲      ▲      ▲
          head   prev   pTail

  prev->pNext = head = 10
  pTail = prev = 20
  delete 30

 SAU     [10] → [20] ↺

Một nút: giống xóa đầu — pTail = NULL.

void XoaCuoiVong(CLIST &l) {
    if (l.pTail == NULL) return;

    NODE* head = l.pTail->pNext;
    if (l.pTail == head) {          // 1 nut
        delete head;
        l.pTail = NULL;
        return;
    }

    NODE* prev = head;
    while (prev->pNext != l.pTail)  // di tim nut ap chot — O(n)
        prev = prev->pNext;

    prev->pNext = head;             // khép vòng bỏ tail
    delete l.pTail;
    l.pTail = prev;
}

	Vòng đơn + `pTail`	Vòng kép	DSLK kép thẳng
Xóa đầu	$O(1)$	$O(1)$	$O(1)$
Xóa cuối	$O(n)$	$O(1)$	$O(1)$

Muốn xóa cuối $O(1)$ trên dữ liệu tuần hoàn → vòng kép (mục E).

⑦ Xóa theo giá trị — $O(n)$

Đi một vòng với cặp (prev, p). Khi gặp p->data == x: prev->pNext = p->pNext. Nếu p là tail thì pTail = prev. Nếu p là head thì pTail->pNext tự thành head mới vì prev đang là tail.

void XoaGiaTriVong(CLIST &l, int x) {
    if (l.pTail == NULL) return;

    NODE* head = l.pTail->pNext;
    if (head == l.pTail && head->data == x) {   // 1 nut
        delete head;
        l.pTail = NULL;
        return;
    }

    NODE* prev = l.pTail;
    NODE* p = head;
    do {
        if (p->data == x) {
            prev->pNext = p->pNext;
            if (p == l.pTail)
                l.pTail = prev;
            delete p;
            return;
        }
        prev = p;
        p = p->pNext;
    } while (p != head);
}

do-while để list 1 nút vẫn được xét (nhánh 1 nút đã return trước, nhưng vòng này còn dùng khi $n \ge 2$ ). Không thấy x thì đi hết một vòng rồi dừng — không treo.

⑧ Hủy vòng — nhớ cắt vòng trước

Nếu gọi XoaDauVong trong while (pTail != NULL) thì được, vì mỗi lần xóa giảm $n$ , hết thì pTail = NULL.

Cách an toàn hơn khi muốn tái sử dụng code hủy DSLK thẳng: cắt vòng thành list thẳng, rồi delete như 3.3.

  [10] → [20] → [30] ↺     cắt: pTail->pNext = NULL
  [10] → [20] → [30] → NULL     giờ while (p != NULL) an toàn

void HuyDanhSachVong(CLIST &l) {
    if (l.pTail == NULL) return;
    NODE* p = l.pTail->pNext;   // head
    l.pTail->pNext = NULL;      // CẮT VÒNG — bien thanh DSLK don thang
    l.pTail = NULL;
    while (p != NULL) {
        NODE* t = p->pNext;
        delete p;
        p = t;
    }
}

Bẫy: hủy bằng while (p != NULL) mà không cắt vòng → treo, không delete hết, rò rỉ + chương trình không kết thúc.

⑨ Ví dụ chạy tay cả chuỗi (vòng đơn)

rỗng
ThemCuoi 20     →  [20]↺
ThemDau 10      →  [10]→[20]↺          (pTail vẫn 20)
ThemCuoi 30     →  [10]→[20]→[30]↺     (pTail = 30)
XoaDau          →  [20]→[30]↺
XoaGiaTri 30    →  [20]↺               (xóa tail, pTail = 20)
XoaCuoi         →  rỗng
 XuatVong bước 3:  10 -> 20 -> 30 -> (quay ve dau)

E. DSLK vòng kép (circular doubly)

Ghép ý 3.4.1 và 3.4.2: mỗi nút có pPrev + pNext, và hai đầu nắm nhau.

     ┌───────────────────────────────────────────────────┐
     ▼                                                   │
 ┌────┬────┬────┐   ┌────┬────┬────┐   ┌────┬────┬────┐  │
 │  ● │ 10 │  ●─┼──►│  ● │ 20 │  ●─┼──►│  ● │ 30 │  ●─┼──┘
 │    │    │    │◄──┼─●  │    │    │◄──┼─●  │    │    │
 └────┴────┴────┘   └────┴────┴────┘   └────┴────┴────┘
     ▲                                                 ▲
   head                                     tail = head->pPrev

 Bất biến vòng kép (không rỗng):
   head->pPrev == tail
   tail->pNext == head
   mọi cặp kề: a.pNext = b  ⇔  b.pPrev = a
 Một nút: p->pNext == p->pPrev == p

Tổ chức: chỉ cần giữ head. Tail suy ra: head->pPrev. Không bắt buộc thêm pTail (khác vòng đơn — vòng đơn phải giữ tail mới thêm đầu/cuối $O(1)$ ).

struct CDNODE {
    int data;
    CDNODE *pPrev, *pNext;
};

CDNODE* TaoCDNode(int x) {
    CDNODE* p = new CDNODE;
    p->data = x;
    p->pPrev = p->pNext = p;   // mac dinh 1 nut tu khép hai chieu
    return p;
}

Duyệt: cùng do-while với vòng đơn; muốn ngược thì p = p->pPrev.

void XuatVongKep(CDNODE* head) {
    if (head == NULL) return;
    CDNODE* p = head;
    do {
        cout << p->data << " ";
        p = p->pNext;
    } while (p != head);
    cout << "\n";
}

Thêm cuối $O(1)$ :

 TRƯỚC  head=10, tail=head->pPrev=30, thêm p=40
  10 ↔ 20 ↔ 30  (30.next=10, 10.prev=30)

  p.next = head          (40 nắm 10)
  p.prev = tail          (40 nắm 30)
  tail.next = p          (30 nắm 40)
  head.prev = p          (10.prev = 40)
  head không đổi

 SAU   10 ↔ 20 ↔ 30 ↔ 40 ↺
       head            tail = 40 = head->pPrev

void ThemCuoiVongKep(CDNODE* &head, CDNODE* p) {
    if (p == NULL) return;
    if (head == NULL) {
        p->pNext = p->pPrev = p;
        head = p;
        return;
    }
    CDNODE* tail = head->pPrev;
    p->pNext = head;
    p->pPrev = tail;
    tail->pNext = p;
    head->pPrev = p;
}

Thêm đầu $O(1)$ : thêm cuối xong, head = p (nút mới vừa là đuôi logic, dời cửa head sang nó thì nó thành đầu). Hoặc chèn vào khe tail ↔ head rồi head = p.

void ThemDauVongKep(CDNODE* &head, CDNODE* p) {
    ThemCuoiVongKep(head, p);
    if (head != NULL)
        head = p;    // p vua la tail, dời head sang p → p thành đầu
}

Xóa một nút đang cầm $O(1)$ — kể cả xóa cuối (thắng vòng đơn):

void XoaNodeVongKep(CDNODE* &head, CDNODE* p) {
    if (head == NULL || p == NULL) return;

    if (p->pNext == p) {          // 1 nut
        delete p;
        head = NULL;
        return;
    }
    p->pPrev->pNext = p->pNext;
    p->pNext->pPrev = p->pPrev;
    if (p == head)
        head = p->pNext;
    delete p;
}

void XoaDauVongKep(CDNODE* &head) {
    if (head != NULL) XoaNodeVongKep(head, head);
}

void XoaCuoiVongKep(CDNODE* &head) {
    if (head != NULL) XoaNodeVongKep(head, head->pPrev);  // O(1)!
}

Hủy: cắt vòng (head->pPrev->pNext = NULL và head->pPrev = NULL) rồi xóa như kép thẳng; hoặc while (head != NULL) XoaDauVongKep(head).

Khi nào dùng vòng kép? Playlist lặp có nút Prev, game đi vòng hai chiều, buffer tròn cần xóa hai đầu $O(1)$ . Đề thi ít bắt cài đủ ADT này — hiểu bất biến + thêm cuối + xóa nút đang cầm là đạt.

F. Ứng dụng: round-robin, playlist, Josephus

1. Round-robin scheduling (hệ điều hành)

CPU có $n$ tiến trình, mỗi tiến trình được chạy một quantum (lát thời gian), xong thì đến tiến trình kế, hết vòng thì về tiến trình đầu. Đúng hình vòng.

  pTail trỏ tiến trình VỪA chạy xong
  pTail->pNext = tiến trình SẼ chạy (head của “hàng chờ vòng”)

  Lát kế:
    chạy head
    nếu head còn việc  →  coi như “chuyển head ra cuối”
                          = ThemCuoi ý niệm: chỉ dời pTail = pTail->pNext
                          (không cấp phát nút mới — chỉ xoay cửa)
    nếu head xong việc →  XoaDauVong

Chạy tay. Ba tiến trình, thời gian còn lại $(P_1=3,\ P_2=2,\ P_3=1)$ , quantum $= 1$ .

 Ban đầu vòng:  P1(3) → P2(2) → P3(1) ↺     sắp chạy P1

 Q1: P1 chạy → P1(2). Chưa xong, xoay:  P2(2) → P3(1) → P1(2)
 Q2: P2 chạy → P2(1). Xoay:             P3(1) → P1(2) → P2(1)
 Q3: P3 chạy → P3(0). XONG, xóa P3:     P1(2) → P2(1)
 Q4: P1 chạy → P1(1). Xoay:             P2(1) → P1(1)
 Q5: P2 chạy → P2(0). XONG, xóa P2:     P1(1)
 Q6: P1 chạy → P1(0). XONG. Vòng rỗng.

 Thứ tự hoàn thành: P3, P2, P1

“Xoay” không cần ThemCuoi thật: pTail = pTail->pNext là đủ — vì list đã là vòng, dời tail một bước = đưa head cũ thành tail, head mới là nút kế. Đây là thao tác chỉ vòng mới có ( $O(1)$ , không cấp phát).

2. Playlist lặp / slide show

Vòng đơn: nút Next. Hết bài cuối → bài đầu tự động (current = current->pNext, không cần if (cuoi) current = head).
Vòng kép: thêm nút Prev. UI “bài trước” = current = current->pPrev.
Thêm bài sau bài đang phát = ThemSau. Xóa bài đang phát = xóa nút đang cầm (vòng kép $O(1)$ ; vòng đơn phải có prev).

3. Game: lượt chơi quanh bàn

Người chơi là nút vòng. current = người đang đi. Hết lượt: current = current->pNext. Người bị loại: xóa nút (Josephus là trường hợp đếm $k$ rồi loại).

4. Circular buffer ≠ DSLK vòng

Sinh viên hay gọi cả hai là “vòng”. Phân biệt:

	DSLK vòng	Circular buffer (mảng vòng)
Lưu	Nút rải Heap, nối con trỏ	Mảng cố định, hai chỉ số `front`/`rear`
Hết chỗ	Còn RAM là thêm được	Đầy khi $(rear+1) \bmod n = front$
Dùng khi	$n$ không biết trước, thêm/xóa giữa	Hàng đợi kích thước kịch trần (buffer âm thanh, IO)

Cùng ý “quay lại đầu”, khác cấu trúc. Chương 4 (Queue) sẽ gặp mảng vòng.

5. Bài toán Josephus — ứng dụng kinh điển

$n$ người đứng vòng, đánh số $1..n$ . Đếm $k$ người thì loại 1, tiếp tục từ người kế, đến khi còn 1 người. Tìm người sống sót.

Mô hình: vòng đơn; xóa nút đang cầm cần con trỏ đứng trước người bị loại.

Chạy tay $n=5$ , $k=2$ (bắt đầu đếm từ người 1; code đứng ở người trước người sắp bị loại):

 Ban đầu:
     ┌─────────────────────────────────┐
     ▼                                 │
   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
   │ 1 │──►│ 2 │──►│ 3 │──►│ 4 │──►│ 5 │┘
   └───┘   └───┘   └───┘   └───┘   └───┘

 k=2: loại người thứ 2 kể từ chỗ đếm.
 Lần 1: đếm 1, 2  → loại 2.  Còn 1 → 3 → 4 → 5 → 1
 Lần 2: từ 3, đếm 3, 4  → loại 4.  Còn 1 → 3 → 5 → 1
 Lần 3: từ 5, đếm 5, 1  → loại 1.  Còn 3 → 5 → 3
 Lần 4: từ 3, đếm 3, 5  → loại 5.  Còn 3 → 3
 Sống sót: 3

Truy vết con trỏ (khớp code dưới: p đứng trước người bị loại; với $k=2$ thì không cần vòng for, p->pNext chính là nạn nhân):

 Ban đầu p = người 1 (head). k=2 → p phải đứng trước nạn nhân.
 Vòng while còn > 1 người:
   for i = 1 .. k-2: p đi tới        (k=2: for không chạy)
   chet = p->pNext
   p->pNext = chet->pNext            (bỏ chet khỏi vòng)
   nếu chet là pTail thì pTail = p
   delete chet
   p = p->pNext                      (người kế tiếp bắt đầu đếm mới)

 Lần 1: p=1, chet=2, 1 nắm 3, p ← 3
 Lần 2: p=3, chet=4, 3 nắm 5, p ← 5
 Lần 3: p=5, chet=1, 5 nắm 3, p ← 3
 Lần 4: p=3, chet=5, 3 nắm 3 (tự trỏ), p ← 3
 Dừng: p->pNext == p, sống = 3

THUẬT TOÁN Josephus(n, k) → người sống sót
nếu n < 1 hoặc k < 1 thì trả về -1
nếu k = 1 thì trả về n          // loại lần lượt người hiện tại
dựng vòng 1..n bằng ThemCuoiVong
p ← head
while p.pNext ≠ p               // còn > 1 người
    lặp k-2 lần: p ← p.pNext    // p đứng trước nạn nhân
    chet ← p.pNext
    p.pNext ← chet.pNext
    nếu chet là pTail thì pTail ← p
   delete chet
   p ← p.pNext
sống ← p.data; delete p; trả về sống

int Josephus(int n, int k) {
    if (n < 1 || k < 1) return -1;
    if (k == 1) return n;          // giet lan luot nguoi hien tai: con lai nguoi n

    CLIST l;
    KhoiTaoC(l);
    for (int i = 1; i <= n; i++)
        ThemCuoiVong(l, TaoNode(i));

    NODE* p = l.pTail->pNext;      // bat dau o nguoi 1
    while (p->pNext != p) {        // con > 1 nguoi
        for (int i = 1; i < k - 1; i++)
            p = p->pNext;
        NODE* chet = p->pNext;
        p->pNext = chet->pNext;
        if (chet == l.pTail) l.pTail = p;
        delete chet;
        p = p->pNext;
    }
    int song = p->data;
    delete p;
    l.pTail = NULL;
    return song;
}

Code đúng với $n=5, k=2$ (sống sót $= 3$ ) và $k \ge 2$ . $k=1$ xử lý riêng: nếu để vào vòng for thì p “đứng trước nạn nhân” không còn đúng nghĩa khi nạn nhân là chính p.

Thêm một test (bài tập 12): $n=5, k=3$ → loại 3, 1, 5, 2 → sống sót 4.

Độ phức tạp mô phỏng: $O(n \cdot k)$ naive. Chỉ cần vị trí sống sót, không cần dựng list: công thức $f(1)=0$ , $f(i)=(f(i-1)+k) \bmod i$ (0-based) — $O(n)$ , không thuộc trọng tâm chương.

G. Ưu / nhược điểm DSLK vòng

Ưu

Từ mọi nút đi được hết danh sách, không cần quay về biến pHead.
Thêm đầu và thêm cuối $O(1)$ nếu giữ pTail (vòng đơn).
“Xoay” cửa $O(1)$ : pTail = pTail->pNext — round-robin không cấp phát.
Mô hình tự nhiên cho dữ liệu tuần hoàn.

Nhược

Dễ vòng lặp vô hạn nếu quên điều kiện dừng / quên cắt vòng khi hủy.
Không có NULL lính canh → hầu hết hàm viết do-while + nhánh rỗng/1 nút.
Vòng đơn: xóa cuối vẫn $O(n)$ .
Debug khó hơn list thẳng (in mãi một vòng trông giống treo).

Chọn loại vòng:

Nhu cầu	Chọn
Round-robin, Josephus, chỉ đi tới	Vòng đơn + `pTail`
Playlist Prev/Next, xóa cuối $O(1)$	Vòng kép
Buffer kích thước cố định	Mảng vòng (không phải DSLK)

H. Bảng bốn loại — nhìn là chọn được

	Đơn thẳng	Kép thẳng	Vòng đơn	Vòng kép
Con trỏ mỗi nút	`pNext`	`pPrev` `pNext`	`pNext`	`pPrev` `pNext`
Nút cuối trỏ	`NULL`	`NULL`	Head	Head
Nút đầu `pPrev`	—	`NULL`	—	Tail
Cửa vào	`pHead` (+`pTail`)	`pHead`+`pTail`	`pTail`	`head` (tail = `head->pPrev`)
Duyệt	`p != NULL`	xuôi/ngược `!= NULL`	`do-while` về head	`do-while` xuôi hoặc ngược
Thêm đầu / cuối	$O(1)$ / $O(1)$	$O(1)$ / $O(1)$	$O(1)$ / $O(1)$	$O(1)$ / $O(1)$
Xóa cuối	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Thêm trước nút đang cầm	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Đi lùi	Không	Có	Không	Có
Ứng dụng mẫu	Stack, danh sách SV	Undo, LRU, deque	Round-robin, Josephus	Playlist lặp 2 chiều

✅ Kiểm tra nhanh 3.4

DSLK kép thắng đơn ở ba thao tác nào khi đã cầm con trỏ tới nút? Đánh đổi gì?
Xóa nút giữa trên kép: hai phép gán bắt buộc? Vì sao phải xét nhánh “1 nút” trước nhánh “xóa đầu”?
Thêm trước nút q trên kép vì sao $O(1)$ , trên đơn lại $O(n)$ ?
LRU đầy: vứt nút nào, thêm nút mới vào đâu? Độ phức tạp mỗi bước (bỏ HashMap)?
Vì sao vòng đơn chỉ giữ pTail chứ không chỉ giữ pHead?
ThemDauVong và ThemCuoiVong khác nhau đúng một dòng nào?
Vì sao while (p != NULL) trên vòng chạy mãi? Viết điều kiện dừng đúng. Vì sao phải do-while chứ không while (p != head)?
Xóa cuối vòng đơn $O(?)$ . Muốn $O(1)$ thì đổi sang loại nào?
Hủy vòng: phải làm gì trước khi while (p != NULL) delete?
Josephus $n=5, k=2$ , người sống sót? $n=5, k=3$ ?

Đáp án:
(1) Đi lùi, xóa chính nút đang cầm, xóa cuối — đều $O(1)$ ; tốn thêm 1 con trỏ/nút, sửa nhiều liên kết hơn, dễ lệch hai chiều.
(2) p->pPrev->pNext = p->pNext và p->pNext->pPrev = p->pPrev. Một nút thì pHead->pNext là NULL; gán pHead = NULL rồi còn pHead->pPrev sẽ crash.
(3) Kép có q->pPrev sẵn; đơn phải duyệt từ head tìm nút t với t->pNext == q.
(4) Vứt pTail (cũ nhất), thêm vào pHead (mới nhất); mỗi bước $O(1)$ trên kép.
(5) pTail->pNext chính là head → thêm đầu và thêm cuối đều chèn sau tail trong $O(1)$ . Chỉ giữ head thì phải tìm last $O(n)$ .
(6) ThemCuoiVong có thêm l.pTail = p; ThemDauVong không.
(7) Không còn NULL. do { … p = p->pNext; } while (p != head). while (p != head) khi p đang ở head → thân vòng không chạy, bỏ hết dữ liệu.
(8) $O(n)$ ; vòng kép (hoặc kép thẳng nếu không cần tuần hoàn).
(9) Cắt vòng: pTail->pNext = NULL.
(10) Người 3; người 4.

3.5. SO SÁNH TỔNG HỢP VÀ ỨNG DỤNG

3.5.1. Bảng chọn cấu trúc

Nhu cầu	Chọn
`a[i]` thường xuyên, ít thêm/xóa giữa	Mảng
Thêm/xóa đầu nhiều, kích thước không biết trước	DSLK đơn
Thêm cuối nhiều	DSLK đơn + `pTail`, hoặc vòng + `pTail`
Xóa cuối / đi lùi / undo-redo	DSLK kép
Dữ liệu tuần hoàn, round-robin	DSLK vòng
Cache LRU, deque	DSLK kép (+ hash nếu cần tìm $O(1)$ )

3.5.2. Overhead bộ nhớ (máy 64-bit, `int` 4 byte, con trỏ 8 byte, alignment)

NODE  đơn:  data 4 + padding 4 + pNext 8  ≈ 16 byte  (chỉ 4 byte là dữ liệu)
DNODE kép: data 4 + pad 4 + pPrev 8 + pNext 8 ≈ 24 byte

1000 số nguyên:

Mảng: $1000 \times 4 = 4000$ byte.
DSLK đơn: $\approx 16000$ byte (gấp 4).
DSLK kép: $\approx 24000$ byte (gấp 6).

DSLK đắt RAM. Đừng dùng khi chỉ cần lưu dãy số tĩnh.

3.5.3. Ứng dụng “zero to hero”

1. Đa thức — mỗi nút (hệ số, số mũ), chỉ lưu số hạng ≠ 0. Đây là ứng dụng kinh điển trong giáo trình CTDL.

P(x) = 3x^5 + 2x^2 + 1     ≡    [3,5] → [2,2] → [1,0] → NULL
                                 coef  exp

Quy ước: sắp theo mũ giảm dần, không có số hạng hệ số 0.

struct Term {
    double coef;
    int exp;
    Term* pNext;
};

Cộng hai đa thức = đi song song hai list (giống Noi), so sánh mũ:

So sánh mũ	Việc làm
`p->exp > q->exp`	Copy số hạng `p` vào kết quả, `p` tiến
`p->exp < q->exp`	Copy số hạng `q`, `q` tiến
`p->exp == q->exp`	Cộng hệ số; nếu tổng ≠ 0 thì ghi vào kết quả; cả `p` và `q` tiến

Tính $P(x_0)$ : duyệt list, tong += coef * pow(x0, exp). $O(n)$ .

2. Danh sách kề của đồ thị — chương sau: mỗi đỉnh một DSLK các đỉnh kề. Đồ thị thưa tiết kiệm hơn ma trận.

3. Ngăn xếp / hàng đợi — chương 4: Stack = thêm/xóa đầu DSLK; Queue = thêm cuối + xóa đầu.

4. Bộ nhớ hệ điều hành — free list: các khối RAM trống xâu thành DSLK.

5. Trình duyệt, editor, LRU, deque — DSLK kép (chi tiết chạy tay: mục 3.4.1.H). Round-robin / Josephus / playlist lặp — DSLK vòng (mục 3.4.2.F).

3.6. THUẬT TOÁN NÂNG CAO TRÊN DSLK ĐƠN

Các thuật toán dưới đây xuất hiện trong bài tập khó / phỏng vấn. Nên hiểu ý tưởng hai con trỏ.

3.6.1. Đảo ngược danh sách — $O(n)$ , $O(1)$ phụ

10 → 20 → 30 → NULL     thành     30 → 20 → 10 → NULL

Cần ba con trỏ vì mỗi lần lật cur->pNext sẽ mất địa chỉ nút sau, nên phải giữ next trước.

 Ban đầu:  prev=NULL     cur
                         │
                         ▼
                      ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
                      │ 10 │  ●─┼───►│ 20 │  ●─┼───►│ 30 │  / │
                      └────┴────┘    └────┴────┘    └────┴────┘

 Lần 1: next=20; lật 10 về prev (NULL)
         prev          cur
           │             │
           ▼             ▼
        ┌────┬────┐   ┌────┬────┐    ┌────┬────┐
        │ 10 │  / │   │ 20 │  ●─┼───►│ 30 │  / │
        └────┴────┘   └────┴────┘    └────┴────┘

 Lần 2: next=30; lật 20 về 10
                      prev          cur
                        │             │
                        ▼             ▼
        ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
        │ 10 │  / │◄──┤ 20 │  ● │   │ 30 │  / │
        └────┴────┘   └────┴────┘   └────┴────┘

 Lần 3: next=NULL; lật 30 về 20; cur=NULL → dừng
  pHead=prev=30:

        ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
        │ 30 │  ●─┼───►│ 20 │  ●─┼───►│ 10 │  / │──► NULL
        └────┴────┘    └────┴────┘    └────┴────┘
            ▲                             ▲
          pHead                         pTail (head cũ)

Mã giả:

THUẬT TOÁN DaoNguoc(l)
prev ← NULL, cur ← pHead
while cur ≠ NULL
    next ← cur.pNext
    cur.pNext ← prev      // lat chieu
    prev ← cur
    cur ← next
pTail ← pHead
pHead ← prev

void DaoNguoc(LIST &l) {
    NODE* prev = NULL;
    NODE* cur  = l.pHead;
    l.pTail = l.pHead;
    while (cur != NULL) {
        NODE* next = cur->pNext;
        cur->pNext = prev;
        prev = cur;
        cur  = next;
    }
    l.pHead = prev;
    if (l.pTail) l.pTail->pNext = NULL;
}

Đệ quy: đảo phần sau, rồi head->pNext->pNext = head; head->pNext = NULL. $O(n)$ stack — không dùng list dài.

3.6.2. Tìm nút giữa — hai con trỏ chậm/nhanh

slow đi 1 bước, fast đi 2. Khi fast không đi tiếp được, slow đang ở giữa — vì fast đã đi gấp đôi.

 List 5 nút:
 ┌────┬────┐   ┌────┬────┐   ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
 │ 10 │  ●─┼──►│ 20 │  ●─┼──►│ 30 │  ●─┼──►│ 40 │  ●─┼──►│ 50 │  / │
 └────┴────┘   └────┴────┘   └────┴────┘   └────┴────┘   └────┴────┘
     ▲
   S,F xuất phát

 Sau 1 nhịp (S+1, F+2):
                   S                   F
                   ▼                   ▼
                 [20]                [40]

 Sau 2 nhịp:
                                 S                   F hết đường
                                 ▼
                               [30]  ← nút giữa, trả về slow

Với số nút chẵn, slow dừng ở nút trái-giữa (tùy điều kiện vòng lặp). Không cần DemSoPhanTu rồi chia 2 — một lần duyệt.

NODE* TimNutGiua(LIST l) {
    if (l.pHead == NULL) return NULL;
    NODE* slow = l.pHead;
    NODE* fast = l.pHead;
    while (fast->pNext != NULL && fast->pNext->pNext != NULL) {
        slow = slow->pNext;
        fast = fast->pNext->pNext;
    }
    return slow;
}

$O(n)$ thời gian, $O(1)$ phụ. Không cần đếm $n$ rồi đi $n/2$ .

Tìm nút thứ $k$ từ cuối: fast đi trước $k$ bước, rồi slow và fast đi cùng tốc độ. Khi fast hết, slow là đáp án.

3.6.3. Phát hiện chu trình — Floyd (tortoise & hare)

Nếu ai đó gán nhầm pTail->pNext vào giữa list, duyệt while (p != NULL) treo.

 ┌────┬────┐   ┌────┬────┐   ┌────┬────┐   ┌────┬────┐
 │ 10 │  ●─┼──►│ 20 │  ●─┼──►│ 30 │  ●─┼──►│ 40 │  ●─┼─┐
 └────┴────┘   └────┴────┘   └────┴────┘   └────┴────┘ │
                     ▲                                 │
                     └─────────────────────────────────┘
  Có chu trình: 40 nắm lại 20. Không còn NULL. Duyệt thẳng sẽ không dừng.

bool CoChuTrinh(LIST l) {
    NODE* slow = l.pHead;
    NODE* fast = l.pHead;
    while (fast != NULL && fast->pNext != NULL) {
        slow = slow->pNext;
        fast = fast->pNext->pNext;
        if (slow == fast) return true;
    }
    return false;
}

Vì sao đúng: trên đoạn thẳng fast không bao giờ bị slow bắt. Khi cả hai vào vòng, mỗi nhịp khoảng cách giảm 1 (vì fast nhanh hơn 1 bước so với chu vi). Sau hữu hạn bước chúng đứng cùng một nút.

Tìm nút vào vòng: sau khi gặp nhau, đưa một con trỏ về pHead, cả hai đi từng bước; chỗ gặp lại là cửa vào vòng (Floyd bước 2).

3.6.4. Kiểm tra palindrome

Palindrome: đọc xuôi = đọc ngược, ví dụ 1 → 2 → 3 → 2 → 1.

Cách dễ (học trước): $O(n)$ thời gian, $O(n)$ bộ nhớ phụ — đẩy nửa đầu vào stack, so từng phần tử với nửa sau.

Cách $O(1)$ phụ:

Tìm nút giữa (mục 3.6.2).
Đảo nửa sau (mục 3.6.1).
So từng cặp từ pHead với đầu nửa sau.
Đảo lại nửa sau để trả list như cũ.

1 → 2 → 3 → 2 → 1
         giữa
đảo nửa sau:  1 → 2 → 3    và    1 → 2
so: 1=1, 2=2  → palindrome

3.7. BÀI TẬP

Làm theo thứ tự. Không nhìn code mẫu ở trên trừ khi đã viết nháp mã giả.

A. Lý thuyết — hiểu khái niệm

Bài 1. Phân biệt p, *p, &x. Vẽ ô nhớ cho:

int x = 7;
int *p = &x;
*p = 3;

Bài 2. Vì sao không được return địa chỉ biến cục bộ? Liên hệ với việc TaoNode phải new.

Bài 3. So sánh cấp phát tuần tự và cấp phát liên kết theo 5 tiêu chí: truy cập, thêm đầu, thêm giữa, bộ nhớ, cache.

Bài 4. DSLK đơn có pTail. Thao tác nào vẫn $O(n)$ ? Vì sao xóa cuối không xuống $O(1)$ ?

Bài 5. Nêu 4 con trỏ phải sửa khi thêm một nút vào giữa DSLK kép. Vẽ trước/sau.

Bài 6. Vì sao duyệt DSLK vòng không dùng while (p != NULL)? Viết điều kiện dừng đúng.

Bài 7. Sau SapXep (đổi chỗ data) trên DSLK, có binary search $O(\log n)$ được không? Giải thích.

Bài 8. Điền bảng: thêm đầu, thêm cuối, xóa đầu, xóa cuối cho (mảng, DSLK đơn+tail, DSLK kép, vòng+tail).

B. Truy vết (trace) — bắt buộc trước khi gõ code

Bài 9. List rỗng. Thực hiện: ThemCuoi 5, ThemDau 2, ThemCuoi 9, XoaDau, ThemTaiViTri(1, 7). Vẽ pHead, pTail sau mỗi bước.

Bài 10. [4]→[1]→[3]→[2]. Chạy SapXep (đổi chỗ trực tiếp, đúng giáo trình). Ghi data các nút sau mỗi vòng p.

Bài 11. DSLK kép [A]↔[B]↔[C]. Xóa B. Liệt kê giá trị pPrev/pNext của A và C sau khi xóa.

Bài 12. Vòng 1-2-3-4-5, Josephus $k=3$ . Liệt kê thứ tự loại.

C. Cài đặt cơ bản (CLO thao tác)

Bài 13. Cài đủ: KhoiTao, TaoNode, ThemDau, ThemCuoi, Xuat, IsEmpty, DemSoPhanTu, HuyDanhSach. Viết main menu.

Bài 14. Thêm: Tim, ThemTaiViTri, XoaDau, XoaCuoi, XoaNodeTheoGiaTri, XoaTaiViTri.

Bài 15. Tạo 50 số ngẫu nhiên $1..30$ vào list (thêm cuối). Đếm số chẵn, in node max, xóa min.

Bài 16. Tach(l, l1, l2): l1 nguyên tố, l2 còn lại. Không phá l.

D. Sắp xếp và trộn

Bài 17. SapXep tăng dần bằng hoán đổi giá trị. In trước/sau.

Bài 18. Viết SapXepGiam. So sánh số lần swap với bản tăng trên cùng dữ liệu.

Bài 19. Noi(l1, l2, l3) hai list đã sort. Test: l1 = 1..10, l2 = 5..15.

Bài 20 (nâng cao). Cài MergeSortList. So thời gian (clock) với SapXep khi $n = 5000$ .

E. Kép và vòng

Bài 21. Cài DSLK kép: thêm đầu/cuối, xóa đầu/cuối, xuất xuôi/ngược, hủy.

Bài 22. Từ DSLK đơn, xây DSLK kép cùng dữ liệu (duyệt đơn, ThemCuoiKep).

Bài 23. Cài vòng đơn với pTail: thêm đầu, thêm cuối, xuất, xóa giá trị.

Bài 24. Josephus $n$ , $k$ nhập từ bàn phím.

Bài 25. Playlist: vòng kép, lệnh next / prev / insert after current / delete current / lặp vô hạn in 20 bước.

F. Ứng dụng và cao cấp

Bài 26. Đa thức. Nút {double coef; int exp; NODE* pNext} sắp theo mũ giảm. Viết cộng và tính $P(x_0)$ .

Bài 27. Đảo list (iterative). Kiểm tra bằng xuất xuôi.

Bài 28. Tìm nút giữa không đếm n. Tìm nút thứ $k$ từ cuối.

Bài 29. Viết CoChuTrinh. Tạo list có vòng (gán pTail->pNext = pHead->pNext) để test, nhớ cắt vòng trước khi HuyDanhSach.

Bài 30. Cho hai list số nguyên đã sort, in các giá trị giao (intersection) theo thứ tự tăng, mỗi giá trị một lần.

Bài 31. Kiểm tra list số nguyên có palindrome không.

Bài 32 (khó). Copy list có thêm con trỏ random (trỏ tới nút bất kỳ). Kết quả là list mới, random trỏ đúng nút tương ứng trên list mới. $O(n)$ thời gian.

G. Câu hỏi tự luận / kiểm tra miệng

Trình bày hình thức tổ chức tuần tự và liên kết. Vẽ sơ đồ.
Viết mã giả thêm đầu, thêm cuối, xóa đầu DSLK đơn có pHead/pTail. Phân tích $O$ .
Vì sao Merge Sort hợp DSLK hơn Quick Sort? Nêu thuật toán tìm giữa.
So sánh DSLK đơn, kép, vòng: cấu trúc nút, thao tác đặc trưng, một ứng dụng mỗi loại.
Liệt kê các lỗi bộ nhớ khi cài DSLK và cách tránh.

🎯 TÓM TẮT CHƯƠNG 3

Kiến thức cốt lõi

Con trỏ + Heap là nền: new/delete, NULL, ->, không giải tham chiếu bừa, không leak.
Cấp phát tuần tự (mảng): a[i] $O(1)$ , chèn giữa $O(n)$ .
Cấp phát liên kết (DSLK): chèn/xóa tại chỗ $O(1)$ , truy cập thứ $i$ là $O(n)$ .
DSLK đơn: NODE + LIST(pHead, pTail). Thêm đầu/cuối $O(1)$ , xóa cuối $O(n)$ .
Sắp xếp: đề thi dùng đổi chỗ trực tiếp trên data — hàm SapXep $O(n^2)$ ; thực tế trên DSLK nên Merge Sort $O(n \log n)$ .
DSLK kép: mỗi nút pPrev + pNext. Thêm trước / xóa nút đang cầm / xóa cuối $O(1)$ ; duyệt hai chiều; tốn thêm 1 con trỏ/nút. Ứng dụng: Back/Forward, Undo/Redo, LRU, deque (mục 3.4.1).
DSLK vòng: đuôi nắm đầu; chỉ giữ pTail (head = pTail->pNext). Duyệt do-while. Thêm đầu/cuối $O(1)$ , xóa cuối vòng đơn vẫn $O(n)$ . Round-robin, Josephus; vòng kép = ghép kép + vòng (mục 3.4.2).

Câu thần chú khi viết code

Nút mới: pNext = NULL trước khi nối (vòng 1 nút: pNext = p, tự trỏ mình).
Đổi liên kết: giữ địa chỉ phần còn lại trước khi ghi đè con trỏ.
Thêm/xóa: luôn xét rỗng / một nút / nút đầu / nút cuối.
Có pTail thì mọi nhánh thêm/xóa ảnh hưởng cuối phải cập nhật pTail.
Kép: mỗi mối nối sửa hai chiều — a->pNext = b kèm b->pPrev = a.
Vòng: không while (p != NULL); hủy phải cắt vòng (pTail->pNext = NULL) rồi mới delete.
Hết việc: HuyDanhSach.

Liên kết chương sau

Chương 4: Stack = thêm/xóa đầu DSLK; Queue = xóa đầu + thêm cuối.
Chương 5: Cây = nút có 2 (hoặc nhiều) con trỏ, không còn tuyến tính.
Đồ thị: danh sách kề là mảng các DSLK.

Hết chương 3. Làm bài tập 13–19 trước khi sang chương 4; bài 21–25 sau khi đọc 3.4 (kép và vòng); bài 20 và 26–32 là mức cao cấp.

🎯 MỤC TIÊU CHƯƠNG 3​

📋 NỘI DUNG CHƯƠNG 3​

📖 CÁCH ĐỌC TÀI LIỆU NÀY (TỪ ZERO ĐẾN HERO)​

📚 BẢNG THUẬT NGỮ​

3.1. GIỚI THIỆU ĐỐI TƯỢNG DỮ LIỆU CON TRỎ​

3.1.1. Bộ nhớ máy tính: biến, địa chỉ, giá trị​

3.1.2. Con trỏ là gì?​

Khai báo và hai toán tử bắt buộc​

3.1.3. Con trỏ NULL và con trỏ hoang​

3.1.4. Con trỏ và struct — toán tử ->​

3.1.5. Stack và Heap — hai “kho” bộ nhớ​

3.1.6. Cấp phát động trong C: malloc, calloc, free​

3.1.7. Cấp phát động trong C++: new / delete​

3.1.8. Bốn lỗi con trỏ “chết người” trong DSLK​

3.1.9. Con trỏ cấp hai (NODE**) và truyền tham chiếu​

3.1.10. Con trỏ và mảng (để đối chiếu với DSLK)​

3.1.11. Ví dụ tổng hợp: tạo 3 node rời rồi nối tay​

✅ Kiểm tra nhanh 3.1​

3.2. DANH SÁCH LIÊN KẾT (DSLK)​

3.2.1. Định nghĩa DSLK​

A. Danh sách tuyến tính (ôn lại)​

B. Định nghĩa danh sách liên kết​

C. Nút (NODE) — viên gạch của DSLK​

D. So sánh mảng và DSLK (nắm để chọn đúng cấu trúc)​

E. Định nghĩa hình thức (toán học) — có thể bỏ qua lần đọc đầu​

3.2.2. Các hình thức tổ chức DSLK​

A. Tổ chức tuần tự (sequential allocation)​

B. Tổ chức liên kết (linked allocation) — trọng tâm chương​

C. Danh sách liên kết tĩnh (cursor / mảng nút)​

D. Phân loại theo chiều liên kết và hình dạng​

E. Biến thể tổ chức: có / không có nút giả (dummy / header node)​

F. Tổ chức quản lý danh sách: chỉ pHead hay thêm pTail?​

✅ Kiểm tra nhanh 3.2​

3.3. DSLK ĐƠN​

3.3.1. Tổ chức DSLK đơn theo cách cấp phát liên kết​

A. Khai báo cấu trúc — học thuộc, viết đúng trong mọi bài​

B. Khởi tạo danh sách rỗng​

C. Tạo một nút — đơn vị cấp phát​

D. Mô hình cấp phát khi thêm lần lượt 10, 20, 30 vào cuối​

E. Duyệt danh sách — thao tác nền của mọi thuật toán​

F. Hai cách “cầm” danh sách trong hàm​

3.3.2. Các thao tác cơ bản trên DSLK đơn​

① Tìm kiếm theo giá trị​

② Thêm vào đầu — O(1)O(1)O(1) — thao tác “rẻ” nhất của DSLK đơn​

③ Thêm vào cuối — O(1)O(1)O(1) nhờ pTail​

④ Thêm sau một nút q cho trước — O(1)O(1)O(1)​

⑤ Thêm trước một nút q — O(n)O(n)O(n) trên DSLK đơn​

⑥ Thêm tại vị trí k (k đếm từ 0)​

⑥b. Lấy phần tử thứ kkk (truy cập)​

⑦ Xóa đầu — O(1)O(1)O(1)​

⑧ Xóa cuối — O(n)O(n)O(n) trên DSLK đơn​

⑨ Xóa sau nút q — O(1)O(1)O(1) nếu đã có q​

⑩ Xóa theo giá trị (nút đầu tiên có data == x)​

⑩b. Xóa tại vị trí kkk (đếm từ 0)​

⑪ Tìm min / max, thống kê — mẫu đề thi​

⑫ Tách danh sách theo điều kiện (mẫu đề thi)​

⑬ Hủy toàn bộ danh sách — chống memory leak​

⑭ Bảng tổng hợp độ phức tạp DSLK đơn (pHead + pTail)​

⑮ Ví dụ chạy tay cả chuỗi thao tác (đọc để “thấy” pHead / pTail)​

⑯ Chương trình tối thiểu — copy, biên dịch, chạy được​

3.3.3. Sắp xếp danh sách​

A. Đổi chỗ trực tiếp — hàm SapXep đúng giáo trình / đề thi​

B. Bubble Sort trên DSLK​

C. Insertion Sort bằng relink nút — O(n2)O(n^2)O(n2), hợp DSLK​

D. Trộn hai danh sách đã sắp — O(n+m)O(n+m)O(n+m) (mẫu đề thi)​

E. Merge Sort trên DSLK — thuật toán “cao cấp” nên dùng thật​

F. Ưu / nhược khi sắp xếp trên DSLK​

✅ Kiểm tra nhanh 3.3​

3.4. MỘT SỐ DSLK KHÁC​

3.4.1. DSLK kép (Doubly Linked List)​

A. Vì sao cần kép? Định nghĩa​

B. Tổ chức DNODE / DLIST và bất biến​

C. Dựng list và duyệt hai chiều​

D. Thêm đầu / thêm cuối — cả hai O(1)O(1)O(1)​

① Thêm đầu — O(1)O(1)O(1)​

② Thêm cuối — O(1)O(1)O(1)​

E. Thêm sau / thêm trước / thêm tại vị trí​

③ Thêm sau nút q — O(1)O(1)O(1) nếu đã cầm q​

④ Thêm trước nút q — O(1)O(1)O(1) ← thắng lợi so với đơn O(n)O(n)O(n)​

⑤ Thêm tại vị trí kkk (đếm từ 0)​

🎯 MỤC TIÊU CHƯƠNG 3

📋 NỘI DUNG CHƯƠNG 3

📖 CÁCH ĐỌC TÀI LIỆU NÀY (TỪ ZERO ĐẾN HERO)

📚 BẢNG THUẬT NGỮ

3.1. GIỚI THIỆU ĐỐI TƯỢNG DỮ LIỆU CON TRỎ

3.1.1. Bộ nhớ máy tính: biến, địa chỉ, giá trị

3.1.2. Con trỏ là gì?

Khai báo và hai toán tử bắt buộc

3.1.3. Con trỏ `NULL` và con trỏ hoang

3.1.4. Con trỏ và `struct` — toán tử `->`

3.1.5. Stack và Heap — hai “kho” bộ nhớ

3.1.6. Cấp phát động trong C: `malloc`, `calloc`, `free`

3.1.7. Cấp phát động trong C++: `new` / `delete`

3.1.8. Bốn lỗi con trỏ “chết người” trong DSLK

3.1.9. Con trỏ cấp hai (`NODE**`) và truyền tham chiếu

3.1.10. Con trỏ và mảng (để đối chiếu với DSLK)

3.1.11. Ví dụ tổng hợp: tạo 3 node rời rồi nối tay

✅ Kiểm tra nhanh 3.1

3.2. DANH SÁCH LIÊN KẾT (DSLK)

3.2.1. Định nghĩa DSLK

A. Danh sách tuyến tính (ôn lại)

B. Định nghĩa danh sách liên kết

C. Nút (NODE) — viên gạch của DSLK

D. So sánh mảng và DSLK (nắm để chọn đúng cấu trúc)

E. Định nghĩa hình thức (toán học) — có thể bỏ qua lần đọc đầu

3.2.2. Các hình thức tổ chức DSLK

A. Tổ chức tuần tự (sequential allocation)

B. Tổ chức liên kết (linked allocation) — trọng tâm chương

C. Danh sách liên kết tĩnh (cursor / mảng nút)

D. Phân loại theo chiều liên kết và hình dạng

E. Biến thể tổ chức: có / không có nút giả (dummy / header node)

F. Tổ chức quản lý danh sách: chỉ `pHead` hay thêm `pTail`?

✅ Kiểm tra nhanh 3.2

3.3. DSLK ĐƠN

3.3.1. Tổ chức DSLK đơn theo cách cấp phát liên kết

A. Khai báo cấu trúc — học thuộc, viết đúng trong mọi bài

B. Khởi tạo danh sách rỗng

C. Tạo một nút — đơn vị cấp phát

D. Mô hình cấp phát khi thêm lần lượt 10, 20, 30 vào cuối

E. Duyệt danh sách — thao tác nền của mọi thuật toán

F. Hai cách “cầm” danh sách trong hàm

3.3.2. Các thao tác cơ bản trên DSLK đơn

① Tìm kiếm theo giá trị

② Thêm vào đầu — $O(1)$ — thao tác “rẻ” nhất của DSLK đơn

③ Thêm vào cuối — $O(1)$ nhờ `pTail`

④ Thêm sau một nút `q` cho trước — $O(1)$

⑤ Thêm trước một nút `q` — $O(n)$ trên DSLK đơn

⑥ Thêm tại vị trí `k` (k đếm từ 0)

⑥b. Lấy phần tử thứ $k$ (truy cập)

⑦ Xóa đầu — $O(1)$

⑧ Xóa cuối — $O(n)$ trên DSLK đơn

⑨ Xóa sau nút `q` — $O(1)$ nếu đã có `q`

⑩ Xóa theo giá trị (nút đầu tiên có `data == x`)

⑩b. Xóa tại vị trí $k$ (đếm từ 0)

⑪ Tìm min / max, thống kê — mẫu đề thi

⑫ Tách danh sách theo điều kiện (mẫu đề thi)

⑬ Hủy toàn bộ danh sách — chống memory leak

⑭ Bảng tổng hợp độ phức tạp DSLK đơn (`pHead` + `pTail`)

⑮ Ví dụ chạy tay cả chuỗi thao tác (đọc để “thấy” pHead / pTail)

⑯ Chương trình tối thiểu — copy, biên dịch, chạy được

3.3.3. Sắp xếp danh sách

A. Đổi chỗ trực tiếp — hàm `SapXep` đúng giáo trình / đề thi

B. Bubble Sort trên DSLK

C. Insertion Sort bằng relink nút — $O(n^2)$ , hợp DSLK

D. Trộn hai danh sách đã sắp — $O(n+m)$ (mẫu đề thi)

E. Merge Sort trên DSLK — thuật toán “cao cấp” nên dùng thật

F. Ưu / nhược khi sắp xếp trên DSLK

✅ Kiểm tra nhanh 3.3

3.4. MỘT SỐ DSLK KHÁC

3.4.1. DSLK kép (Doubly Linked List)

A. Vì sao cần kép? Định nghĩa

B. Tổ chức `DNODE` / `DLIST` và bất biến

C. Dựng list và duyệt hai chiều

D. Thêm đầu / thêm cuối — cả hai $O(1)$

① Thêm đầu — $O(1)$

② Thêm cuối — $O(1)$

E. Thêm sau / thêm trước / thêm tại vị trí

③ Thêm sau nút `q` — $O(1)$ nếu đã cầm `q`

④ Thêm trước nút `q` — $O(1)$ ← thắng lợi so với đơn $O(n)$

⑤ Thêm tại vị trí $k$ (đếm từ 0)