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

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

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.