Danh sách liên kết
Hãy nhớ lại nhược điểm của mảng: kích thước phải định trước, và nếu muốn chèn một phần tử vào giữa thì phải đẩy hàng loạt phần tử sang chỗ khác. Danh sách liên kết giải quyết đúng hai điểm này: nó lớn lên hay co lại tuỳ ý trong lúc chạy, và chèn hay xoá một phần tử chỉ cần đổi vài con trỏ. Danh sách liên kết được dựng nên từ struct và malloc mà bạn đã học, để dữ liệu co giãn tự do trong lúc chương trình chạy.
Hãy tưởng tượng bạn viết chương trình quản lý sinh viên đăng ký một môn học mà không biết trước sẽ có bao nhiêu em. Khai báo mảng 50 phần tử thì thiếu chỗ khi em thứ 51 đăng ký, mà khai báo mảng 10000 phần tử thì lãng phí khủng khiếp trong khi lớp chỉ có 40 em. Tệ hơn, sinh viên rút môn giữa kỳ, và với mảng thì xoá một em ở giữa buộc bạn dồn toàn bộ các em phía sau lên một ô.
Vấn đề gốc của mảng là nó đòi hỏi tất cả phần tử phải nằm liền khối trong bộ nhớ. Chính ràng buộc liền khối ấy sinh ra cả hai nhược điểm: phải biết trước tổng kích thước để xin đủ một dải bộ nhớ liên tục, và phải dồn phần tử khi chèn hay xoá để giữ dải ấy không bị thủng lỗ. Danh sách liên kết ra đời từ câu hỏi: nếu ta bỏ hẳn ràng buộc liền khối thì sao?
Câu trả lời là các phần tử được phép nằm rải rác khắp bộ nhớ, và ta giữ trật tự giữa chúng không phải bằng vị trí vật lý mà bằng cách cho mỗi phần tử cầm địa chỉ của phần tử kế tiếp. Trật tự chuyển từ chỗ nằm sang chỗ chỉ. Đây là lúc con trỏ trở thành công cụ không thể thiếu: cả bài này thực chất là một bài tập lớn về con trỏ, nên ai còn lơ mơ về ->, malloc hay Node ** thì nên quay lại bài con trỏ trước khi đi tiếp.
Thử ngay: xem danh sách liên kết chạy từng bước
Trình mô phỏng dưới đây dựng một danh sách nhỏ rồi duyệt nó. Hãy chú ý cột heap: mỗi nút là một thẻ trên bộ nhớ động, và trường next của nó hoặc trỏ tới (->) một nút khác, hoặc mang NULL ở nút cuối. Con trỏ head trên stack luôn trỏ tới nút đầu.
1int main(void) {2 Node *head = NULL;3 themCuoi(&head, 10);4 themCuoi(&head, 20);5 themDau(&head, 5);6 inDanhSach(head);7 return 0;8}
Nút là gì
Một nút (node) là một struct gồm hai phần: phần dữ liệu (ví dụ một số nguyên), và một con trỏ tên next trỏ tới nút kế tiếp. Nhiều nút nối đuôi nhau qua con trỏ next tạo thành danh sách liên kết đơn. Nút cuối có next bằng NULL để báo hết danh sách. Ta chỉ cần giữ một con trỏ head trỏ tới nút đầu là đủ đi tới mọi nút.
Hình dung một cuộc truy tìm kho báu: mỗi nút là một mẩu giấy đặt đâu đó trong thành phố, trên mẩu giấy có một phần dữ liệu và một địa chỉ dẫn tới mẩu giấy tiếp theo. Bạn không cần biết mọi mẩu giấy nằm ở đâu, chỉ cần biết mẩu đầu tiên, rồi cứ đi theo địa chỉ ghi trên mỗi mẩu là tới hết. Mẩu cuối ghi NULL, nghĩa là hết đường.
Hai hệ quả rút ra ngay, và cả bài còn lại chỉ là khai triển chúng. Thứ nhất, con trỏ head là sinh mạng của cả danh sách: mất head là mất đường vào, mọi nút phía sau vẫn nằm nguyên trong bộ nhớ nhưng không còn cách nào chạm tới. Thứ hai, ta chỉ đi được một chiều và tuần tự: không nhảy thẳng tới nút thứ năm mà không qua bốn nút trước, cũng không lùi lại nút trước đó, vì mẩu giấy chỉ ghi địa chỉ đi tới chứ không ghi địa chỉ quay về. Đó là cái giá phải trả cho sự linh hoạt.
#include <stdio.h>
#include <stdlib.h> // for malloc, free
typedef struct Node {
int data; // the value stored in this node
struct Node *next; // pointer to the next node
} Node;
Lưu ý dòng struct Node *next; phải dùng tên struct Node đầy đủ vì lúc đó typedef chưa kết thúc nên tên rút gọn Node chưa dùng được bên trong.
Tạo một nút mới bằng malloc
Vì số nút không biết trước, ta xin bộ nhớ cho từng nút lúc chạy bằng malloc. Mỗi nút nằm trên heap (bộ nhớ động). Hàm dưới tạo một nút, đặt dữ liệu, đặt next bằng NULL, rồi trả con trỏ về.
Node *taoNut(int giaTri) {
Node *p = (Node *) malloc(sizeof(Node)); // ask for memory
if (p == NULL) { // malloc may fail
printf("Het bo nho!\n");
exit(1);
}
p->data = giaTri; // set the data field
p->next = NULL; // not linked to anything yet
return p;
}
Mỗi malloc cần một free tương ứng khi không còn dùng nút nữa, nếu không sẽ rò rỉ bộ nhớ. Với danh sách liên kết, lúc kết thúc phải duyệt và free từng nút.
Thêm nút vào đầu và vào cuối
Thêm vào đầu là thao tác nhanh nhất, chỉ ba bước: tạo nút mới, cho next của nó trỏ tới head cũ, rồi cho head trỏ tới nút mới. Vì head có thể thay đổi, ta truyền địa chỉ của head (kiểu Node **) vào hàm để sửa được biến gốc.
void themDau(Node **head, int giaTri) {
Node *moi = taoNut(giaTri);
moi->next = *head; // new node points to old first node
*head = moi; // head now points to the new node
}
Thứ tự hai dòng trong themDau là bắt buộc và đây là chi tiết quyết định. Ta phải cho next của nút mới trỏ tới head cũ trước, rồi mới cho head trỏ tới nút mới. Nếu làm ngược lại, tức gán *head = moi; trước, thì địa chỉ của nút đầu cũ không còn được ai giữ nữa: nút mới chưa kịp trỏ tới nó, mà head thì đã bỏ nó để trỏ sang chỗ khác. Toàn bộ danh sách cũ lập tức trở thành bộ nhớ mồ côi, vẫn chiếm chỗ nhưng không sao chạm tới được. Nguyên tắc chung khi thao tác trên con trỏ: luôn nối dây mới trước khi cắt dây cũ.
Cũng cần nói rõ vì sao hàm nhận Node **head chứ không phải Node *head. Hàm này phải làm cho biến head ngoài main trỏ sang một nút khác, tức là nó phải sửa chính con trỏ đó. Theo quy tắc đã học ở bài con trỏ, muốn hàm sửa được biến kiểu T thì phải truyền cho nó T *; ở đây T chính là Node *, nên tham số phải là Node **. Nếu chỉ nhận Node *head, hàm sẽ có một bản sao của con trỏ, gán lại bản sao chẳng ảnh hưởng gì tới main, và danh sách bên ngoài không hề thay đổi. Đây là lỗi kinh điển khi lần đầu viết danh sách liên kết.
Thêm vào cuối phải đi từ head tới nút cuối (nút có next bằng NULL) rồi gắn nút mới vào đó. Nếu danh sách đang rỗng thì nút mới chính là nút đầu.
void themCuoi(Node **head, int giaTri) {
Node *moi = taoNut(giaTri);
if (*head == NULL) { // empty list
*head = moi;
return;
}
Node *p = *head;
while (p->next != NULL) // walk to the last node
p = p->next;
p->next = moi; // attach new node at the end
}
Hãy so sánh chi phí của hai hàm vừa viết, vì đây là bài học lớn nhất về danh sách liên kết. themDau làm đúng ba việc bất kể danh sách có 5 nút hay 5 triệu nút, nên chi phí của nó là hằng số. themCuoi thì phải đi bộ từ head tới tận cuối, nên danh sách càng dài nó càng chậm, chi phí tỷ lệ với số nút. Trong hàng loạt bài toán, sự chênh lệch này lớn tới mức người ta chấp nhận xây danh sách theo thứ tự ngược rồi đảo lại một lần ở cuối, hoặc giữ thêm một con trỏ tail luôn trỏ tới nút cuối để themCuoi cũng thành hằng số.
Chú ý điều kiện dừng của vòng lặp là p->next != NULL chứ không phải p != NULL. Ta muốn dừng lại tại nút cuối để còn gắn nút mới vào nó, chứ không muốn đi quá nút cuối. Nếu viết nhầm thành while (p != NULL) p = p->next; thì khi vòng lặp kết thúc p đã là NULL, và dòng p->next = moi; ngay sau đó truy cập gián tiếp một con trỏ NULL khiến chương trình sập.
Duyệt danh sách
Duyệt là đi từ head, in dữ liệu từng nút, rồi nhảy sang nút sau bằng p = p->next, cho tới khi gặp NULL. Đây là khuôn mẫu lặp lại trong hầu hết thao tác trên danh sách.
void inDanhSach(Node *head) {
Node *p = head;
while (p != NULL) { // until end of list
printf("%d -> ", p->data);
p = p->next; // move to next node
}
printf("NULL\n");
}
Có một chi tiết trông vụn vặt nhưng cực kỳ quan trọng: hàm dùng một con trỏ tạm p chứ không chạy thẳng trên head. Nếu viết while (head != NULL) { ...; head = head->next; } thì tuy chương trình vẫn in ra đúng, ta đã phá hỏng một nguyên tắc. Ở đây head là bản sao nên main không bị ảnh hưởng, nhưng thói quen chạy trực tiếp trên con trỏ đầu sẽ giết bạn ngay khi hàm nhận Node **head, hoặc khi bạn cần dùng lại head ở phần sau của chính hàm đó. Hãy tập phản xạ: con trỏ đầu là thứ thiêng liêng, muốn đi thì đi bằng con trỏ tạm.
Vòng lặp while (p != NULL) { ...; p = p->next; } là khuôn mẫu duyệt, và nó xuất hiện lại y nguyên trong hầu hết thao tác còn lại: đếm nút, tính tổng, tìm kiếm, giải phóng bộ nhớ. Khi gặp một bài toán mới trên danh sách, câu hỏi đầu tiên nên là "khuôn mẫu duyệt này có đủ không, hay tôi cần thêm một con trỏ chạy sau nữa".
Xoá một nút
Xoá là thao tác dễ sai nhất trên danh sách liên kết, vì nó đụng cùng lúc tới ba thứ: con trỏ của nút đứng trước, con trỏ head, và vùng nhớ của nút bị xoá. Ý tưởng thì đơn giản. Muốn xoá nút p, ta phải làm cho nút đứng ngay trước p trỏ vượt qua p để tới p->next, tức là nối tắt qua nút cần xoá, rồi mới trả vùng nhớ của p về cho hệ thống bằng free.
Vấn đề là ở danh sách liên kết đơn, từ nút p không có cách nào tìm ngược ra nút đứng trước nó, vì mũi tên chỉ đi một chiều. Cách giải là cho hai con trỏ cùng đi, một cái p để dò tìm và một cái truoc luôn chạy sau p đúng một bước. Khi p tìm thấy nút cần xoá thì truoc đã sẵn ở đúng vị trí cần thiết.
void xoaNut(Node **head, int giaTri) {
Node *p = *head;
Node *truoc = NULL; // walks one step behind p
while (p != NULL && p->data != giaTri) {
truoc = p; // remember the current node
p = p->next; // then move forward
}
if (p == NULL) return; // value not found, nothing to delete
if (truoc == NULL) { // p is the first node: head must move
*head = p->next;
} else { // link the previous node past p
truoc->next = p->next;
}
free(p); // only now release the memory
}
Hàm này gói gọn bốn tình huống mà mọi thao tác xoá đều phải xử lý. Danh sách rỗng: vòng lặp không chạy lần nào, p là NULL ngay từ đầu, hàm thoát an toàn. Không tìm thấy giá trị: p chạy tới hết và thành NULL, hàm thoát mà không đụng gì. Xoá nút đầu: khi ấy truoc vẫn là NULL vì p chưa bước lần nào, và đó chính là dấu hiệu để biết phải dịch head chứ không phải dịch truoc->next. Xoá nút giữa hay nút cuối: truoc->next = p->next; xử lý được cả hai, vì nếu p là nút cuối thì p->next là NULL và truoc trở thành nút cuối mới một cách tự nhiên.
Chú ý thứ tự ở hai dòng cuối: nối tắt trước, free sau. Nếu free(p) trước rồi mới đọc p->next thì ta đang đọc một vùng nhớ đã trả lại cho hệ thống. Vẫn đúng nguyên tắc lúc nãy: nối dây mới xong xuôi rồi mới cắt. Điều kiện p != NULL && p->data != giaTri cũng không đặt tuỳ tiện: nhờ tính dừng sớm của phép "và", khi p đã là NULL thì C không tính vế phải nữa, nên p->data không bao giờ bị đọc trên một con trỏ NULL. Đảo hai vế lại là chương trình sập ngay khi duyệt hết danh sách mà không tìm thấy.
Xem xoá một nút chạy từng bước
Trình mô phỏng dưới đây xoá nút giữa mang giá trị 20 khỏi danh sách head -> #H1(10) -> #H2(20) -> #H3(30) -> NULL. Hãy chú ý cặp con trỏ p và truoc: p dò tìm, còn truoc luôn chạy sau một bước để lát nữa còn nối lại. Đây là mặt trái của chèn: chèn thêm một mắt xích, xoá thì bắc cầu vượt qua một mắt xích rồi trả nó về hệ thống.
1void xoaNut(Node **head, int giaTri) {2 Node *p = *head;3 Node *truoc = NULL;4 while (p != NULL && p->data != giaTri) {5 truoc = p;6 p = p->next;7 }8 if (p == NULL) return;9 if (truoc == NULL) *head = p->next;10 else truoc->next = p->next;11 free(p);12}
Giải phóng toàn bộ danh sách
Mỗi nút được sinh ra bằng một lần malloc, nên mỗi nút phải được thu về bằng một lần free. Không làm vậy thì bộ nhớ đã xin vẫn bị đánh dấu là đang dùng cho tới khi chương trình kết thúc, dù không còn ai chạm tới nó. Hiện tượng ấy gọi là rò rỉ bộ nhớ (memory leak). Với một bài tập nhỏ thì vô hại, nhưng với một chương trình chạy liên tục nhiều ngày, rò rỉ tích luỹ dần cho tới lúc ăn hết bộ nhớ máy.
void giaiPhong(Node **head) {
Node *p = *head;
while (p != NULL) {
Node *sau = p->next; // save the next pointer BEFORE freeing p
free(p); // now p is invalid, must not be touched again
p = sau; // continue from the saved pointer
}
*head = NULL; // the list is empty now, say so
}
Biến tạm sau là bắt buộc chứ không phải cho gọn. Sau khi free(p) chạy xong, vùng nhớ của nút đã được trả về hệ thống và mọi thứ bên trong nó, kể cả trường next, đều không còn đáng tin. Viết free(p); p = p->next; là đọc trường next của một nút đã chết, và đây là lỗi rất hiểm: nó thường vẫn chạy đúng trên máy bạn vì hệ thống chưa kịp dùng lại vùng nhớ đó, rồi sập trên máy khác hoặc sập khi dữ liệu lớn hơn. Phải lưu p->next ra một chỗ an toàn trước khi free.
Dòng cuối *head = NULL; cũng không thừa. Sau khi giải phóng, biến head ngoài main vẫn đang giữ địa chỉ của nút đầu, mà nút đầu đã bị free rồi, nên head đã trở thành một con trỏ treo. Đặt nó về NULL biến một cái bẫy im lặng thành một trạng thái trung thực và kiểm tra được.
Ghép mọi hàm đã viết lại với nhau (đặt ngay sau khối khai báo Node ở đầu bài, tức đã có
stdio.h và stdlib.h), ta được một chương trình chạy trọn vẹn.
int main(void) {
Node *head = NULL;
themCuoi(&head, 10);
themCuoi(&head, 20);
themDau(&head, 5);
inDanhSach(head); // 5 -> 10 -> 20 -> NULL
xoaNut(&head, 10);
inDanhSach(head); // 5 -> 20 -> NULL
giaiPhong(&head); // free every node, head becomes NULL
inDanhSach(head); // NULL
return 0;
}
Toàn bộ danh sách chỉ có đúng một lối vào là head. Ghi đè head mà chưa kịp giữ lại địa chỉ nút đầu cũ ở đâu đó, và lập tức mọi nút trở thành bộ nhớ mồ côi: chúng vẫn nằm nguyên trên vùng nhớ động, vẫn bị tính là đang dùng, nhưng không một dòng mã nào còn có thể chạm tới để dùng lại hay để free. Đây vừa là mất dữ liệu vừa là rò rỉ bộ nhớ, và nó xảy ra tức thì chỉ trong một dòng gán.
Ba tình huống hay gây ra nó. Một là đảo thứ tự trong themDau, gán *head = moi; trước khi cho moi->next trỏ về nút đầu cũ. Hai là dùng thẳng head làm con trỏ chạy khi duyệt, thay vì dùng một con trỏ tạm. Ba là gán head = NULL; để "xoá danh sách" mà quên free từng nút trước đó.
Nguyên nhân gốc chung là quên rằng head không phải một biến thường mà là đường đi duy nhất tới một khối dữ liệu. Cách phòng vệ thì đơn giản đến mức máy móc: mọi thao tác duyệt đều đi bằng con trỏ tạm, và mọi thao tác đổi head đều phải bảo đảm nút đầu cũ vẫn còn ai đó cầm địa chỉ trước khi head buông tay.
So sánh mảng và danh sách liên kết
Cả hai đều lưu một dãy phần tử, nhưng mạnh yếu khác nhau. Mảng nằm liền khối nên truy cập phần tử thứ i tức thì qua chỉ số, nhưng kích thước cứng nhắc và chèn hay xoá giữa thì tốn công dồn. Danh sách liên kết co giãn tự do và chèn hay xoá nhanh nếu đã ở đúng chỗ, nhưng muốn tới phần tử thứ i phải đi lần từ đầu, và mỗi nút tốn thêm bộ nhớ cho con trỏ next.
| Tiêu chí | Mảng | Danh sách liên kết đơn |
|---|---|---|
| Bố trí bộ nhớ | liền khối, các phần tử kề nhau | rải rác, nối nhau bằng con trỏ next |
| Kích thước | cố định khi khai báo | co giãn tuỳ ý lúc chạy |
Truy cập phần tử thứ i | tức thì qua chỉ số a[i] | phải duyệt từ head, chậm |
| Chèn hay xoá ở đầu | tốn công dồn các phần tử | rất nhanh, chỉ đổi vài con trỏ |
| Bộ nhớ phụ | không | mỗi nút tốn thêm chỗ cho con trỏ |
| Cấp phát | thường tĩnh, đơn giản | động qua malloc và free, dễ rò rỉ |
Chọn mảng khi số phần tử ổn định và cần truy cập ngẫu nhiên nhanh theo chỉ số. Chọn danh sách liên kết khi số phần tử thay đổi nhiều, hay thêm hoặc xoá ở đầu danh sách, và ít cần nhảy thẳng tới phần tử giữa.
Bảng trên nói cái gì nhanh cái gì chậm, nhưng cái vì sao mới đáng nhớ. Mọi dòng trong bảng đều suy ra từ một sự thật duy nhất đã nêu ở đầu bài: mảng nằm liền khối, danh sách nằm rải rác. Vì mảng liền khối nên máy tính được địa chỉ của phần tử thứ i chỉ bằng một phép nhân và một phép cộng; cũng vì liền khối nên muốn chèn vào giữa thì phải dồn để giữ dải liên tục. Vì danh sách rải rác nên chèn hay xoá chỉ là đổi vài con trỏ; cũng vì rải rác nên không có công thức nào tính ra địa chỉ nút thứ i, buộc phải lần từ head.
Có một chi phí ẩn mà bảng không ghi được, đó là tính cục bộ bộ nhớ. Bộ xử lý hiện đại đọc bộ nhớ theo từng khối lớn và giữ lại trong bộ nhớ đệm, nên khi duyệt một mảng, việc đọc phần tử đầu đã kéo sẵn hàng chục phần tử sau vào đệm và chúng gần như miễn phí. Danh sách liên kết thì mỗi nút nằm một nơi ngẫu nhiên, mỗi bước nhảy p = p->next là một lần truy cập tới vùng nhớ mà bộ đệm chưa có sẵn. Kết quả là duyệt tuần tự một mảng thường nhanh hơn duyệt danh sách nhiều lần, dù trên giấy tờ cả hai đều đi qua từng phần tử một.
Vậy khi nào danh sách liên kết thật sự đáng dùng? Khi thao tác chủ yếu là thêm và xoá ở đầu, hoặc khi ta dựng những cấu trúc lớn hơn như ngăn xếp, hàng đợi, bảng băm và cây, vốn đều dùng nút nối bằng con trỏ. Với người học, giá trị lớn nhất của bài này không nằm ở chỗ danh sách liên kết nhanh hay chậm, mà ở chỗ nó buộc bạn thành thạo con trỏ và bộ nhớ động, hai thứ chi phối mọi cấu trúc dữ liệu về sau.
Bài tập thực hành
Bài 1. Dùng kiểu Node trong bài, viết chương trình tạo một danh sách liên kết các số 1, 2, 3, 4, 5 bằng themCuoi, in danh sách, rồi xoá nút mang giá trị 3 và in lại. Nhớ free mọi nút trước khi kết thúc.
Gợi ý
Để xoá theo giá trị, giữ thêm con trỏ truoc chạy sau p một bước. Khi tìm thấy nút cần xoá: nếu nó là head thì cho head trỏ tới p->next, ngược lại cho truoc->next trỏ tới p->next để nối qua nó, rồi mới free(p). Cuối chương trình, duyệt và free từng nút; nhớ lưu p->next vào một biến tạm trước khi free(p).
Bài 2. Viết hàm int demNut(Node *head) trả về số nút của danh sách, và hàm int tongData(Node *head) trả về tổng các giá trị data. Viết main thử hai hàm này.
Gợi ý
Cả hai hàm dùng chung khuôn mẫu duyệt: cho p = head, lặp while (p != NULL) rồi p = p->next. Trong demNut mỗi vòng tăng biến đếm; trong tongData mỗi vòng cộng p->data vào tổng. Trả về biến tích luỹ sau vòng lặp.
Bài 3. Viết hàm int timKiem(Node *head, int x) trả về 1 nếu giá trị x có trong danh sách, ngược lại trả về 0. So sánh ý tưởng tìm kiếm này với tìm kiếm tuần tự trên mảng.
Gợi ý
Duyệt từ head, mỗi nút so p->data với x; nếu bằng thì trả về 1 ngay. Hết danh sách (gặp NULL) mà chưa thấy thì trả về 0. Ý tưởng giống tìm kiếm tuần tự trên mảng, chỉ khác cách đi tới phần tử sau: mảng tăng chỉ số, danh sách nhảy theo con trỏ next.
Bài 4 (nâng cao). Viết chương trình đọc một dãy số nguyên từ tệp songuyen.txt vào một danh sách liên kết (mỗi số một nút, thêm vào cuối), in danh sách, rồi đảo ngược danh sách bằng cách chỉ đổi các con trỏ next (không tạo nút mới) và in lại.
Gợi ý
Đọc tệp bằng while (fscanf(f, "%d", &x) == 1) và mỗi số gọi themCuoi. Để đảo ngược, dùng ba con trỏ truoc = NULL, hientai = head, sau. Mỗi vòng: lưu sau = hientai->next, cho hientai->next trỏ về truoc, rồi dịch truoc = hientai và hientai = sau. Khi hientai thành NULL, cho head = truoc.
Bài 5. Viết hàm void chenSauGiaTri(Node **head, int moc, int giaTri) chèn một nút mới mang giaTri vào ngay sau nút đầu tiên có dữ liệu bằng moc. Nếu không tìm thấy moc thì không làm gì. Vì sao hàm này không cần con trỏ truoc như hàm xoá?
Lời giải chi tiết
Câu hỏi cuối chính là điểm mấu chốt. Hàm xoá cần con trỏ truoc vì muốn xoá nút p thì phải sửa trường next của nút đứng trước p, mà từ p không có đường đi ngược. Còn ở đây ta chèn vào sau nút mốc, nên thứ cần sửa là trường next của chính nút mốc, thứ mà ta đang cầm trong tay. Không cần nhìn lui thì không cần con trỏ chạy sau.
Đây là nhận xét tổng quát rất đáng nhớ: trên danh sách liên kết đơn, mọi thao tác chỉ cần nhìn tới đều làm được với một con trỏ, còn thao tác nào cần nhìn lui đều phải trả giá bằng một con trỏ thứ hai.
Thứ tự hai dòng nối cũng lại là vấn đề quen thuộc. Nút mới phải trỏ tới phần đuôi cũ trước, rồi nút mốc mới được trỏ sang nút mới. Đảo lại là đứt luôn phần đuôi.
void chenSauGiaTri(Node **head, int moc, int giaTri) {
Node *p = *head;
while (p != NULL && p->data != moc) { // find the anchor node
p = p->next;
}
if (p == NULL) return; // anchor not found, do nothing
Node *moi = taoNut(giaTri);
moi->next = p->next; // new node takes over the old tail
p->next = moi; // only then the anchor points to it
}
Chú ý hàm vẫn nhận Node **head dù nó không hề sửa head. Lý do là để giữ giao diện đồng nhất với các hàm còn lại, và để phòng khi về sau ta muốn mở rộng nó, chẳng hạn cho phép chèn vào danh sách rỗng. Nếu muốn chặt chẽ hơn thì nhận Node *head cũng chạy đúng, vì thao tác này không bao giờ đụng tới nút đầu.
Ý chính: chèn sau một nút đã cầm trong tay là thao tác chi phí hằng số và chỉ cần một con trỏ; chính điều này là thế mạnh lớn nhất của danh sách liên kết so với mảng.
Tự kiểm tra
Vì sao thêm nút vào đầu danh sách lại nhanh hơn nhiều so với chèn vào đầu mảng?
Thêm vào đầu danh sách chỉ cần tạo một nút mới, cho next của nó trỏ tới head cũ rồi cho head trỏ tới nút mới: cố định ba thao tác, không phụ thuộc số phần tử. Chèn vào đầu mảng phải đẩy toàn bộ các phần tử hiện có lùi một ô để chừa chỗ, nên chi phí tăng theo số phần tử. Danh sách chỉ đổi vài con trỏ, mảng phải dồn cả dãy.
Làm sao chương trình biết đã duyệt tới nút cuối của danh sách?
Nút cuối có con trỏ next bằng NULL. Khi duyệt, sau mỗi bước ta gán p = p->next; tới nút cuối thì p->next là NULL nên p trở thành NULL và điều kiện while (p != NULL) sai, vòng lặp dừng. Chính giá trị NULL ở next của nút cuối là dấu hết danh sách.
Câu hỏi tự kiểm
- 1Trong danh sách liên kết đơn, con trỏ next của nút cuối mang giá trị gì để báo hết danh sách?
- 2Trong hàm themDau, thứ tự nối đúng hai con trỏ là gì?
- 3Vì sao hàm cần thay đổi head phải nhận tham số kiểu Node ** chứ không phải Node *?
- 4Khi giải phóng danh sách, vì sao phải lưu p->next ra biến tạm trước khi gọi free(p)?
Tóm tắt
Danh sách liên kết sinh ra từ việc bỏ đi một ràng buộc của mảng: ràng buộc các phần tử phải nằm liền khối. Bỏ nó đi thì kích thước không cần biết trước và chèn xoá không cần dồn phần tử, nhưng đổi lại ta mất khả năng nhảy thẳng tới phần tử thứ i và mất luôn cả lợi thế của bộ nhớ đệm. Không có cấu trúc nào tốt hơn tuyệt đối, chỉ có cấu trúc hợp hay không hợp với thao tác mà bài toán cần làm nhiều nhất.
Về kỹ thuật, mọi thứ trong bài đều quy về con trỏ. Mỗi nút là một struct do malloc cấp trên vùng nhớ động, giữ dữ liệu và một trường next trỏ tới nút sau, với nút cuối mang NULL. Con trỏ head là đường đi duy nhất vào danh sách. Hàm nào cần đổi head thì phải nhận Node **, vì muốn sửa một biến kiểu Node * thì phải truyền địa chỉ của nó.
Ba quy tắc dưới đây phòng được gần hết lỗi mà người mới mắc phải. Thứ nhất, luôn nối dây mới trước khi cắt dây cũ, vì cắt trước là mất luôn phần đuôi. Thứ hai, luôn duyệt bằng con trỏ tạm và không bao giờ chạy trực tiếp trên head. Thứ ba, lưu p->next ra biến tạm trước khi gọi free(p), vì sau free thì mọi thứ bên trong nút đều không còn đáng tin.
Cuối cùng, mỗi malloc phải có một free tương ứng. Rò rỉ bộ nhớ không làm chương trình sập ngay nên rất dễ bỏ qua trong bài tập nhỏ, nhưng nó là thói quen phải rèn từ bây giờ, vì trong một hệ thống chạy dài ngày thì rò rỉ luôn là thứ giết chương trình sau cùng.
Mỗi nút của danh sách liên kết đơn là một struct chứa dữ liệu và con trỏ next trỏ tới nút sau, với nút cuối mang next bằng NULL. Ta tạo nút động bằng malloc, thêm đầu hoặc cuối, duyệt bằng cách lần theo con trỏ next, và luôn free mọi nút khi xong. So với mảng, danh sách liên kết đổi truy cập nhanh theo chỉ số lấy sự linh hoạt về kích thước và thao tác thêm hay xoá ở đầu.