Linked List

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về Linked List, một trong những cấu trúc dữ liệu được ứng dụng phổ biến nhất trong thực tế. Hãy cùng nhau đi tìm hiểu sao nó lại được sử dụng nhiều vậy nhé!

---

Nội dung

Để có thể tiếp thu bài học một cách tốt nhất, các bạn nên có những kiến thức cơ bản về các phần:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học   

Trong bài học này, chúng ta sẽ cùng nhau tìm hiểu về:

• Khái niệm Linked List
• Cơ chế hoạt động của Linked List
• So sánh Linked List và mảng

---

Bài toán đặt ra

Chúng ta có một dãy số gồm n phần tử. Hãy tìm cách chèn vào vị trí i một giá trị mà không làm thay đổi vị trí tương đối của các phần tử trong dãy.

Ví dụ: Ta có dãy [1, 4, 6, 2, 3, 5]. Sau khi chèn phần tử 7 vào vị trí thứ 3 ta sẽ được dãy [1, 4, 7, 6, 2, 3, 5].

---

Lời giải ban đầu

Thông thường, khi ta lưu trữ một dãy dưới dạng mảng mà chèn trực tiếp phần tử vào sẽ làm mất giá trị gốc ở vị trí đó. Do đó, ta nghĩ đến việc sẽ phải tạo ra một ô trống ở vị trí cần chèn. Từ đó, ta sẽ có ý tưởng sau: Dồn các phần tử bắt đầu từ vị trí cần chèn đến cuối cùng về ô sau nó, khi đó, vị trí cần chèn sẽ trống.

Khi triển khai dưới mô hình code ta sẽ có: Nếu như muốn chèn thêm phần tử ở vị trí k trong mảng, ta sẽ gán a_n+1 = a_n, a_n = a_n-1, …, a_k+1 = a_k.

Lúc này, đoạn a_n+1, a_n, a_n-1, …, a_k+1 chính là đoạn an, a_n-1, a_n-2, …, a_k trong mảng ban đầu, ta chỉ cần gán a_k bằng giá trị cần chèn là coi như đã chèn được một phần tử mới vào dãy.

Tuy nhiên, cách trên sẽ mất độ phức tạp O(n) do ta cần duyệt dãy để thực hiện phép gán và do kích thước mảng là cố định nên số phần tử chèn được là có giới hạn. Liệu có cách nào tối ưu hơn không?

---

Nhận xét

Ta thấy trong dãy trên, khi chèn phần tử mới vào vị trí k, chỉ có quan hệ trước sau giữa phần tử a_k-1, a_k và phần tử được chèn thêm là có sự thay đổi. Do đó, ta sẽ nghĩ cách làm sao chỉ thay đổi quan hệ của 3 phần tử này mà không làm ảnh hưởng đến các phần tử khác.

---

Cách giải cải tiến

Bây giờ, hãy cùng nhìn vào một ví dụ trong thực tế. Chúng ta có một hàng ngang gồm n người nắm tay nhau. Bây giờ, chúng ta muốn có thêm một người C vào vị trí giữa hai người A và B. Vậy thì chúng ta sẽ làm thế nào? Có phải là chúng ta sẽ bảo 2 người A và B không nắm tay nhau nữa, tay khi nãy nắm lấy người B của người A thì nắm lấy tay người C, tay khi nãy nắm lấy người A của người B thì nắm lấy tay người C. Lúc này, người C sẽ trở thành một phần của hàng.

Ví dụ minh hoạ trên chính là ý tưởng cơ sở của Linked List. Bây giờ, để hiểu rõ hơn, chúng ta sẽ đi tìm hiểu chi tiết về Linked List.

---

Khái niệm Linked List

Linked List (tiếng Việt: danh sách liên kết) là một tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử chỉ đến phần tử tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện một dãy.

Định nghĩa trên là tương đối phức tạp và khó hiểu nên các bạn cũng không cần quá quan tâm để làm gì. Điều ta chú trọng là Linked List sẽ làm được gì.

Một Linked List sẽ có các phương thức cơ bản sau:

• Chèn một phần tử vào vị trí xác định
• Xoá một phần tử ở vị trí xác định

Trên thực tế, có rất nhiều kiểu Linked List như Single Linked List (Danh sách liên kết đơn), Double Linked List (Danh sách liên kết đôi), Circular Linked List (Danh sách liên kết vòng tròn) nhưng về cơ bản cách hoạt động của chúng là hoàn toàn giống nhau. Trong bài học này, mình sẽ giới thiệu về Double Linked List.

Bài học này, mình sẽ đi chi tiết vào cách thức hoạt động của Linked List. Có 3 lí do cho việc này:

• Đa phần các bài toán sẽ yêu cầu tuỳ biến Linked List
• Học về Linked List sẽ giúp các bạn hiểu phần nào cách sử dụng con trỏ
• Linked List là nền tảng cơ sở cho việc thiết kế rất nhiều các cấu trúc dữ liệu khác

---

Cơ chế hoạt động của Linked List

Nguyên tắc hoạt động

Hãy quay lại một chút với định nghĩa trên, Linked List “là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện một dãy”. Do đó, Linked List là mỗi chuỗi các nút được kết nối với nhau.

Mô hình của Linked List được thể hiện qua hình sau:

Ta có một node mở đầu gọi là Head để nhận biết vị trí bắt đầu của dãy, mỗi node sẽ có hai con trỏ prv, nxt trong đó nxt là con trỏ được trỏ đến phần tử kế tiếp, prv là con trỏ được trỏ đến phần tử liền trước. Với phần tử đầu tiên (head), prv trỏ đến NULL, với phần tử cuối cùng, nxt trỏ đến NULL. Nếu nhìn lại ví dụ trong thực tế thì prv, nxt chính là hai tay của một người, người đầu và người cuối dãy dĩ nhiên chỉ cần nắm tay một người. Ngoài ra, trong mỗi node sẽ có một biến data để thể hiện cho giá trị node đó.

Một node sẽ được code như sau:

struct Node{
    int data;
    Node *prv, *nxt;

    Node(int _data){
        data = _data;
        prv = NULL;
        nxt = NULL;
    }
};

---

Thêm phần tử vào Linked List

Khi thêm một phần tử vào trong Linked List, sẽ có 4 trường hợp xảy ra:

• Linked List trống
• Thêm vào vị trí đầu
• Thêm vào sau vị trí cuối
• Thêm vào vị trí xác định

Bây giờ, chúng ta sẽ cùng nhau đi giải quyết từng vấn đề một.

---

Linked List trống

Lúc này, chúng ta sẽ cần gán head của Linked List chính là node mới thêm vào

---

Thêm vào vị trí đầu

Cơ chế thêm vào vị trí đầu được thể hiện qua mô hình sau:

Ta thấy ở đây có 3 sự thay đổi:

• prv của head ban đầu sẽ trỏ về node mới
• nxt của node mới sẽ trỏ về head ban đầu
• Cập nhật lại head là node mới

prv của node mới mặc định là NULL nên không cần thay đổi

---

Thêm vào sau vị trí cuối

Cơ chế thêm vào vị trí cuối được thể hiện qua mô hình sau:

Ta thấy ở đây có 2 sự thay đổi:

• nxt của phần tử cuối trỏ về node mới
• prv của node mới trỏ về phần tử cuối

nxt của node mới mặc định là NULL nên không cần thay đổi

---

Thêm vào vị trí xác định

Cơ chế thêm vào vị trí xác định được thể hiện qua mô hình sau:

Ta thấy ở đây có 4 sự thay đổi. Giả sử ta thêm phần tử vào vị trí k thì:

• nxt của node k – 1 sẽ trỏ về node mới
• prv của node mới sẽ trỏ về node k – 1
• nxt của node mới sẽ trỏ về node k
• prv của node k sẽ trỏ về node mới

---

Code

void addNewNode(int pos, int data){
    Node* newNode = new Node(data);
    if(head == NULL){
        head = newNode;
        sz++;
        return;
    }

    if(pos == 1){ // Thêm vào đầu
        newNode->nxt = head;
        head->prv = newNode;
        head = newNode;
        sz++;
        return;
    }

    if(pos == sz + 1){ // Thêm vào sau phần tử cuối cùng
        Node* temp = head;
        // Node temp sau thao tác này là node cuối cùng
        while(temp->nxt != NULL) temp = temp->nxt;
        newNode->prv = temp;
        temp->nxt = newNode;
        sz++;
        return;
    }

    int count = 1;
    Node* temp = head;
    // Node temp sau thao tác này chính là node ở vị trí thứ pos
    while(count < pos){
        temp = temp->nxt;
        count++;
    }

    newNode->nxt = temp;
    newNode->prv = temp->prv;
    newNode->prv->nxt = newNode;
    temp->prv = newNode;
    sz++;
}

---

Loại bỏ phần tử khỏi Linked List

Tương tự với việc thêm, loại bỏ phần tử ra khỏi Linked List cũng có 4 trường hợp:

• Linked List chỉ có 1 phần tử
• Loại node ở vị trí đầu
• Loại node ở vị trí cuối
• Loại node ở vị trí xác định

---

Linked List chỉ có 1 phần tử

Lúc này, ta chỉ cần gán head bằng NULL thì Linked List sẽ tự động rỗng.

---

Loại node ở vị trí đầu

Cơ chế loại bỏ node ở đầu được thể hiện qua mô hình sau:

Ta thấy, ở đây có 2 sự thay đổi:

• prv của node kế tiếp head trỏ về NULL
• head được cập nhật lại là node kế tiếp của head ban đầu

---

Loại bỏ node ở vị trí cuối

Cơ chế loại bỏ node ở cuối được thể hiện qua mô hình sau:

Ta thấy chỉ có 1 sự thay đổi duy nhất là nxt của node liền trước node cuối trỏ về NULL

---

Loại bỏ node ở vị trí xác định

Cơ chế loại bỏ node ở vị trí xác định được thể hiện qua mô hình sau:

Ta thấy ở đây có 2 sự thay đổi. Giả sử ta loại bỏ node ở vị trí k thì:

• nxt của node k - 1 sẽ trỏ về node k + 1
• prv của node k + 1 sẽ trỏ về node k - 1

---

Code

void deleteNode(int pos){
    Node* temp = head;

    if(sz == 1){ // Linked List chỉ có 1 node
        head = NULL;
        sz--;
        return;
    }

    int count = 1;
    // Node temp sau thao tác này chính là node ở vị trí thứ pos
    while(count < pos){
        temp = temp->nxt;
        count++;
    }

    if(pos == 1){ // Xoá bỏ node đầu
        temp->nxt->prv = NULL;
        head = temp->nxt;
        sz--;
        return;
    }

    if(pos == sz){ // Xoá bỏ node cuối
        temp->prv->nxt = NULL;
        sz--;
        return;
    }

    temp->prv->nxt = temp->nxt;
    temp->nxt->prv = temp->prv;
    sz--;
}

---

Code hoàn chỉnh

struct Node{
    int data;
    Node *prv, *nxt;

    Node(int _data){
        data = _data;
        prv = NULL;
        nxt = NULL;
    }
};

struct LinkedList{
    Node *head;
    int sz = 0;

    void addNewNode(int pos, int data){
        Node* newNode = new Node(data);
        if(head == NULL){
            head = newNode;
            sz++;
            return;
        }

        if(pos == 1){ // Chèn vào đầu
            newNode->nxt = head;
            head->prv = newNode;
            head = newNode;
            sz++;
            return;
        }

        if(pos == sz + 1){ // Chèn vào sau phần tử cuối cùng
            Node* temp = head;
            // Node temp sau thao tác này là node cuối cùng
            while(temp->nxt != NULL) temp = temp->nxt;
            newNode->prv = temp;
            temp->nxt = newNode;
            sz++;
            return;
        }

        int count = 1;
        Node* temp = head;
        // Node temp sau thao tác này chính là node ở vị trí thứ pos
        while(count < pos){
            temp = temp->nxt;
            count++;
        }

        newNode->nxt = temp;
        newNode->prv = temp->prv;
        newNode->prv->nxt = newNode;
        temp->prv = newNode;
        sz++;
    }

    void deleteNode(int pos){
        Node* temp = head;

        if(sz == 1){
            head = NULL;
            sz--;
            return;
        }

        int count = 1;
        // Node temp sau thao tác này chính là node ở vị trí thứ pos
        while(count < pos){
            temp = temp->nxt;
            count++;
        }

        if(pos == 1){ // Xoá bỏ node đầu
            temp->nxt->prv = NULL;
            head = temp->nxt;
            sz--;
            return;
        }

        if(pos == sz){ // Xoá bỏ node cuối
            temp->prv->nxt = NULL;
            sz--;
            return;
        }

        temp->prv->nxt = temp->nxt;
        temp->nxt->prv = temp->prv;
        sz--;
    }

    void print(){
        Node* temp = head;
        while(temp != NULL){
            cout << temp->data << " ";
            temp = temp->nxt;
        }
    }
} LinkedList;

Lưu ý: Tất cả các hàm trên đều chỉ đúng khi vị trí pos có ý nghĩa, nghĩa là các vị trí thêm phải nằm trong đoạn [1, sz + 1], các vị trí xoá phải nằm trong đoạn [1, sz].

---

Demo

Để tiện lợi cho việc demo, mình sẽ tạo ra thêm một hàm print() bên trong struct để in ra toàn bộ giá trị các node của Linked List như sau:

void print(){
    Node* temp = head;
    while(temp != NULL){
        cout << temp->data << " ";
        temp = temp->nxt;
    }
    cout << endl;
}

Ta có một đoạn code demo các phương thức như sau:

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *prv, *nxt;

    Node(int _data){
        data = _data;
        prv = NULL;
        nxt = NULL;
    }
};

struct LinkedList{
    Node *head;
    int sz = 0;

    void addNewNode(int pos, int data){
        Node* newNode = new Node(data);
        if(head == NULL){
            head = newNode;
            sz++;
            return;
        }

        if(pos == 1){ // Chèn vào đầu
            newNode->nxt = head;
            head->prv = newNode;
            head = newNode;
            sz++;
            return;
        }

        if(pos == sz + 1){ // Chèn vào sau phần tử cuối cùng
            Node* temp = head;
            // Node temp sau thao tác này là node cuối cùng
            while(temp->nxt != NULL) temp = temp->nxt;
            newNode->prv = temp;
            temp->nxt = newNode;
            sz++;
            return;
        }

        int count = 1;
        Node* temp = head;
        // Node temp sau thao tác này chính là node ở vị trí thứ pos
        while(count < pos){
            temp = temp->nxt;
            count++;
        }

        newNode->nxt = temp;
        newNode->prv = temp->prv;
        newNode->prv->nxt = newNode;
        temp->prv = newNode;
        sz++;
    }

    void deleteNode(int pos){
        Node* temp = head;

        if(sz == 1){
            head = NULL;
            sz--;
            return;
        }

        int count = 1;
        // Node temp sau thao tác này chính là node ở vị trí thứ pos
        while(count < pos){
            temp = temp->nxt;
            count++;
        }

        if(pos == 1){ // Xoá bỏ node đầu
            temp->nxt->prv = NULL;
            head = temp->nxt;
            sz--;
            return;
        }

        if(pos == sz){ // Xoá bỏ node cuối
            temp->prv->nxt = NULL;
            sz--;
            return;
        }

        temp->prv->nxt = temp->nxt;
        temp->nxt->prv = temp->prv;
        sz--;
    }

    void print(){
        Node* temp = head;
        while(temp != NULL){
            cout << temp->data << " ";
            temp = temp->nxt;
        }
        cout << endl;
    }
} LinkedList;

int main(){
    LinkedList.addNewNode(1, 3); 
    // [3]
    LinkedList.addNewNode(2, 5);
    // [3, 5]
    LinkedList.addNewNode(2, 7);
    // [3, 7, 5]
    LinkedList.print();
    LinkedList.deleteNode(2);
    // [3, 5]
    LinkedList.print();
    LinkedList.deleteNode(2);
    // [3]
    LinkedList.print();
    LinkedList.deleteNode(1);
    // []
    LinkedList.print();

    return 0;
}

Khi chạy đoạn code trên ta có kết quả như sau:

---

So sánh Linked List và mảng

Mình sẽ có một bảng so sánh các tính chất của mảng và Linked List

Tuỳ vào các tính chất, đặc điểm của từng cấu trúc dữ liệu mà các bạn có thể đưa ra lựa chọn phù hợp cho vấn đề của mình.

---

Kết luận

Qua bài này chúng ta đã nắm được về Linked List

Bài sau chúng ta sẽ tìm hiểu về cấu trúc dữ liệu Prefix Sum

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.