Single linked list - Danh sách liên kết đơn

Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó kiến thức con trỏ là kiến thức cần có để hiểu cách danh sách liên kết hoạt động. Bạn cũng cần một chút kiến thức về cấp phát bộ nhớ động.
Nội dung bài viết này:
1 Lý thuyết về danh sách liên kết
2 Danh sách liên kết là gì
3 Cài đặt danh sách liên kết đơn
   Khai báo linked list
   Tạo mới một node
   Thêm Node vào danh sách liên kết: Thêm vào đầu, thêm vào cuối và thêm vào 1 vị trí bất kỳ
   Xoá Node khỏi danh sách liên kết: Xoá đầu, xoá cuối và xoá ở vị trí bất kỳ
   Lấy giá trị ở ví trí bất kỳ
   Tìm kiếm trong danh sách liên kết
   Duyệt danh sách liên kết
   Một số hàm bổ trợ khác
   Hàm khởi tạo Node head
   Hàm lấy số phần tử của DSLK
   Hàm nhập danh sách liên kết

1. Lý thuyết về danh sách liên kết

Về bản chất, danh sách liên kết có chức năng như một mảng, có thể thêm và xoá các phần tử ở bất kỳ vị trí nào khi cần thiết. Một số sự khác nhau giữa danh sách liên kết và mảng:

Nội dung	Mảng	Danh sách liên kết
Kích thước	Kích thước cố định Cần chỉ rõ kích thước trong khi khai báo	Kích thước thay đổi trong quá trình thêm/ xóa phần tử Kích thước tối đa phụ thuộc vào bộ nhớ
Cấp phát bộ nhớ	Tĩnh: Bộ nhớ được cấp phát trong quá trình biên dịch	Động: Bộ nhớ được cấp phát trong quá trình chạy
Thứ tự & sắp xếp	Được lưu trữ trên một dãy ô nhớ liên tục	Được lưu trữ trên các ô nhớ ngẫu nhiên
Truy cập	Truy cập tới phần tử ngẫu nhiên trực tiếp bằng cách sử dụng chỉ số mảng: O(1)	Truy cập tới phần tử ngẫu nhiên cần phải duyệt từ đầu/cuối đến phần tử đó: O(n)
Tìm kiếm	Tìm kiếm tuyến tính hoặc tìm kiếm nhị phân	Chỉ có thể tìm kiếm tuyến tính

Lưu ý: Ở bảng phía trên, các phần in nghiêng là ưu điểm hơn sơ với đối thủ.

2. Danh sách liên kết là gì
Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp them cách sao cho mỗi Node chứa "một giá trị" (Data) và "một con trỏ" (Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ đến NUL, nghĩa là đó là phần tử cuối cùng của liên kết danh sách.

Và đây là hình ảnh mô phỏng một danh sách liên kết đơn đầy đủ :

Các loại danh sách liên kết:
_ Danh sách liên kết đơn (Single linked list): Chỉ có sự kết nối từ phần tử phía trước với phần tử phía sau.
_ Danh sách liên kết đôi (Double linked list): Có sự kết nối hai chiều giữa phần tử phía trước và phần tử phía sau.
_ Danh sách liên kết vòng (Circular linked list): Có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín.

3. Cài đặt danh sách liên kết đơn 
3.1 Khai báo linked list
Để đơn giản hoá, data của chúng ta sẽ là số nguyên(int). Bạn cũng có thể sử dụng các kiểu nguyên thuỷ khác(float, char ...) hay các kiểu dữ liệu struct (SinhVien, CanBo ...) tự tạo.

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

Khai báo trên sẽ được sự dụng cho mọi Node trong linked list. Trường data sẽ lưu giữ giá trị và next sẽ là con trỏ để trỏ đến thằng kế tiếp của nó.

Tại sao next lại là kiểu LinkedList của chính nó? 
Bởi vì nó là con trỏ trỏ của chính bản thân nó và nó trỏ tới một thằng Node kế tiếp cũng có kiểu LinkedList.

//
//  main.cpp
//  DanhSachLienKet2
//
//  Created by Nguyen on 9/12/19.
//  Copyright © 2019 Apple. All rights reserved.
//

#include <iostream>
#include <ctime>

using namespace std;

struct Data {
    int n;
};

struct NODE {
    Data data;
    NODE* pNext;
};

struct LIST {
    NODE *pHead;
    NODE *pTail;
};

NODE* CreateNode(Data data) {
    NODE* node = new NODE;
    if(node == NULL) {
        return NULL;
    }
    node->data = data;
    node->pNext = NULL;
    return node;
};

NODE* CreateNode(int n) {
    Data data = { n };
    NODE* node = CreateNode(data);
    return node;
};

void initList(LIST& lst) {
    lst.pHead = lst.pTail = NULL;
}

bool IsEmpty(LIST lst) {
    if(lst.pHead == NULL) {
        return true;
    }
    return false;
}

//Thêm node vào list
void AddHead(LIST& lst, NODE* pNode) {
    if(IsEmpty(lst)) {
        lst.pHead = lst.pTail = pNode;
    } else {
        pNode->pNext = lst.pHead;
        lst.pHead = pNode;
    }
}

void AddHead(LIST& lst, int n) {
    NODE* pNode = CreateNode(n);
    AddHead(lst, pNode);
}

//Thêm node vào cuối danh sách
void AddTail(LIST& lst, NODE* pNode) {
    if(IsEmpty(lst)) {
        lst.pHead = lst.pTail = pNode;
    } else {
        lst.pTail->pNext = pNode;
        lst.pTail = pNode;
    }
}

void AddTail(LIST& lst, int n) {
    NODE* pNode = CreateNode(n);
    AddTail(lst, pNode);
}

//Xoá phần tử đầu danh sách
void DelHead(LIST& lst) {
    if(IsEmpty(lst)) {
        return;
    } else {
        NODE* p = lst.pHead;
        lst.pHead = lst.pHead->pNext;
        delete p;
    }
}

//Xoá phần tử cuối cùng của danh sách
void DelTail(LIST& lst) {
    if(IsEmpty(lst)) {
        return;
    } else {
        for(NODE* k = lst.pHead; k != NULL; k = k->pNext) {
            //Phát hiện thằng kế cuối
            if(k->pNext == lst.pTail) {
                delete lst.pTail; //Xoá đi phần tử cuối
                k->pNext = NULL; // Cho con trỏ của node kế cuối trỏ đến vùng nhớ NULL
                lst.pTail = k; // Cập nhật lại pTail
                return;
            }
        }
    }
}

//Xoá 1 node sau node q trong danh sách
void XoaSau(LIST& lst, NODE* q) {
    if(IsEmpty(lst)) {
        return;
    }
    //Duyệt danh sách từ đầu đến cuối để tìm node q
    for(NODE* k = lst.pHead; k != NULL; k = k->pNext) {
        if(k->data.n == q->data.n) {
            NODE* g = k->pNext; //node g chính là node nằm sau node k <=> node mà ta sẽ xoá
            k->pNext = g->pNext; //cập nhật mối liên kết giữa node k(node q) với node g
            delete g; //Xoá node nằm sau node q
        }
    }
}

//Xoá 1 node có khoá k bất kì
void XoaNodeCoKhoaBatKy(LIST& lst, int x) {
    if(IsEmpty(lst)) {
        return;
    }
    //nếu node cần xoá nằm ở đầu danh sách
    if(lst.pHead->data.n == x) {
        DelHead(lst);
        return;
    }
    //nếu node cần xoá nằm ở cuối danh sách
    if(lst.pTail->data.n == x) {
        DelTail(lst);
        return;
    }
    NODE* g = new NODE;
    for(NODE* k = lst.pHead; k != NULL; k->pNext) {
        if(k->data.n == x) {
            g->pNext = k->pNext;
            delete k; //Xoá node nằm sau node k
            return;
        }
        g = k; // cho node g trỏ đến node k
    }
}

//Chèn phần tử vào sau node q
void InsertNode(LIST& lst, NODE* q, NODE* pNewNode) {
    if(pNewNode == NULL || q == NULL) return;
    if(IsEmpty(lst)) {
        lst.pHead = lst.pTail = pNewNode;
    } else {
        if(lst.pTail == q) {
            AddTail(lst, pNewNode);
        } else {
            pNewNode->pNext = q->pNext;
            q->pNext = pNewNode;
        }
    }
}

//Get node tại index
NODE* GetNodeAt(LIST lst, int idx) {
    if(IsEmpty(lst) && idx < 0) {
        return NULL;
    } else {
        int curIdx = 0;
        NODE* pNode = lst.pHead;
        while(pNode != NULL && curIdx < idx) {
            curIdx++;
            pNode = pNode->pNext;
        }
        return pNode;
    }
}

//Chèn phần tử sau index
void InsertNode(LIST& lst, int idx, NODE* pNewNode) {
    NODE* pNode = GetNodeAt(lst, idx);
    if(pNode != NULL) {
        InsertNode(lst, pNode, pNewNode);
    }
}

//Xuất danh sách
void PrintList(LIST lst,  char* mess) {
    cout << mess << endl;
    if(IsEmpty(lst)) {
        cout << "List is empty!" << endl;
    } else {
        NODE* pNode = lst.pHead; //Gan node = pHead
        while(pNode != NULL) {
            cout << pNode->data.n << " ";
            pNode = pNode->pNext;
        }

    }
}

//Lấy size của liên kết
void GetSize(LIST lst, char* mess) {
    cout << mess << endl;
    if(IsEmpty(lst)) {
        cout << "List is empty!" << endl;
    } else {
        int count = 0;
        NODE* pNode = lst.pHead; //Gan node = pHead
        while (pNode != NULL) {
            count++;
            pNode = pNode->pNext;
        }
        cout << "Size of lien ket = " << count << endl;
    }
}

//Hàm giải phóng vùng nhớ cho danh sách liên kết đơn
void GiaiPhongDanhSach(LIST& lst) {
    // Duyệt từ đầu danh sách đến cuối danh sách
    NODE* k = NULL;
    while (k != NULL) {
        k = lst.pHead;
        lst.pHead = lst.pHead->pNext;
        delete k;
    }
}

int main() {
    int a = 10;
    LIST lst;
    Data data = { 69 };

    Data* pData = new Data;
    pData->n = 69;

    NODE* node = CreateNode(*pData);
    cout << node->data.n << endl;
    cout << a << endl;

    //Khởi tạo list
    initList(lst);

    //Kiểm tra list rỗng
    if(IsEmpty(lst)) {
        cout << "List is empty" << endl;
    } else {
        cout << "List is not empty" << endl;
    }

    //Thêm node vào đầu list
    srand(time(NULL));
    for(int i = 0; i < 10; i++) {
        int nRand = rand() % 100;
        AddTail(lst, nRand);
    }

    cout << "Node thu 3: " << GetNodeAt(lst, 3)->data.n << endl;
    //Insert node vào vị trí số 3
    InsertNode(lst, 3, CreateNode(69));

    //Xuất danh sách
    PrintList(lst, "Xuat danh sach");
    GetSize(lst, "Kich thuoc cua danh sach");
    DelHead(lst);
    PrintList(lst, "Xuat danh sach");
    GiaiPhongDanhSach(lst);
    system("pause");
    return 0;
};