單向鏈表結構

定義：
單鏈表是一種鏈式存取的數據結構，單鏈表中的數據是以結點的形式存在，每一個結點是由數據元素和下一個結點的存儲的位置組成。

單鏈表的邏輯結構如下（帶頭節點）：

鏈表在內存中的存儲結構如下：

解釋：

1. 鏈表是以節點的方式來存儲，是鏈式存儲;
2. 每個節點都包含data域和next域：next指向下一個節點;
3. 鏈表的各個節點的內存地址不一定是連續存儲的;
4. head節點：不存放具體的數據，作用就是表示單鏈表的頭；

單鏈表與數組的區別是：
單鏈表的數據元素存放在內存空間的地址是不連續的，而數組的數據元素存放的地址在內存空間中是連續的，這也是為什么根據索引無法像數組那樣直接就能查詢到數據元素。

單向鏈表的特點：

• 每個節點只包含一個指向下一個節點的指針；
• 只能從頭到尾單向遍歷；

應用場景：

• 簡單列表應用；
• 棧的實現；

操作的復雜度分析：

• 讀、寫元素
  O(n);
• 刪除元素
  O(1);
• 增加元素
  O(1);

數組缺點：

• 數組必須占用整塊、連續的內存空間，如果聲明數組過大，可能回導致“內存不足”。
• 數組不夠靈活，一旦需要擴容，會重新申請連續整塊空間，并需要把原數組的數據全部拷貝到新申請的空間。

鏈表缺點：

• 內存空間消耗更大，用于儲存結點指針信息。
• 對鏈表進行頻繁的插入、刪除操作會導致頻繁的內存申請、釋放，容易造成內存碎片，如果是JAVA語言，還有可能會導致頻繁的GC（Garbage Collection，垃圾回收）。

雙向鏈表結構

定義：
雙鏈表（Doubly Linked List）也是一種常見的數據結構，與單鏈表不同的是，雙鏈表每個節點除了包含指向下一個節點的指針（next）外，還包含指向前一個節點的指針（prev）。這使得雙鏈表可以雙向遍歷，即從頭部到尾部或從尾部到頭部。

特點：

• 鏈表的每個節點都包含一個指向前節點和一個指向后節點的指針，可以雙向遍歷。
• 靈活插入：可以在任意節點前后插入新節點

雙鏈表的適合場景：

• 實現雙向隊列(deque)
• 瀏覽器歷史記錄(前進/后退功能)
• 音樂播放器的播放列表
• 撤銷/重做功能實現；

操作的復雜度分析：

• 讀、寫元素
  O(n);
• 刪除元素
  O(1);
• 增加元素
  O(1);