Danh sách liên kết đơn – Khám phá thông tin chi tiết nhất

Danh sách liên kết đơn là khái niệm quan trọng trong lập trình và mang lại nhiều ứng dụng vô cùng lớn. Nếu bạn muốn tìm hiểu về lĩnh vực này, không thể bỏ qua kiến thức về danh sách liên kết đơn. Trong bài viết này, chúng ta sẽ tìm hiểu thêm về định nghĩa, đặc điểm và cách cài đặt danh sách liên kết đơn.

Tìm hiểu về danh sách liên kết

Trước khi khám phá danh sách liên kết đơn, hãy cùng điểm qua danh sách liên kết trước. Để dễ hiểu, bạn có thể tưởng tượng danh sách liên kết trong ngôn ngữ C có chức năng tương tự như một mảng. Tuy nhiên, danh sách liên kết vẫn có một số điểm khác biệt đáng chú ý. Đây là một số khác biệt giữa danh sách liên kết và mảng:

Mảng

• Kích thước được cố định mọi lúc
• Cần chỉ rõ kích thước khi khai báo

Danh sách liên kết

• Kích thước thay đổi liên tục trong quá trình thêm, bớt phần tử
• Kích thước tối đa chỉ phụ thuộc vào bộ nhớ

Mảng

• Cấp phát bộ nhớ tĩnh: Bộ nhớ được cấp theo chế độ trong quá trình biên dịch

Danh sách liên kết

• Cấp phát bộ nhớ động: Bộ nhớ được cấp theo chế độ trong quá trình khởi chạy

Mảng

• Thứ tự và cách sắp xếp: Được lưu lại trên một dãy các ô nhớ liền kề

Danh sách liên kết

• Thứ tự và cách sắp xếp: Được lưu lại trên các ô nhớ bất kỳ

Mảng

• Truy cập: Bằng cách sử dụng chỉ số mảng, cho phép truy cập đến một phần tử ngẫu nhiên: O(1)

Danh sách liên kết

• Truy cập: Muốn truy cập đến phần tử ngẫu nhiên cần phải trải qua quá trình duyệt từ đầu đến cuối phần tử đó: O(n)

Mảng

• Tìm kiếm: Có thể tìm kiếm bằng 2 ngôn ngữ tuyến tính và nhị phân

Danh sách liên kết

• Tìm kiếm: Chỉ có thể tìm kiếm bằng tuyến tính

Danh sách liên kết đơn (Single linked list) là một trong 3 dạng danh sách liên kết trong ngôn ngữ lập trình C++.

Danh sách liên kết đơn là gì?

Danh sách liên kết đơn (Single Linked List), hay còn được gọi là Single Linked List, được sử dụng để biểu diễn một cấu trúc dữ liệu di động, trong đó mỗi phần tử liên kết với phần tử đứng sau nó.

Single Linked List được sử dụng phổ biến trong ngôn ngữ lập trình C++. Trong danh sách liên kết C++, mỗi phần tử được cấu tạo từ hai thành phần chính: thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu chịu trách nhiệm lưu trữ thông tin về phần tử đó, và thành phần liên kết giúp lưu địa chỉ của phần tử tiếp theo trong danh sách. Nếu phần tử xét đang đứng cuối danh sách, thành phần liên kết sẽ được gán bằng NULL. Một phần tử hoàn chỉnh được cấu thành từ data (dữ liệu) và pointer (liên kết) được gọi là một node (hay còn được gọi là nút).

Mời bạn tham khảo thêm: Sử dụng MongoDB như thế nào? Ưu nhược điểm khi sử dụng

Đặc điểm của danh sách liên kết đơn

Tính cấp phát dữ liệu động

Trong quá trình chạy chương trình, danh sách liên kết đơn C++ sẽ được cấp phát bộ nhớ động. Các phần tử được lưu trữ một cách ngẫu nhiên trong RAM. Khi thêm hoặc xóa phần tử, kích thước của danh sách cũng sẽ thay đổi. Kích thước tối đa của Single linked list trong C++ phụ thuộc vào bộ nhớ khả dụng của RAM.

Tính liên kết của phần tử đầu và phần tử tiếp theo

Vì có sự liên kết giữa các phần tử, chỉ cần biết thông tin của phần tử đầu và phần tử cuối, người dùng có thể dễ dàng quản lý toàn bộ danh sách. Tuy nhiên, nếu muốn truy cập đến một vị trí bất kỳ, người dùng phải thực hiện quá trình duyệt từ đầu đến phần tử đó. Ngoài ra, trong danh sách liên kết đơn C++, chỉ cho phép tìm kiếm tuyến tính duy nhất cho 1 phần tử.

Cách cài đặt danh sách liên kết đơn

Tạo node

Một danh sách được tạo lên từ nhiều node. Do đó, chúng ta sẽ bắt đầu bằng việc tạo node. Một node bao gồm 2 thành phần chính: thành phần liên kết và thành phần dữ liệu. Thành phần dữ liệu có thể tự tạo hoặc sử dụng dữ liệu có sẵn như struct. Thành phần liên kết sẽ là con trỏ, trỏ từ node hiện tại đến node tiếp theo.

Ví dụ về khai báo node:

struct Node
{
    int data;
    Node* next;
};

Để tạo một node mới, chúng ta sẽ khởi tạo giá trị ban đầu và trả về địa chỉ của node được cấp phát.

Node* CreateNode(int init_data)
{
    Node* node = new Node;
    node->data = init_data;
    node->next = NULL;

    return node;
}

Code danh sách liên kết đơn C++

Khi đã có những node, chúng ta sẽ tiến hành tạo danh sách. Vì node liên kết với nhau, chúng ta chỉ cần biết thông tin về node đầu (head) và node cuối (tail) để quản lý danh sách.

struct LinkedList
{
    Node* head;
    Node* tail;
};

Khi tạo danh sách mới, cả head và tail đều chưa có phần tử. Vì vậy, chúng ta sẽ gán head và tail thành NULL.

void CreateList(LinkedList& l)
{
    l.head = NULL;
    l.tail = NULL;
}

Thêm phần tử vào danh sách liên kết đơn

Thêm phần tử vào đầu danh sách

Đầu tiên, chúng ta cần kiểm tra danh sách có rỗng hay không. Nếu rỗng, chúng ta chỉ cần gán head cho node cần thêm. Nếu không rỗng, chúng ta sẽ trỏ liên kết từ head vào node mới và sau đó gán lại head cho node này.

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 phần tử vào cuối danh sách

Tương tự như việc thêm phần tử vào đầu danh sách, chúng ta sẽ kiểm tra danh sách có rỗng hay không. Nếu rỗng, chúng ta chỉ cần gán tail cho node cần thêm. Nếu không rỗng, chúng ta sẽ trỏ liên kết từ tail tới node mới và sau đó gán lại tail cho node mới này.

void AddTail(LinkedList& l, Node* node)
{
    if (l.head == NULL)
    {
        l.head = node;
        l.tail = node;
    }
    else
    {
        l.tail->next = node;
        l.tail = node;
    }
}

Thêm vào điểm bất kỳ

Gọi p là node cần thêm, q là node đứng trước vị trí cần thêm. Đầu tiên, chúng ta sẽ kiểm tra xem q có NULL hay không. Nếu q NULL, có nghĩa là danh sách rỗng, không cần xóa mà chỉ cần đặt giá trị thành 0. Nếu không, chúng ta sẽ thực hiện các bước sau: trỏ p->next = q->next, sau đó q->next = p.

void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
    if (q != NULL)
    {
        p->next = q->next;
        q->next = p;
    }
}

Xóa phần tử khỏi danh sách liên kết đơn

Xóa ở đầu danh sách

Đầu tiên, chúng ta kiểm tra danh sách có rỗng không. Nếu không rỗng, chúng ta sẽ gán head cho node sau phần tử cần xóa, sau đó xóa node đầu và giữ lại giá trị trong x. Nếu head NULL, gán tail thành NULL.

int RemoveHead(LinkedList& l, int& x)
{
    if (l.head != NULL)
    {
        Node* node = l.head;
        x = node->data;
        l.head = node->next;
        delete node;

        if (l.head == NULL)
            l.tail = NULL;

        return 1;
    }

    return 0;
}

Xóa ở điểm bất kỳ

Nếu cần xóa node p sau node q trong danh sách, chúng ta có 3 trường hợp cần xem xét:

• Nếu q là NULL, có nghĩa là danh sách rỗng, không cần xóa mà chỉ cần trả về 0.
• Nếu next của q NULL, có nghĩa là p NULL, không tồn tại để xóa.
• Nếu p tồn tại, kiểm tra xem p có phải tail hay không. Nếu phải, chỉ cần gán tail thành q.

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 liên kết đơn và in

Để kiểm tra xem danh sách đã hoàn chỉnh hay chưa, chúng ta gán một node bằng head. Sau đó, kiểm tra xem node đó có NULL không. Nếu không NULL có nghĩa là chúng ta đã có dữ liệu của node này. Tiếp tục thực hiện thao tác đó cho đến khi node NULL, đó chính là tail của danh sách.

Mời bạn đọc tham khảo thêm: Lập trình web là làm gì? Những công việc của một lập trình viên

Với bài viết trên, chúng ta đã cùng tìm hiểu về các đặc điểm của danh sách liên kết đơn cũng như cách tạo danh sách hoàn chỉnh. Hy vọng những kiến thức này sẽ hữu ích cho việc học tập và làm việc của bạn.

TEKY là Học viện sáng tạo công nghệ đầu tiên tại Việt Nam dành cho trẻ em từ 4 đến 18 tuổi, áp dụng chương trình STEAM (Science - Technology - Engineering - Art - Mathematics) theo chuẩn Mỹ.

Được thành lập vào tháng 6 năm 2016, TEKY tập trung mang đến cho thế hệ trẻ Việt Nam kiến thức toàn diện về STEAM, đặc biệt là các tư duy công nghệ, khoa học máy tính và kỹ năng thế kỷ 21 - 4Cs (Critical Thinking - Tư duy phản biện, Communication - Giao tiếp, Creativity - Sáng tạo, Collaboration - Làm việc nhóm).

Đây là chương trình không chỉ trang bị kiến thức lập trình mà còn rèn luyện các kỹ năng nhóm 4Cs cho trẻ:

• Học tư duy phản biện thông qua việc phân tích các vấn đề.
• Học tính sáng tạo và tư duy logic thông qua việc lắp đặt và lập trình robot sử dụng mô hình Lego Mindstorm, app trò chơi.
• Phát triển kỹ năng hợp tác thông qua các trò chơi team-building và các dự án nhóm trên lớp.
• Phát triển khả năng giao tiếp hiệu quả thông qua các bài tập và hoạt động hấp dẫn.

TEKY cung cấp nhiều khóa học, bao gồm lập trình và phát triển ứng dụng, lập trình game, lập trình web với Python, lập trình Scratch, Robotics Engineering, Công nghệ 3D và Multimedia.

Liên hệ học viện công nghệ sáng tạo TEKY để được tư vấn khóa học:

• Hotline Hà Nội: 024-7109-6668 / 0975-241-015
• Hotline Hồ Chí Minh: 028-7109-9948 / 097-900-8642

Website: https://teky.edu.vn Email: [email protected]