Đây là bài viết số 2 thuộc bài học Cấp phát bộ nhớ động và Danh sách liên kết của chuyên đề lập trình C++ cơ bản. Để nắm vững bài viết này, trước tiên các bạn hãy tìm đọc lại các bài viết trước đây gồm các kiến thức liên quan:
- Địa chỉ ảo, Tham chiếu và Con trỏ trong C++.
- Hoạt động nâng cao với con trỏ trong C++.
- Kĩ thuật Cấp phát bộ nhớ động trong C++.
I. Giới thiệu chung
Đối với những ai học lập trình, bất kể cơ bản hay nâng cao, cấu trúc dữ liệu mảng luôn luôn là một cấu trúc dữ liệu được nghiên cứu đầu tiên, vì nó quá đơn giản và quen thuộc. Giả sử chúng ta cần phải lưu trữ một dãy số và tính trung bình cộng của nó, mảng là sự lựa chọn không thể tuyệt vời hơn. Đặc biệt, sức mạnh của mảng đến từ khả năng truy cập vị trí ngẫu nhiên trên mảng bằng chỉ số chỉ trong O[1]O[1].
Tuy nhiên, không phải mảng không có hạn chế. Một số vấn đề có thể sinh ra khi sử dụng mảng là:
- Bắt buộc phải biết trước số lượng phần tử của dãy số cần lưu trữ.
- Do các phần tử của mảng được lưu trữ trên một đoạn vị trí liên tiếp nhau trong bộ nhớ máy tính, nên khi cần tăng kích thước mảng hoặc thêm/xóa một phần tử vào vị trí bất kì trong mảng sẽ cần tới độ phức tạp O[n]O[n].
Để khắc phục những nhược điểm trên, người ta nghĩ ra một cấu trúc dữ liệu là danh sách liên kết.
Về bản chất, danh sách liên kết có chức năng giống như một mảng dùng để lưu trữ một tập các giá trị có cùng kiểu, nhưng nó được thiết kế để lưu trữ dãy số không biết trước số lượng phần tử hoặc các phần tử thường xuyên thay đổi dựa trên các con trỏ trỏ tới các phần tử trong danh sách. Nhờ thế, khi xóa một phần tử trong danh sách liên kết, nếu ta biết trước con trỏ trỏ vào phần tử đó, thì độ phức tạp của thao tác xóa chỉ là O[1]O[1]. Ngoài ra, các thao tác chèn phần tử vào đầu/cuối danh sách liên kết cũng có độ phức tạp chỉ là O[1]O[1].
Có ba kiểu danh sách liên kết: Danh sách liên kết đơn, Danh sách liên kết đôi và Danh sách liên kết vòng.
Trước khi tìm hiểu về danh sách liên kết, các bạn cần nắm vững kiến thức về con trỏ, bởi vì đây là một cấu trúc dữ liệu hoàn toàn sử dụng con trỏ để cài đặt.
II. Danh sách liên kết đơn
1. Định nghĩa
Danh sách liên kết đơn là một tập hợp các nodes được phân bố ngẫu nhiên trong bộ nhớ, và sắp xếp theo cách sao cho mỗi node chứa một giá trị [data] và một ***con trỏ [next]***. Con trỏ sẽ trỏ đến địa chỉ của phần tử kế tiếp trong danh sách, hoặc trỏ đến địa chỉ
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
0 nếu như đó là phần tử cuối cùng của danh sách.
Bởi vì mỗi node đều lưu con trỏ tới phần tử tiếp theo trong danh sách, nên chúng ta chỉ cần lưu trữ node đầu tiên là head [cũng là một con trỏ]. Nhờ vào node này chúng ta có thể đi tới lần lượt tất cả các node tiếp theo trong danh sách.
Hình ảnh dưới đây mô phỏng một danh sách liên kết đơn gồm 33 phần tử:
2. Các thao tác của Danh sách liên kết đơn
Trong phần cài đặt, tôi sẽ minh họa các thao tác trên danh sách liên kết với kiểu dữ liệu của từng phần tử là
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
1 cho đơn giản. Các bạn có thể thay thế kiểu dữ liệu của các node trong danh sách theo ý của mình tùy vào tình huống.
2.1. Khai báo
Trước hết, ta khai báo một cấu trúc cho một node trong danh sách liên kết:
struct Node
{
int value;
struct Node* next;
Node[]
{
value = 0;
next = NULL;
}
}
Mỗi node sẽ có trường value\text{value} lưu giá trị và trường next\text{next} là một con trỏ kiểu
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
2 trỏ đến một node tiếp theo trong danh sách liên kết.
Danh sách liên kết đặc biệt ở chỗ, ta không cần phải tạo ra một danh sách thực sự như mảng hay
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
3, mà chỉ cần lưu trữ phần tử đầu tiên của danh sách thôi. Node head\text{head} sẽ là phần tử đầu tiên đó.
2.2. Tạo mới một node
Sử dụng một hàm để tạo ra một node mới lưu trữ giá trị value\text{value}. Mỗi khi một node được tạo ra, ta sẽ cấp phát bộ nhớ động cho nó rồi cho con trỏ next\text{next} của nó mặc định trỏ tới
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
0. Ta sẽ viết hàm này thành một hàm thành viên của cấu trúc NodeNode:
struct Node
{
int value;
struct Node* next;
Node[]
{
value = 0;
next = NULL;
}
void create_node[int _value]
{
value = _value;
next = NULL;
}
};
2.3. Thêm node vào danh sách liên kết
Thêm node vào đầu danh sách liên kết
Để thêm một node vào đầu danh sách, ta cần phải cập nhật lại giá trị head\text{head} của danh sách đó. Với một giá trị value\text{value} mới, để thêm nó vào đầu danh sách ta làm như sau:
- Tạo node mới new_node\text{new\_node} có data=value\text{data} = \text{value}.
- Nếu như head\text{head} đang trỏ tới
Node* add_to_front[int value, Node* head] {
}Node* new_node = create_node[value]; if [head == NULL] head = new_node; else { new_node -> next = head; head = new_node; } return head;0 - nghĩa là danh sách đang rỗng, thì ta đặt luôn node mới là head\text{head}. Ngược lại ta phải thay thế head\text{head} cũ thành node mới, thao tác hai bước:
- Cho next\text{next} của new_node\text{new\_node} trỏ tới head\text{head} ban đầu.
- Đặt head=new_node\text{head} = \text{new\_node}.
- Trả về giá trị head\text{head} mới cho danh sách liên kết.
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
Thao tác này có độ phức tạp là O[1]O[1].
Thêm node vào cuối danh sách liên kết
Chúng ta sẽ cần node đầu tiên head\text{head} và giá trị value\text{value} cần thêm. Khi đó, làm các thao tác sau:
- Tạo node mới new_node\text{new\_node} với data=value\text{data} = \text{value}.
- Nếu head=\text{head} =
Node* add_to_front[int value, Node* head] {
}Node* new_node = create_node[value]; if [head == NULL] head = new_node; else { new_node -> next = head; head = new_node; } return head; - Ngược lại, ta duyệt liên tục từ head\text{head} tới node cuối cùng của danh sách [node có next=\text{next} =
Node* add_to_front[int value, Node* head] {
}Node* new_node = create_node[value]; if [head == NULL] head = new_node; else { new_node -> next = head; head = new_node; } return head; - và đặt next\text{next} của node đó trỏ vào new_node\text{new\_node}.
- Cuối cùng trả về giá trị head\text{head} mới của danh sách liên kết.
Node* add_to_last[int value, Node* head]
{
// Node mới cần thêm vào.
Node* new_node = create_node[value];
// Danh sách rỗng thì gán luôn head bằng node mới.
if [head == NULL]
head = new_node;
else
{
// Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
Node* p = head;
while [p -> next != NULL]
p = p -> next;
// Cho next của phần tử cuối trỏ tới node mới.
p -> next = new_node;
}
return head;
}
Độ phức tạp của thao tác này là O[n]O[n].
Thêm một node vào giữa danh sách liên kết
Thao tác này sẽ phức tạp hơn một chút. Giả sử cần thêm một giá trị mới vào vị trí xx trên danh sách, ta cần làm như sau:
- Duyệt từ đầu danh sách tới node đang nằm ở vị trí x−1x - 1 của danh sách. Giả sử đó là node QQ và coi như vị trí của các node trên danh sách sẽ bắt đầu từ 00.
- Cho trường next\text{next} của node mới trỏ tới node mà QQ đang trỏ tới.
- Cho trường next\text{next} của node QQ trỏ tới node mới.
Các bạn chỉ cần lưu ý trường hợp nếu như x=0x = 0 hoặc danh sách liên kết đang rỗng thì coi như đó chính là thao tác thêm một node vào đầu danh sách. Còn nếu như duyệt hết danh sách mà không thể tìm ra node Q,Q, thì thao tác chèn đó là một thao tác không hợp lệ, hoặc bạn có thể mặc định chèn vào cuối danh sách.
Hình ảnh dưới đây minh họa cho việc chèn một node vào vị trí thứ 22 trong danh sách liên kết:
Node* add_to_position[Node* head, int value, int x]
{
// Danh sách đang rỗng hoặc x = 0 thì coi như là chèn vào đầu danh sách.
if [x == 0 || head == NULL] // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
head = add_to_front[value, head];
else
{
Node* p = head;
int k = 0;
while [p != NULL && k + 1 != x]
{
p = p -> next;
++k;
}
// Không tìm được node ở vị trí x - 1.
if [k + 1 != x]
{
// Thông báo vị trí không hợp lệ
cout next = p -> next;
p -> next = new_node;
}
}
return head;
}
Độ phức tạp của thao tác này là O[n]O[n].
2.4. Xóa node khỏi danh sách liên kết
Xóa vị trí đầu
Rất đơn giản, khi xóa vị trí đầu nghĩa là ta thay đổi phần tử head\text{head} thành phần tử nó đang trỏ đến. Nghĩa là gán head=head→next\text{head} = \text{head} \to \text{next}.
Sau đó trả về giá trị mới của head\text{head}. Lưu ý trường hợp danh sách rỗng thì không có gì để xóa cả.
Node* del_front[Node* head]
{
if [head == NULL]
cout next];
}
Thao tác này có độ phức tạp O[1]O[1].
Xóa vị trí cuối
Đồng nghĩa với việc giảm kích thước của danh sách liên kết đi 11 đơn vị. Ta sẽ tìm phần tử áp chót của danh sách liên kết, sau đó cho phần tử đó trỏ tới
Node* add_to_front[int value, Node* head]
{
Node* new_node = create_node[value];
if [head == NULL]
head = new_node;
else
{
new_node -> next = head;
head = new_node;
}
return head;
}
0. Còn nếu như danh sách đang rỗng hoặc chỉ có 11 phần tử thì ta coi như đó là đang xóa phần tử đầu tiên.
Sau đó ta trả về giá trị mới của head\text{head}.
Node* del_last[Node* head]
{
if [head == NULL || head -> next == NULL]
return del_front[head];
Node* p = head;
while [p -> next -> next != NULL]
p = p -> next;
p -> next = NULL;
return head;
}
Thao tác này có độ phức tạp O[n]O[n].
Xóa node ở vị trí bất kì
Thao tác này cũng khá giống với thao tác xóa node ở vị trí cuối. Nó đơn giản là ta bỏ qua phần tử ở vị trí đó bằng cách cho next\text{next} của phần tử trước nó trỏ tới phần tử sau nó.
Tuy nhiên, cần lưu ý trường hợp vị trí cần xóa không tồn tại trong danh sách, đó là khi duyệt hết danh sách mà vẫn chưa tới được phần tử ở trước phần tử cần xóa.
Hình ảnh dưới đây minh họa thao tác xóa một phần tử trong danh sách liên kết [phần tử tmp\text{tmp}]:
Node* del_at_position[Node* head, int x]
{
if [x == 0 || head == NULL || head -> next == NULL] // Hoặc x == 1 tùy vào cách đánh số trên danh sách.
return del_front[head];
Node* p = head;
int k = 0;
while [p -> next -> next != NULL && k != x - 1]
{
p = p -> next;
++k;
}
// Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước
// vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa.
if [k != x - 1]
cout next = p -> next -> next;
return head;
}
Thao tác này có độ phức tạp O[n]O[n]. Tuy nhiên, nếu ta biết trước con trỏ trỏ tới phần tử cần xóa thì độ phức tạp sẽ chỉ còn là O[1]O[1].
2.5. Lấy giá trị ở vị trí bất kì
Để lấy giá trị ở vị trí xx bất kì trên danh sách liên kết, không có cách nào khác ngoài việc duyệt từ đầu danh sách cho tới khi tìm được phần tử ở vị trí xx. Các thao tác tìm kiếm trên danh sách cũng hoàn toàn tương tự. Có thể thấy, việc tìm kiếm và truy xuất giá trị không phải là một ưu thế của danh sách liên kết.
Dưới đây là code lấy giá trị ở vị trí xx bất kì trên danh sách liên kết. Đối với thao tác tìm kiếm một phần tử value\text{value} trên danh sách, các bạn cũng làm hoàn toàn tương tự. Ngoài ra, các bạn có thể viết thêm đoạn code kiểm tra vị trí cần truy xuất có hợp lệ hay không.
Node* value_at_index[int x]
{
int k = 0; // Hoặc int k = 1 tùy vào cách đánh số trên danh sách.
Node* p = head;
while [p -> next != NULL && k != x]
{
p = p -> next;
++k;
}
return p -> data;
}
Thao tác này có độ phức tạp O[n]O[n].
2.6. Một số thao tác bổ trợ khác
Duyệt danh sách liên kết
Để duyệt và in ra danh sách liên kết, các bạn chỉ cần liên tục gán head=head→next\text{head} = \text{head} \to \text{next} là có thể làm được. Thao tác này có độ phức tạp O[n]O[n].
void print_list[Node* head]
{
for [Node* p = head; p != NULL; p = p -> next]
cout data next = head;
head = new_node;
}
return head;
}
9. Như vậy, các hàm tác động tới con trỏ headhead sẽ có chút thay đổi ở kiểu hàm, các bạn quan sát chương trình mẫu để hiểu rõ hơn.
Dưới đây là chương trình minh họa cài đặt Danh sách liên kết đơn lưu số nguyên:
struct Node
{
int value;
struct Node* next;
Node[]
{
value = 0;
next = NULL;
}
void create_node[int _value]
{
value = _value;
next = NULL;
}
};
2
Các bạn có thể xem thêm cài đặt đầy đủ của Danh sách liên kết đôi tại đây.
III. So sánh giữa mảng và danh sách liên kết
Tổng kết lại, ta có bảng so sánh giữa danh sách liên kết và mảng dưới đây:
Đồng thời độ phức tạp của từng thao tác tôi cũng đã đề cập kĩ ở cài đặt. Tùy vào tình huống mà các bạn có thể lựa chọn sử dụng cấu trúc dữ liệu mảng hay danh sách liên kết cho phù hợp.
Danh sách liên kết đơn vọng là gì?
Danh sách liên kết vòng là một biến thể của danh sách được liên kết trong đó phần tử đầu tiên trỏ đến phần tử cuối cùng và phần tử cuối cùng trỏ đến phần tử đầu tiên. Cả Danh sách liên kết đơn và Danh sách liên kết đôi có thể được tạo thành một danh sách liên kết vòng.nullBài 13 - Danh sách liên kết vòng trong cấu trúc dữ liệu & giải thuậtlotusacademy.edu.vn › blog › bai-13-danh-sach-lien-ket-vong-trong-cau-tr...null
Nhược điểm của danh sách liên kết là gì?
Một nhược điểm của danh sách liên kết là thời gian truy cập là tuyến tính [và khó thực thi ống dẫn]. Truy cập nhanh hơn, ví dụ như truy cập ngẫu nhiên, là không khả thi. Mảng có vùng đệm [cache locality] tốt hơn so với danh sách liên kết.nullDanh sách liên kết – Wikipedia tiếng Việtvi.wikipedia.org › wiki › Danh_sách_liên_kếtnull
Tại sao lại dùng danh sách liên kết?
Ưu điểm chính của danh sách liên kết là bạn có thể thêm bớt phần tử ở bất kỳ vị trí nào với độ phức tạp O[1] . Một lưu ý là bạn cần phải có một tham chiếu đến nút ở vị trí mà bạn muốn thêm/xóa, nếu không thì thao tác sẽ tốn O[n] .nullSự khác biệt giữa danh sách liên kết đơn và mảng - Tek4tek4.vn › khoa-hoc › su-khac-biet-giua-danh-sach-lien-ket-don-va-mangnull
Danh sách liên kết đối là gì?
Danh sách liên kết đôi [Double Linked List] là một tập hợp các Node được phân bố động, mà cấu trúc mỗi Node bao gồm: Dữ liệu [data]. Một con trỏ next sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của danh sách.nullTìm hiểu danh sách liên kết kép-Double Linked List [Cấu trúc ...hanam88.com › kho-tai-lieu › tim-hieu-danh-sach-lien-ket-kep-double-lin...null