🌱 Cấu trúc dữ liệu - Linked List

    🔻 Đặt vấn đề

    Một bài toán đơn giản và thường gặp đó là quản lý một tập hợp các thiết bị trong kho của cửa hàng, sử dụng ngôn ngữ lập trình C (Quản lý học viên, vào ra folder, ...).

    Với các bài toán này, chúng ta có thể nghĩ đến mảng đầu tiên. Tạo một mảng Devive[100], rồi triển khai các hàm thêm/xóa/... Tuy nhiên, dễ thấy với bài toán thực tế thì việc này sẽ hơi khó triển khai với 2 vấn đề:

• Nếu user chỉ dùng có chưa đến 10 thiết bị ⟹ Số lượng bộ nhớ đã cấp phát bị lãng phí.
• Nếu user cần dùng nhiều hơn 100 phần tử ⟹ Bài toán không đáp ứng được.

    Đối với một số bài toán cần quản lý một số lượng lớn dữ liệu, mà không biết trước số phần tử như vậy, chúng ta cần một Cấu trúc dữ liệu mang tính Dynamic nhiều hơn, có thể thay đổi số lượng phần tử trong Runtime. Bài viết này sẽ giới thiệu và bàn luận về kiểu cấu trúc dữ liệu Linked List.

    👉 Giới thiệu về Linked List

    Linked List là một linear data structure, các phần tử của list sẽ không sắp xếp liên tiếp nhau giống như array, thay vào đó nó sử dụng phương thức phần tử trước lưu trữ thông tin của phần tử sau (thường gặp nhất là lưu trữ địa chỉ, sử dụng pointer).

• Một phần tử của mỗi Linked List gọi là một "Node", nó bao gồm "Data" của phần tử và "pNext" chứa thông tin (địa chỉ) của phần tử tiếp theo.
• Thông tin địa chỉ của phần tử đầu tiên trong List sẽ được lưu trữ bởi HEAD pointer,
• Phần tử cuối cùng trong List không chứa bất kỳ địa chỉ nào nên "pNext" = NULL.

    🔻 Một số kiểu Linked List

• Single Linked List
• Double Linked List
• Circular Linked List

    👉 Triển khai Linked List trong C

    Vẫn với cách tiếp cận quen thuộc khi triển khai các Data Structure, với Linked List, chúng ta cũng chia ra làm 2 phase:

• Organize Data - Tổ chức Data (Cho các Node)
• Operations - Triển khai các thao tác với Linked List (Thêm / Xóa / Tìm kiếm Node)

    💬 Organize Data - Tổ chức Data

    Khi triển khai một Linked List bằng ngôn ngữ lập trình C, chúng ta sẽ cần một thành phần lưu data (có thể là uint32 với số nguyên, hoặc struct, ... tùy bài toán), và thành phần thứ 2 là một pointer, chứa địa chỉ của phần tử tiếp theo.

    Ví dụ.

typedef struct Node_t 
{
    uint32_t Data;
    Node_t * pNext; 
} NodeType;

    💬 Linked List Operations

    > Khởi tạo Linked List

    Dễ thấy ban đầu khi khởi tạo, Linked List không có Node nào, nó chỉ bao gồm một con trỏ HEAD = NULL.

NodeType * HEAD = NULL;

    > Thêm Node vào Linked List

    Việc thêm một Node vào List có thể thực hiện bằng cách thêm vào đầu, thêm vào cuối, hoặc chèn vào giữa List.

    Ở đây mình ví dụ việc thêm một Node vào đầu List, chúng ta cần:

1. Cấp phát bộ nhớ cho Node mới
2. Assign Data cho Node mới
3. pNext của Node mới sẽ chứa địa chỉ của Node đầu tiên cũ
4. HEAD sẽ chứa địa chỉ của Node mới

    >>> Code ví dụ,

void List_AddNode(uint32_t Data)
{
    /* 1. Allocate new node memory */
    NodeType * pnewNode = (NodeType*)malloc(sizeof(NodeType));
    /* 2. Assign new Data */
    pnewNode->Data = Data;
    /* 3. New Node will contain address of Old First Node */
    pnewNode->pNext = HEAD;
    /* 4. HEAD will contain address of the New Node */
    HEAD = pnewNode;
}

    Run This Code    

 

Chú ý, dễ thấy bước 3 và 4 không thể đổi vị trí cho nhau, vì nếu bước 4 làm trước, thì HEAD sẽ trỏ đến newNode, từ đó chúng ta sẽ mất thông tin của first node cũ, đó là hiện tượng Memory Leak. 

    > Xóa Node khỏi Linked List

    Việc xóa Node khỏi Linked List cũng có thể thực hiện theo nhiều cách: xóa node đầu tiên, xóa node cuối cùng, hoặc xóa node bất kỳ theo data, theo index, ... tùy vào mục đích sử dụng.

    Ở đây mình ví dụ việc xoá một node theo index, phức tạp hơn một chút so với việc thêm, khi xóa node, ngoài việc loại bỏ node cần xóa, chúng ta còn phải free node đó để tránh lãng phí bộ nhớ, cụ thể cần:

1. Chúng ta sẽ cần một pointer tạm (pTemp) để chứa địa chỉ của Node cần xóa (Node B)(Mục đích là sau khi xóa xong Node đó khỏi List thì cần thông tin địa chỉ để free nó đi)
   Vì vậy việc đầu tiên là tìm đến Node cần xóa, đưa pointer tạm này trỏ vào Node đó (pTemp = &NodeB).
2. Cần một pointer trỏ vào Node trước Node cần xóa (pPrev = &NodeA), mục tiêu để thay đổi pNext của Node trước này, trỏ đến địa chỉ của Node sau đó
   NodeA➔pNext = NodeB➔pNext = &NodeC
   hay: pPrev➔pNext = pTemp➔pNext
3. free vùng nhớ của Node cần xóa.

    >>> Code ví dụ,

void List_DeleteNode(uint32_t NodeIdx)
{
    /* Allocate new node memory */
    NodeType * pPrev = HEAD;
    NodeType * pTemp = HEAD;
    uint32_t idx;
    
    /* Find the NodeIdx to assign pPrev & pTemp */
    for (idx = 0U; idx < NodeIdx; idx++)
    {
        /* Check if List has one Node only */
        if (0U == idx && 1U == NodeIdx) 
        {
            HEAD = HEAD->pNext;
            break;
        }
        else
        {
            if (idx == NodeIdx - 1U && pTemp) 
            {
                /* NodeA➔pNext = NodeB➔pNext = &NodeC */
                pPrev->pNext = pTemp->pNext;
                break;
            }
            else 
            {
                pPrev = pTemp;
                /* Position was greater than number of nodes in the list */
                if (pPrev == NULL)
                    break;
                pTemp = pTemp->pNext;
            }
        }
    }
    
    /* Free Memory of Deleted Node */
    free(pTemp);
}

    Run This Code    

    > Tìm kiếm một Node trong Linked List

    Việc tìm kiếm Node thì có nhiều hướng, tùy thuộc vào yêu cầu bài toán cũng như phương pháp tìm kiếm. Ví dụ tìm kiếm theo giá trị data trong Node (giá trị là duy nhất hoặc không duy nhất), hoặc tìm kiếm theo một thành phần của Data (với Data dạng Struct, ví dụ StudentID trong struct Student).

    Các tìm kiếm đơn giản nhất là sử dụng một vòng lặp và check từng phần tử trong List. Chi tiết về các kiểu Searching sẽ được đề cập trong một bài viết sau này!

>>>= Follow ngay =<<<

Để nhận được những bài học miễn phí mới nhất nhé 😊

Chúc các bạn học tập tốt 😊