Singly linked list là gì?

Danh sách liên kết đơn (singly linked list) là loại danh sách liên kết (linked list) đơn giản nhất trong đó mỗi nút (node) chứa một số dữ liệu và một con trỏ (pointer) trỏ đến đến nút tiếp theo của cùng một kiểu dữ liệu (data type). Nút chứa một con trỏ trỏ đến nút tiếp theo có nghĩa là nút đó lưu trữ địa chỉ (address) của nút tiếp theo trong chuỗi. Danh sách liên kết đơn (singly linked list) cho phép duyệt (traverse) chỉ theo một hướng từ nút đầu (head) đến nút cuối cùng (tail).

Nút đầu tiên được gọi là head, nó trỏ đến nút đầu tiên của danh sách và giúp chúng ttaôi truy cập vào mọi phần tử khác trong danh sách. Nút cuối cùng đôi khi còn được gọi là tail trỏ đến NULL giúp chúng ta xác định khi nào danh sách kết thúc.

Một số thao tác trong danh sách liên kết đơn (singly linked list) như:

• Tìm kiếm một nút trong danh sách: Bạn có thể xác định và truy xuất một nút cụ thể từ phía đầu, phía cuối danh sách hoặc bất kỳ nơi nào trong danh sách. Trường hợp xấu nhất độ phức tạp thời gian (time complexity) để truy xuất một nút từ bất kỳ đâu trong danh sách là O(n).
• Thêm một nút vào danh sách: Bạn có thể thêm một nút ở đầu, cuối hoặc bất kỳ đâu trong danh sách. Trường hợp xấu nhất độ phức tạp về thời gian của thêm nút vào đầu danh sách là O(1), thêm nút vào cuối danh sách là O(n) và thêm nút vào bất kỳ vị trí nào trong danh sách là O(n).
• Xóa một nút khỏi danh sách: Bạn có thể xóa một nút từ phía đầu, phía cuối hoặc từ bất kỳ vị trí nào trong danh sách. Trong trường hợp xấu nhất độ phức tạp về thời gian của xóa nút khỏi đầu danh sách là O(1), xóa nút khỏi cuối danh sách là O(n), xóa nút khỏi bất kỳ vị trí nào trong danh sách là O (n).

Bên dưới là code tạo và duyệt danh sách liên kết đơn (singly linked list) trong C++:

// C++ program to illustrate creation
// and traversal of Singly Linked List
 
#include 
using namespace std;
 
// Structure of Node
class Node {
public:
    int data;
    Node* next;
};
 
// Function to print the content of
// linked list starting from the
// given node
void printList(Node* n)
{
 
    // Iterate till n reaches NULL
    while (n != NULL) {
 
        // Print the data
        cout data next;
    }
}
 
// Driver Code
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
 
    // Allocate 3 nodes in the heap
    head = new Node();
    second = new Node();
    third = new Node();
 
    // Assign data in first node
    head->data = 1;
 
    // Link first node with second
    head->next = second;
 
    // Assign data to second node
    second->data = 2;
    second->next = third;
 
    // Assign data to third node
    third->data = 3;
    third->next = NULL;
 
    printList(head);
 
    return 0;
}

Output:

1 2 3