Danh sách liên kết đơn [tên tiếng Anh là Singly Linked List] thuộc loại danh sách liên kết đơn hướng, tức là nó được duyệt theo một hướng từ đầu đến cuối. Mỗi phần tử trong danh sách liên kết được gọi là một nút [node], trong đó mỗi nút đều được liên kết với nút đứng sau. Các nút được kết nối với nhau bằng con trỏ, phần đầu là con trỏ sẽ trỏ tới nút đầu tiên của danh sách, giúp bạn duyệt danh sách. Nút cuối cùng trỏ tới null, giúp bạn xác định được danh sách kết thúc khi nào.
Các thành phần của Singly Linked List gồm có:
- Data [dữ liệu]: giá trị được lưu giữ
- Next Pointer [con trỏ tiếp theo]: chứa địa chỉ của nút tiếp theo ở trong chuỗi.
2. Cấu trúc của Singly Linked List
Để giúp bạn có được cái nhìn trực quan, chúng ta hãy cùng làm ví dụ tạo 1 danh sách liên kết đơn để lưu trữ dữ liệu kiểu số nguyên trong đó. Ta sẽ có đoạn code như sau:
Sử dụng class [lớp]
class node
{
int data;
node *next;
};
Sử dụng struct [cấu trúc]
struct Node
{
int data;
struct Node *next;
};
Đoạn code trên sẽ tạo một kiểu dữ liệu node, có thể lưu trữ hai giá trị:
- Giá trị int: dữ liệu
- Giá trị con trỏ: địa chỉ của node tiếp theo
3. Tại sao cần sử dụng danh sách liên kết đơn?
Việc sử dụng danh sách liên kết có rất nhiều lợi ích, có thể kể ra như:
- Giúp cho việc thao tác trên danh sách dễ dàng hơn: danh sách liên kết đơn cho phép bạn thực hiện các thao tác như chèn, xóa một cách hiệu quả và linh hoạt hơn.
- Việc phân bổ bộ nhớ được tối ưu và hiệu quả hơn: bạn sẽ không cần phân bổ trước bộ nhớ cho danh sách liên kết đơn. Bộ nhớ động sẽ được phân bổ trong danh sách liên kết, giúp bạn tiết kiệm dung lượng bộ nhớ.
- Triển khai cấu trúc dữ liệu nâng cao: có rất nhiều cấu trúc dữ liệu nâng cao được phát triển hiệu quả với singly linked list.
4. Các thao tác trên danh sách liên kết đơn trong C
Các thao tác bạn có thể thực hiện để cài đặt danh sách liên kết đơn có thể kể đến như: xóa, chèn, sắp xếp chèn vào danh sách, đảo ngược danh sách, xóa các nút thay thế trong danh sách liên kết, kiểm tra danh sách liên kết… Sau đây, chúng ta sẽ cùng nhau tìm hiểu 1 số thao tác phổ biến trên danh sách liên kết C++ thông qua các ví dụ cụ thể.
4.1. Chèn node
Chúng ta có ví dụ cách chèn 1 nút trên danh sách liên kết đơn C++ như sau:
Sử dụng class [lớp]:
void insertStart[int data]
{
Node* newNode = new Node[data];
newNode->next = head;
head = newNode;
cout