C++ 鏈表的全面解析

一、什麼是鏈表

鏈表是一種線性數據結構，與數組不同的是，鏈表元素不存儲在連續的內存空間中，而是通過指針鏈接在一起。鏈表的每個節點由兩個部分組成，一個是存儲數據的部分，另一個是指向下一個節點的指針。

鏈表主要分為單向鏈表、雙向鏈表和循環鏈表。其中，單向鏈表每個節點只有一個指針指向下一個節點，雙向鏈表每個節點有兩個指針，一個指向前一個節點，一個指向後一個節點，循環鏈表最後一個節點指向鏈表的頭結點，形成一個環。

二、鏈表的優點和缺點

鏈表相比於數組的優點在於：

1、動態分配內存，節點數可以隨時改變；

2、插入和刪除操作方便，不需要移動大量元素；

3、不需要預先分配大量內存空間，節省內存。

鏈表相比於數組的缺點在於：

1、不支持隨機訪問，只能從頭或尾開始遍歷；

2、空間佔用多，需要額外的指針存儲節點間關係；

3、緩存不友好，由於鏈表元素間不連續，不易被緩存。

三、鏈表的基本操作

1. 創建鏈表

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int val) {
        this->val = val;
        this->next = nullptr;
    }
};

ListNode* createList(vector nums) {
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    for (int num : nums) {
        ListNode* node = new ListNode(num);
        cur->next = node;
        cur = cur->next;
    }
    return head->next;
}

2. 遍歷鏈表

void traverseList(ListNode* head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        cout <val <next;
    }
    cout << endl;
}

3. 插入節點

void insertNode(ListNode* head, int val, int index) {
    ListNode* node = new ListNode(val);
    ListNode* cur = head;
    for (int i = 0; cur != nullptr && i next;
    }
    if (cur == nullptr) {
        return;
    }
    node->next = cur->next;
    cur->next = node;
}

4. 刪除節點

void deleteNode(ListNode* head, int index) {
    ListNode* cur = head;
    for (int i = 0; cur != nullptr && i next;
    }
    if (cur == nullptr || cur->next == nullptr) {
        return;
    }
    ListNode* del = cur->next;
    cur->next = del->next;
    delete del;
}

四、鏈表的應用場景

鏈表常用於實現如下的數據結構：

1、隊列和棧；

2、圖、樹等複雜數據結構的節點存儲和遍歷；

3、處理海量數據，如鏈表分段處理大文件。

五、總結

鏈表作為一種常用的數據結構，具有一些獨特的特點。在實際的編程工作中，我們需要根據具體情況選擇合適的數據結構。掌握鏈表的基本操作，有助於我們更加高效地處理鏈表相關問題。