Linked List | How Kteam

Posted on by adminChuyên mục:Kiến thức Internet
Trong bài học kinh nghiệm ngày ngày hôm nay, tất cả chúng ta sẽ cùng nhau đi tìm hiểu và khám phá về Linked List, một trong những cấu trúc tài liệu được ứng dụng phổ cập nhất trong trong thực tiễn. Hãy cùng nhau đi tìm hiểu và khám phá sao nó lại được sử dụng nhiều vậy nhé !

Nội dung

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

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

Bạn đang đọc: Linked List | How Kteam

  • Khái niệmLinked List
  • Cơ chế hoạt động giải trí củaLinked List
  • So sánhLinked Listvà mảng

Bài toán đặt ra

Chúng ta có một dãy số gồm n thành phần. Hãy tìm cách chèn vào vị trí i một giá trị mà không làm biến hóa vị trí tương đối của những thành phần trong dãy .
Ví dụ : Ta có dãy [ 1, 4, 6, 2, 3, 5 ]. Sau khi chèn thành phần 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 tàng trữ một dãy dưới dạng mảng mà chèn trực tiếp thành phần 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ó sáng tạo độc đáo sau : Dồn những thành phần khởi đầu từ vị trí cần chèn đến sau cuối về ô sau nó, khi đó, vị trí cần chèn sẽ trống .
Khi tiến hành dưới quy mô code ta sẽ có : Nếu như muốn chèn thêm thành phần ở vị trí k trong mảng, ta sẽ gán an + 1 = an, an = an-1, …, ak + 1 = ak .

Lúc này, đoạn an + 1, an, an-1, …, ak + 1 chính là đoạn an, an-1, an-2, …, ak trong mảng bắt đầu, ta chỉ cần gán ak bằng giá trị cần chèn là coi như đã chèn được một thành phần 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 để triển khai phép gán và do kích cỡ mảng là cố định và thắt chặt nên số thành phần chèn được là có số lượng 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 thành phần mới vào vị trí k, chỉ có quan hệ trước sau giữa thành phần ak-1, ak và thành phần được chèn thêm là có sự biến hóa. Do đó, ta sẽ nghĩ cách làm thế nào chỉ đổi khác quan hệ của 3 thành phần này mà không làm tác động ảnh hưởng đến những thành phần 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 tiễn. Chúng ta có một hàng ngang gồm n người nắm tay nhau. Bây giờ, tất cả 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ì tất cả chúng ta sẽ làm thế nào ? Có phải là tất cả 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 họa trên chính là ý tưởng sáng tạo cơ sở của Linked List. Bây giờ, để hiểu rõ hơn, tất cả chúng ta sẽ đi khám phá chi tiết cụ thể về Linked List .

Khái niệm Linked List

Linked List ( tiếng Việt : list link ) là một tập hợp tuyến tính những thành phần tài 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 thành phần chỉ đến thành phần tiếp theo. Nó là một cấu trúc tài liệu gồm có một tập hợp những nút cùng bộc lộ một dãy .
Định nghĩa trên là tương đối phức tạp và khó hiểu nên những bạn cũng không cần quá chăm sóc để làm gì. Điều ta chú trọng là Linked List sẽ làm được gì .
Một Linked List sẽ có những phương pháp cơ bản sau :

  • Chèn một thành phần vào vị trí xác lập
  • Xóa một thành phần ở vị trí xác lập

Trên thực tiễn, có rất nhiều kiểu Linked List như Single Linked List ( Danh sách link đơn ), Double Linked List ( Danh sách liên kết đôi ), Circular Linked List ( Danh sách link vòng tròn ) nhưng về cơ bản cách hoạt động giải trí của chúng là trọn vẹn giống nhau. Trong bài học kinh nghiệm này, mình sẽ trình làng về Double Linked List .
Bài học này, mình sẽ đi cụ thể vào phương pháp hoạt động giải trí của Linked List. Có 3 lí do cho việc này :

  • Đa phần những bài toán sẽ nhu yếu tùy biếnLinked List
  • Học vềLinked Listsẽ giúp những bạn hiểu phần nào cách sử dụng con trỏ
  • Linked Listlà nền tảng cơ sở cho việc phong cách thiết kế rất nhiều những cấu trúc tài 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 ít với định nghĩa trên, Linked List “ là một cấu trúc tài liệu gồm có một tập hợp những nút cùng bộc lộ một dãy ”. Do đó, Linked List là mỗi chuỗi những nút được liên kết với nhau .
Mô hình của Linked List được biểu lộ 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 thành phần 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 lập

Bây giờ, tất cả chúng ta sẽ cùng nhau đi xử lý từng yếu tố một .

Linked List trống

Lúc này, tất cả 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 bộc lộ qua quy mô sau :

Ta thấy ở đây có 3 sự biến hóa :

  • prvcủa head bắt đầu sẽ trỏ vềnodemới
  • nxtcủa
    nodemới sẽ trỏ về head khởi đầu
  • Cập nhật lại head lànodemới

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

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

Cơ chế thêm vào vị trí cuối được bộc lộ qua quy mô sau :

Ta thấy ở đây có 2 sự biến hóa :

nxt của node mới mặc định là NULL nên không cần biến hóa

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

Cơ chế thêm vào vị trí xác lập được biểu lộ qua quy mô sau :

Ta thấy ở đây có 4 sự biến hóa. Giả sử ta thêm thành phần vào vị trí k thì :

  • nxtcủa
    nodek – 1 sẽ trỏ vềnodemới
  • prvcủa
    nodemới sẽ trỏ vềnodek – 1
  • nxtcủa
    node mới sẽ trỏ vềnodek
  • prvcủa
    nodek sẽ trỏ vềnodemớ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, vô hiệu thành phần ra khỏi Linked List cũng có 4 trường hợp :

  • Linked List chỉ có 1 thành phần
  • Loạinodeở vị trí đầu
  • Loạinodeở vị trí cuối
  • Loạinodeở vị trí xác lập

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 hóa rỗng .

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

Cơ chế vô hiệu node ở đầu được biểu lộ qua quy mô sau :

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

  • prvcủa
    nodetiếp nối head trỏ về NULL
  • headđược update lại lànodetiếp nối của head bắt đầu

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

Cơ chế vô hiệu node ở cuối được bộc lộ qua quy mô sau :

Ta thấy chỉ có 1 sự biến hóa 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ế vô hiệu node ở vị trí xác lập được bộc lộ qua quy mô sau :

Ta thấy ở đây có 2 sự biến hóa. Giả sử ta vô hiệu node ở vị trí k thì :

  • nxtcủa
    nodek – 1 sẽ trỏ vềnodek + 1
  • prvcủa
    nodek + 1 sẽ trỏ vềnodek – 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ả những hàm trên đều chỉ đúng khi vị trí pos có ý nghĩa, nghĩa là những vị trí thêm phải nằm trong đoạn [ 1, sz + 1 ], những vị trí xóa phải nằm trong đoạn [ 1, sz ] .

Demo

Để thuận tiện cho việc demo, mình sẽ tạo ra thêm một hàm print ( ) bên trong struct để in ra hàng loạt giá trị những 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 những phương pháp như sau :

#include
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ó tác dụng như sau :

So sánh Linked List và mảng

Mình sẽ có một bảng so sánh những đặc thù của mảng và Linked List

Tùy vào những đặc thù, đặc thù của từng cấu trúc tài liệu mà những bạn hoàn toàn có thể đưa ra lựa chọn tương thích cho yếu tố của mình .

Kết luận

Qua bài này tất cả 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 vất vả hay vướng mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI và ĐÁP trên thư viện Howkteam. com để nhận được sự tương hỗ từ hội đồng .

admin