Giới thiệu
Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu động phổ biến trong ngôn ngữ lập trình C++. Nó cung cấp một phương pháp linh hoạt để lưu trữ và quản lý dữ liệu. Trong danh sách liên kết đơn, mỗi phần tử được liên kết với phần tử đằng sau nó trong danh sách. Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần:
- Thành phần dữ liệu: lưu trữ thông tin về bản thân phần tử đó.
- Thành phần liên kết: lưu trữ địa chỉ của phần tử đứng sau nó trong danh sách. Nếu phần tử đó là phần tử cuối cùng, thành phần này sẽ bằng NULL.
Danh sách liên kết đơn cung cấp khả năng thay đổi kích thước dễ dàng bằng cách thêm hoặc xóa các phần tử. Đồng thời, nó cũng cho phép lưu trữ các phần tử ngẫu nhiên trong bộ nhớ, không yêu cầu vùng nhớ liên tiếp. Tuy nhiên, việc truy cập tới một phần tử ngẫu nhiên trong danh sách yêu cầu duyệt từ đầu đến vị trí đó. Ngoài ra, chỉ có thể tìm kiếm tuyến tính một phần tử trong danh sách.
Đặc điểm của danh sách liên kết đơn
Danh sách liên kết đơn có một số đặc điểm sau:
- Được cấp phát bộ nhớ khi chạy chương trình.
- Có thể thay đổi kích thước bằng cách thêm hoặc xóa phần tử.
- Kích thước tối đa phụ thuộc vào bộ nhớ khả dụng của RAM.
- Các phần tử được lưu trữ ngẫu nhiên trong RAM.
Do tính chất liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó còn có các đặc điểm sau:
- Chỉ cần nắm được phần tử đầu và cuối là có thể quản lý được danh sách.
- Truy cập tới phần tử ngẫu nhiên phải duyệt từ đầu đến vị trí đó.
- Chỉ có thể tìm kiếm tuyến tính một phần tử.
Cài đặt danh sách liên kết đơn
Trước khi tiến hành cài đặt danh sách liên kết đơn, chúng ta cần nắm vững về con trỏ và cấp phát động trong ngôn ngữ lập trình C++. Đây là những khái niệm quan trọng để hiểu được cách hoạt động của danh sách. Nếu bạn chưa tự tin về kiến thức này, hãy dành thời gian để tìm hiểu thêm trước khi đọc bài viết này.
Tạo node
Danh sách liên kết đơn được tạo thành từ nhiều node, do đó, chúng ta sẽ bắt đầu từ node đầu tiên. Một node bao gồm hai thành phần: thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu có thể là một kiểu dữ liệu có sẵn hoặc bạn tự định nghĩa (struct hoặc class). Trong ví dụ này, để đơn giản, chúng ta sẽ sử dụng kiểu int cho thành phần dữ liệu. Thành phần liên kết sẽ là một con trỏ trỏ đến node tiếp theo.
struct Node {
int data;
Node* next;
};
Node* CreateNode(int init_data) {
Node* node = new Node;
node->data = init_data;
node->next = NULL;
return node;
}Tạo danh sách liên kết đơn
Sau khi có thành phần tạo nên danh sách (node), chúng ta cần quản lý chúng bằng cách biết phần tử đầu và phần tử cuối của danh sách. Vì mỗi phần tử liên kết với phần tử kế tiếp, ta chỉ cần biết phần tử đầu và phần tử cuối để quản lý danh sách này. Để thực hiện điều đó, chúng ta cần tạo một cấu trúc LinkedList lưu trữ địa chỉ của phần tử đầu (head) và phần tử cuối (tail).
struct LinkedList {
Node* head;
Node* tail;
};
void CreateList(LinkedList& l) {
l.head = NULL;
l.tail = NULL;
}Để tạo một danh sách, ta chỉ cần gọi hàm CreateList như sau:
LinkedList list;
CreateList(list); // Gán head và tail bằng NULLThêm phần tử vào danh sách
Thêm vào đầu
Để thêm một node vào đầu danh sách, ta cần kiểm tra xem danh sách có rỗng hay không. Nếu danh sách rỗng, ta chỉ cần gán head và tail của danh sách bằng node đó. Ngược lại, nếu danh sách không rỗng, ta sẽ thực hiện trỏ thành phần liên kết của node vào head, sau đó gán lại head bằng node mới.
void AddHead(LinkedList& l, Node* node) {
if (l.head == NULL) {
l.head = node;
l.tail = node;
} else {
node->next = l.head;
l.head = node;
}
}Thêm vào cuối
Tương tự như thêm vào đầu, để thêm một node vào cuối danh sách, ta cũng cần kiểm tra xem danh sách có rỗng hay không. Nếu danh sách rỗng, ta chỉ cần gán head và tail của danh sách bằng node mới. Ngược lại, nếu danh sách không rỗng, ta sẽ thực hiện trỏ next của tail vào node mới, sau đó gán lại tail bằng node mới.
void AddTail(LinkedList& l, Node* node) {
if (l.head == NULL) {
l.head = node;
l.tail = node;
} else {
l.tail->next = node;
l.tail = node;
}
}Cài đặt thêm vào sau node bất kỳ
Để thêm một node p vào sau node q bất kỳ, ta cần kiểm tra xem node q có NULL hay không. Nếu node q là NULL, tức là danh sách rỗng, ta sẽ thêm node vào đầu danh sách. Nếu node q không NULL, tức là node q tồn tại trong danh sách, ta sẽ thực hiện trỏ next của node p vào next của node q, sau đó gán lại next của node q bằng node p. Tiếp theo, chúng ta sẽ kiểm tra xem node q có phải là node cuối danh sách hay không. Nếu node q là node cuối, ta sẽ gán tail bằng node p.
void InsertAfterQ(LinkedList& l, Node* p, Node* q) {
if (q != NULL) {
p->next = q->next;
q->next = p;
if (l.tail == q) l.tail = p;
} else {
AddHead(l, p);
}
}Xóa phần tử khỏi danh sách
Xóa ở đầu
Để xóa phần tử ở đầu danh sách, ta cần kiểm tra xem danh sách có rỗng hay không. Nếu danh sách rỗng, ta không cần xóa gì cả và trả về kết quả là 0. Ngược lại, nếu danh sách không rỗng, ta sẽ thực hiện lưu giá trị của node đầu vào biến x, sau đó gán head bằng next của node đầu, cuối cùng là xóa node đầu đi. Tiếp theo, ta sẽ kiểm tra xem danh sách sau khi xóa node đầu có rỗng hay không. Nếu rỗng, ta sẽ gán lại tail bằng NULL và trả về kết quả là 1, ngược lại trả về 0.
int RemoveHead(LinkedList& l, int& x) {
if (l.head != NULL) {
Node* node = l.head;
x = node->data; // Lưu giá trị của node đầu lại
l.head = node->next;
delete node; // Hủy node đầu đi
if (l.head == NULL) l.tail = NULL;
return 1;
}
return 0;
}Xóa ở sau node bất kỳ
Để xóa một node p sau node q bất kỳ, ta cần kiểm tra xem node q có NULL hay không. Nếu node q là NULL, tức là node không tồn tại trong danh sách, ta sẽ trả về kết quả 0 và không xóa gì cả. Nếu node q khác NULL nhưng next của q là NULL, tức là p bằng NULL, ta sẽ trả về kết quả 0 (do p không tồn tại hoặc vị trí của p nằm ngoài danh sách). Nếu node p tồn tại, ta sẽ thực hiện kiểm tra xem node p có phải là node cuối danh sách hay không. Nếu p là node cuối, ta sẽ gán tail bằng q để xóa node p.
int RemoveAfterQ(LinkedList& l, Node* q, int& x) {
if (q != NULL) {
Node* p = q->next;
if (p != NULL) {
if (l.tail == p) l.tail = q;
q->next = p->next;
x = p->data;
delete p;
return 1;
}
return 0;
}
return 0;
}Duyệt danh sách và in
Sau khi có các thao tác thêm, xóa, chúng ta có thể in ra danh sách để kiểm tra xem có hoạt động đúng hay không. Để in danh sách, ta chỉ cần duyệt từ đầu đến cuối danh sách và in ra phần tử trong lúc duyệt. Ta sẽ gán một node bằng head, sau đó kiểm tra xem node đó có NULL hay không. Nếu không, ta sẽ in ra giá trị của node đó và gán node bằng next của chính nó để chuyển sang node tiếp theo. Tiếp tục quá trình này cho đến khi node bằng NULL.
void PrintList(LinkedList l) {
if (l.head != NULL) {
Node* node = l.head;
while (node != NULL) {
cout node->data ' ';
node = node->next;
}
}
}Tìm kiếm phần tử trong danh sách
Để tìm kiếm một phần tử trong danh sách, chúng ta cũng thực hiện duyệt qua từng node trong danh sách. Nếu chưa tìm thấy, ta tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ cần kiểm tra xem node cuối cùng có khác NULL hay không để xác định kết quả tìm kiếm.
Node* Search(LinkedList l, int x) {
Node* node = l.head;
while (node != NULL && node->data != x) node = node->next;
if (node != NULL) return node;
return NULL;
}Đếm số phần tử của danh sách
Để đếm số phần tử của danh sách, ta thực hiện duyệt từ đầu đến cuối danh sách và đếm số node.
int Length(LinkedList l) {
int count = 0;
Node* node = l.head;
while (node != NULL) {
count++;
node = node->next;
}
return count;
}Xóa danh sách
Để xóa danh sách, ta cần hủy tất cả các node. Điều này được thực hiện bằng cách duyệt từ đầu đến cuối danh sách và xóa từng node một. Chúng ta có thể sử dụng lại hàm RemoveHead để xóa từng node. Đầu tiên, ta gán một node bằng head, sau đó kiểm tra nếu node khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp tục, cứ lặp như vậy cho đến khi node NULL. Sau khi đã xóa hết tất cả phần tử, ta gán lại tail bằng NULL.
void DestroyList(LinkedList& l) {
int x;
Node* node = l.head;
while (node != NULL) {
RemoveHead(l, x);
node = l.head;
}
l.tail = NULL;
}Tổng kết
Trên đây là một số cách cài đặt và sử dụng cơ bản cho danh sách liên kết đơn trong ngôn ngữ lập trình C++. Đây chỉ là một cách tiếp cận và có nhiều cách thức khác nhau để thực hiện. Quan trọng nhất là nắm vững về con trỏ và cấp phát động trong C++. Nếu bạn thấy bài viết hữu ích, hãy chia sẻ nó với bạn bè của bạn. Cảm ơn bạn đã theo dõi bài viết này!
Nguồn code: GitHub
Emotional writing and user experience guidance in Vietnamese: Danh sách liên kết đơn trong C++: Cấu trúc dữ liệu động và cách sử dụng
Giới thiệu
Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu phổ biến trong ngôn ngữ lập trình C++. Nó cung cấp một phương pháp linh hoạt để lưu trữ và quản lý dữ liệu. Trong danh sách liên kết đơn, mỗi phần tử được liên kết với phần tử đằng sau nó trong danh sách. Mỗi phần tử trong danh sách liên kết đơn bao gồm thông tin về bản thân và địa chỉ của phần tử kế tiếp trong danh sách.
Danh sách liên kết đơn có thể thay đổi kích thước bằng cách thêm hoặc xóa phần tử. Nó cũng cho phép lưu trữ các phần tử ngẫu nhiên trong bộ nhớ. Tuy nhiên, để truy cập tới một phần tử ngẫu nhiên trong danh sách, ta phải duyệt từ đầu đến vị trí đó. Danh sách liên kết đơn chỉ hỗ trợ tìm kiếm tuyến tính một phần tử.
Cài đặt danh sách liên kết đơn
Để cài đặt danh sách liên kết đơn, chúng ta cần biết về cấu trúc node và quản lý phần tử đầu và cuối của danh sách. Mỗi node trong danh sách bao gồm một phần tử dữ liệu và một con trỏ trỏ đến node tiếp theo.
Thêm phần tử vào danh sách
Chúng ta có thể thêm phần tử vào đầu hoặc cuối danh sách. Nếu danh sách rỗng, ta chỉ cần gán phần tử đó cho cả phần tử đầu và cuối. Nếu danh sách không rỗng, ta sẽ thay đổi con trỏ đầu hoặc cuối để thêm phần tử mới.
Xóa phần tử khỏi danh sách
Chúng ta có thể xóa phần tử từ đầu hoặc sau một phần tử bất kỳ trong danh sách. Để xóa phần tử từ đầu, ta chỉ cần thay đổi con trỏ đầu và xóa phần tử. Để xóa phần tử sau một phần tử bất kỳ, ta sẽ tìm phần tử đó và thay đổi con trỏ để bỏ qua phần tử cần xóa.
Duyệt danh sách và in
Để duyệt danh sách, ta sẽ duyệt qua từng phần tử và in giá trị của chúng. Điều này giúp kiểm tra xem danh sách đã hoạt động đúng hay không.
Tìm kiếm phần tử trong danh sách
Chúng ta có thể tìm kiếm một phần tử trong danh sách bằng cách duyệt qua từng phần tử và so sánh giá trị. Nếu tìm thấy phần tử, ta sẽ trả về phần tử đó. Nếu không tìm thấy, ta sẽ trả về NULL.
Đếm số phần tử của danh sách
Để đếm số phần tử trong danh sách, ta duyệt qua từng phần tử và tăng biến đếm. Cuối cùng, ta trả về giá trị của biến đếm.
Tổng kết
Danh sách liên kết đơn là một cấu trúc dữ liệu linh hoạt và hữu ích trong ngôn ngữ lập trình C++. Bằng cách sử dụng các phép toán cơ bản và quản lý con trỏ, ta có thể thêm, xóa, duyệt và tìm kiếm phần tử trong danh sách.