Linklist 基礎

#clippings

關於鏈表，你該瞭解這些！

什麼是鏈表，鏈表是一種通過指針串聯在一起的線性結構，每一個節點由兩部分組成，一個是數據域一個是指針域（存放指向下一個節點的指針），最後一個節點的指針域指向null（空指針的意思）。

鏈表的入口節點稱為鏈表的頭結點也就是head。

如圖所示：

接下來說一下鏈表的幾種類型:

單鏈表

剛剛說的就是單鏈表。

雙鏈表

單鏈表中的指針域只能指向節點的下一個節點。

雙鏈表：每一個節點有兩個指針域，一個指向下一個節點，一個指向上一個節點。

雙鏈表 既可以向前查詢也可以向後查詢。

如圖所示：

循環鏈表

循環鏈表，顧名思義，就是鏈表首尾相連。

循環鏈表可以用來解決約瑟夫環問題。

瞭解完鏈表的類型，再來說一說鏈表在內存中的存儲方式。

數組是在內存中是連續分佈的，但是鏈表在內存中可不是連續分佈的。

鏈表是通過指針域的指針鏈接在內存中各個節點。

所以鏈表中的節點在內存中不是連續分佈的 ，而是散亂分佈在內存中的某地址上，分配機製取決於作業系統的內存管理。

如圖所示：

這個鏈表起始節點為2， 終止節點為7， 各個節點分佈在內存的不同地址空間上，通過指針串聯在一起。

接下來說一說鏈表的定義。

鏈表節點的定義，很多同學在面試的時候都寫不好。

這是因為平時在刷leetcode的時候，鏈表的節點都默認定義好了，直接用就行了，所以同學們都沒有注意到鏈表的節點是如何定義的。

而在面試的時候，一旦要自己手寫鏈表，就寫的錯漏百出。

這裡我給出C/C++的定義鏈表節點方式，如下所示：

struct ListNode {
    int val;  
    ListNode *next;  
    ListNode(int x) : val(x), next(NULL) {}  
};

有同學說了，我不定義構造函數行不行，答案是可以的，C++默認生成一個構造函數。

但是這個構造函數不會初始化任何成員變量，下面我來舉兩個例子：

通過自己定義構造函數初始化節點：

ListNode* head = new ListNode(5);

使用默認構造函數初始化節點：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定義構造函數使用默認構造函數的話，在初始化的時候就不能直接給變量賦值！

刪除節點

刪除D節點，如圖所示：

只要將C節點的next指針 指向E節點就可以了。

那有同學說了，D節點不是依然存留在內存裡麼？只不過是沒有在這個鏈表裡而已。

是這樣的，所以在C++裡最好是再手動釋放這個D節點，釋放這塊內存。

其他語言例如Java、Python，就有自己的內存回收機製，就不用自己手動釋放了。

添加節點

如圖所示：

可以看出鏈表的增添和刪除都是O(1)操作，也不會影響到其他節點。

但是要注意，要是刪除第五個節點，需要從頭節點查找到第四個節點通過next指針進行刪除操作，查找的時間複雜度是O(n)。

再把鏈表的特性和數組的特性進行一個對比，如圖所示：

數組在定義的時候，長度就是固定的，如果想改動數組的長度，就需要重新定義一個新的數組。

鏈表的長度可以是不固定的，並且可以動態增刪， 適合數據量不固定，頻繁增刪，較少查詢的場景。