Lập trình C++
4888
24/11/2023
Tìm hiểu về danh sách liên kết đơn trong C++
Danh sách liên kết đơn trong C++ là một trong những khái niệm về cấu trúc dữ liệu đơn giản và hay gặp nhất. Hãy cùng ICANTECH tìm hiểu thêm về danh sách liên kết đơn C++ thông qua bài viết này.
1. Thế nào là danh sách liên kết đơn?
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 << data << " Inserted" << endl;
}
Sử dụng struct (cấu trúc):
void insertStart(Node** head, int data)
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = *head;
*head = newNode;
cout << "\n" << newNode->data << " Inserted" << endl;
}
4.2. Xóa node
Sử dụng class:
void deleteStart()
{
if (head == nullptr)
{
cout << "Linked List Empty, nothing to delete" << endl;
return;
}
Node* temp = head;
head = head->next;
cout << temp->data << " deleted" << endl;
delete temp;
}
Sử dụng struct:
void deleteStart(Node** head)
{
Node* temp = *head;
if (*head == nullptr)
{
cout << "Linked List Empty, nothing to delete" << endl;
return;
}
*head = (*head)->next;
cout << "\n" << temp->data << " deleted" << endl;
delete temp;
}
4.3. Truyền tải trong danh sách liên kết đơn
Sử dụng class:
void display()
{
cout << "Linked List: ";
Node* current = head;
while (current != nullptr)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
Sử dụng struct:
void display(Node* node)
{
cout << "\nLinked List: ";
while (node != nullptr)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
4.4. Code thực hiện danh sách liên kết đơn C++
Sử dụng class:
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList
{
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
void insertStart(int data)
{
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
cout << data << " Inserted" << endl;
}
void deleteStart()
{
if (head == nullptr)
{
cout << "Linked List Empty, nothing to delete" << endl;
return;
}
Node* temp = head;
head = head->next;
cout << temp->data << " deleted" << endl;
delete temp;
}
void display()
{
cout << "Linked List: ";
Node* current = head;
while (current != nullptr)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main()
{
LinkedList list;
list.insertStart(100);
list.insertStart(80);
list.insertStart(60);
list.insertStart(40);
list.insertStart(20);
list.display();
list.deleteStart();
list.deleteStart();
list.display();
return 0;
}
Sử dụng struct:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
void insertStart(Node** head, int data)
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = *head;
*head = newNode;
cout << "\n" << newNode->data << " Inserted" << endl;
}
void deleteStart(Node** head)
{
Node* temp = *head;
if (*head == nullptr)
{
cout << "Linked List Empty, nothing to delete" << endl;
return;
}
*head = (*head)->next;
cout << "\n" << temp->data << " deleted" << endl;
delete temp;
}
void display(Node* node)
{
cout << "\nLinked List: ";
while (node != nullptr)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main()
{
Node* head = nullptr;
insertStart(&head, 100);
insertStart(&head, 80);
insertStart(&head, 60);
insertStart(&head, 40);
insertStart(&head, 20);
display(head);
deleteStart(&head);
deleteStart(&head);
display(head);
return 0;
}
Output:
100 Inserted
80 Inserted
60 Inserted
40 Inserted
20 Inserted
Linked List: 20 40 60 80 100
20 deleted
40 deleted
Linked List: 60 80 100
5. Ứng dụng thực tế
Dưới đây là một số ứng dụng thực tế của liên kết đơn:
- Được sử dụng để lưu trữ các đa thức đơn hoặc đa thức hai biến
- Làm cơ sở cho một số cấu trúc dữ liệu nhất định như Queue, Stack, Graph
- Xây dựng chiến lược cho các sơ đồ phân bổ tệp theo Hệ điều hành (Operating System)
- Theo dõi dung lượng trống trên đĩa phụ, giúp tất cả các không gian trống có thể liên kết được với nhau
- Để lưu giữ các bản ghi âm nhạc, video, hình ảnh, trang web… giúp chúng liên kết với nhau và cho phép bạn di chuyển các bản ghi theo tuần tự.
- Sử dụng danh sách liên kết vòng tròn để quyết định người chơi với trong cách trò chơi theo lượt.
6. Lời Kết
Vậy là qua bài viết trên, chúng ta đã cùng khám phá toàn bộ thông tin cần thiết về danh sách liên kết đơn. ICANTECH hi vọng bạn đã có thêm kiến thức cũng như biết cách tạo 1 danh sách liên kết đơn.
Cảm ơn bạn đã đọc bài viết, nếu bạn đang quan tâm đến học lập trình thì hãy tham khảo ngay các khóa học lập trình dưới đây tại ICANTECH nhé
Nguồn ảnh: ICANTECH.
Tags
Lập trình C++
