連結串列的由來

一、連結串列的由來

我們接觸最多的資料儲存結構應該是陣列了，在實際場景中它的出現頻率極高，但是它並不能適於用所有情況。這也是的連結串列

原因如下：

在很多程式語言中，陣列的長度是固定的，所以當陣列已被資料填滿時，再要加入新的元素就會非常困難。在陣列中的新增和刪除元素很麻煩，因為需要將陣列中的其他元素向前或向後平移。JavaScript中陣列的主要問題是，它們被實現成了物件，與其他語言（比如 C++ 和 Java） 的陣列相比，效率較低。

為了解決上述問題如果你發現數組在實際使用時很慢，就可以考慮使用連結串列來替代它。除了對資料的隨機訪問，連結串列幾乎可以用在任何可以使用一維陣列的情況中，如果需要頻繁的刪除和新增操作，就主動考慮一下連結串列吧～

1.1 特點

優點

訪問時間是線性的(而且難以管道化)，更快的訪問，如隨機訪問，是不可行的。與連結串列相比，陣列具有更好的快取位置。失去了陣列隨機讀取的優點，同時連結串列由於增加了結點的指標域，空間開銷比較大

連結串列有很多種不同的型別：單向連結串列，雙向連結串列以及迴圈連結串列。連結串列可以在多種程式語言中實現。下面出現的程式碼都是用Js實現的，如果不對的地方，歡迎大佬們指正，我們共勉。

二、單鏈表

單鏈表中的每個結點不僅包含值，還包含連結到下一個結點的引用欄位。透過這種方式，單鏈表將所有結點按順序組織起來。、

下面是一個單鏈表的例子：

當你得到了head節點，就得到了整個列表。

我們建立單一節點（Node）的操作應該是這樣的：

2.1 新增節點

就像給繩子打結一樣，新增節點，就是在兩個繩結之間，再打一個新結。

如果我們想在給定的結點 prev 之後新增新值，我們應該：

建立要插入的Node——cur將cur節點的next連結到next節點（pre的下一個節點）將pre的next連結到cur節點

在開頭新增結點

眾所周知，我們使用頭結點（head）來代表整個列表。

因此，在列表開頭新增新節點時更新頭結點 head 至關重要。

初始化一個新結點 cur；將新結點cur的next連結到我們的原始頭結點 head.next節點將head節點的next連結到cur即可。

在末尾新增節點

找到next節點連結為null的節點，以及它的前節點prevprev.next 連結 null 即可

三、設計連結串列

以LeetCode的中的基礎題為例，我們嘗試用代換實現前文提過的思路。707.設計連結串列

題目

設計連結串列的實現。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節點應該具有兩個屬性：val 和 next。val 是當前節點的值，next 是指向下一個節點的指標/引用。如果要使用雙向連結串列，則還需要一個屬性 prev 以指示連結串列中的上一個節點。假設連結串列中的所有節點都是 0-index 的。

在連結串列類中實現這些功能：

get(index)：獲取連結串列中第 index 個節點的值。如果索引無效，則返回-1。addAtHead(val)：在連結串列的第一個元素之前新增一個值為 val 的節點。插入後，新節點將成為連結串列的第一個節點。addAtTail(val)：將值為 val 的節點追加到連結串列的最後一個元素。addAtIndex(index,val)：在連結串列中的第 index 個節點之前新增值為 val 的節點。如果 index 等於連結串列的長度，則該節點將附加到連結串列的末尾。如果 index 大於連結串列長度，則不會插入節點。如果index小於0，則在頭部插入節點。deleteAtIndex(index)：如果索引 index 有效，則刪除連結串列中的第 index 個節點。

示例：

Js版程式碼實現

為了方便操作，我們主動建立了一個節點為頭節點，實際儲存過程中是完全不需要的。

四、連結串列的基本使用場景

1.建立節點

2.建立連結串列

3.查詢目標節點

4.新增操作

5.查詢儲存目標節點的節點

7.列印操作

測試資料