目錄

LinkedList的模擬實現

什么是雙向鏈表

增加數據

頭插法：

?尾插法：

指定的下標插入：

刪除數據

?刪除雙向鏈表中出現的第一個key

置空所有數據

LinkedList和ArrayList的區別

---

????????

順序表對應的集合類是ArrayList；鏈表對應的集合類是LinkedList，在Java集合框架中，它們是兩種最基礎也是最常用的數據結構實現，它們的底層實現原理和性能差異是怎么樣的呢？這里我們先來模擬實現LinkedList；

LinkedList的模擬實現

什么是雙向鏈表

????????首先，我們要知道的是LinkedList的底層使用了雙向鏈表，那么什么是雙鏈表呢？我們前面學過單鏈表是由一個個節點組成，節點中包括數據域和指針域的一個鏈表其中指針域存放著下一個節點的地址值：

????????雙向鏈表同樣也是由一個個節點組成，多了個prev指針，指向前驅節點的地址，和一個last指針指向最后一個節點；那么我們如何構建一個雙向鏈表呢？基于單鏈表的學習，雙向鏈表我們模仿單鏈表的樣式去寫就簡單很多了：

    //1.想構成鏈表的是？->節點由什么組成？定義變量 一個節點為一個對象定義成內部類static class ListNode{public int val;public ListNode next;public ListNode prev;//構造一個節點，只需要實例化public ListNode(int val) {this.val = val;}}//指向節點的一些指針public ListNode head;public ListNode last;//始終指向最后一個節點

?????????這樣寫好一個鏈表的基本結構我們就可以為這個鏈表寫一些操作方法了；雙向鏈表有一些操作時不太涉及prev指針域的，這些操作是跟前面學習的單鏈表一致的，比如：鏈表打印display、表長size、查找鏈表的元素contains、這里就不重復記錄了；具體看單鏈表的手動實現+相關習題，這里主要介紹與單鏈表有點區別的操作。

增加數據

頭插法：

    public void addFirst(int data) {//1.實例化一個節點ListNode node = new ListNode(data);//2.鏈表尾空if (head == null){head = node;last = node;}else {node.next = head;//先綁定后面head.prev = node;head = node;}return;}

雙向鏈表中有兩個指針域，操作節點是要尤其注意操作指針域的順序，要避免數據丟失的情況。?

?尾插法：

    public void addLast(int data) {ListNode node = new ListNode(data);if (head == null){head = node;last = node;}else {last.next = node;node.prev = last;last = node;//注意要更新last節點，保證last是最后一個節點}}

指定的下標插入：

????????在指定下標位置進行插入時，我們重點要關注的是中間插入元素是的操作順序

    public void addIndex(int index, int data) {ListNode node = new ListNode(data);//1.判斷index合法性if (index < 0 && index > size()){throw new IndexException("index非法" + index);}//2.index為0時，頭插if (index == 0){addFirst(data);return;}//index為size時，尾插if (index == size()){addLast(data);return;}//3.找indexListNode cur = findIndex(index);//注意順序node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index){ListNode cur = head;int count = 0;while (count != index){//因為是雙向鏈表，可以訪問到節點的前驅和后繼，所以不用跟單鏈表一樣找index-1cur = cur.next;count++;}return cur;}

刪除數據

?刪除雙向鏈表中出現的第一個key

注意：刪除時要考慮到所有特殊的情況，比如刪除頭結點、尾結點、鏈表只有一個節點的情況：

    public void remove(int key) {//遍歷找keyListNode cur = head;while (cur != null){if (cur.val == key ){//1.要刪的節點是頭結點if (cur == head){head = head.next;if (head != null){head.prev = null;}else {//鏈表只有一個節點且是需要刪除的節點,也得置空last = null;}return;}else {if (cur.next == null){//刪除尾結點cur.prev.next = null;last = last.prev;}else {//刪除中間節點cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}cur = cur.next;}}

????????刪除第一個key值得代碼我們寫出來了，那么刪除所有key值也非常得簡單了，把return去掉讓他繼續往下遍歷往下刪除即可；

置空所有數據

????????我們可以直接簡單粗暴的分別把head和last置空，導致整個表置空；也可以把每個節點的指針域依次置空?，本質上兩種方法時一樣的：

    public void clear() {//循環把節點依次置空ListNode cur = head;while (cur != null){//定義一個指針指向即將被刪除的節點，記錄下下一個要被刪除的節點ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}this.head = null;this.last = null;}

LinkedList和ArrayList的區別

存儲空間方面：

• ArrayList：物理存儲和邏輯順序都是連續的（基于動態數組實現）。

• LinkedList：邏輯上是連續的，但物理存儲不一定連續（基于雙向鏈表實現）。

查找修改效率：

• ArrayList是數組結構,支持隨機訪問，可以直接通過索引定位元素,效率極高O(1);修改的第一步也是要訪問，所以修改的時間復雜度也為O(1)

• LinkedList不支持隨機存取，必須從頭或尾遍歷鏈表,訪問效率較低O(n)

插入和刪除元素效率：

• ArrayList?插入或刪除除了頭節點和尾結點元素時，需要移動后續所有元素，效率較低O(n)

• LinkedList只需調整相鄰節點的指針，無需移動數據，效率更高O(1)

擴容機制：

• ArrayList:采用靜態分配，初始容量固定，擴容時需要重新分配更大的數組并復制數據,時間復雜度 O(n)。可能導致空間浪費或頻繁擴容。

• LinkedList:動態分配，每次插入新元素時才分配內存，無需擴容。沒有容量限制，但每個節點需要額外存儲指針，占用更多內存。

適用場景:

• ArrayList：適合讀多寫少的場景,。

• LinkedList：適合增刪頻繁的場景。

---

?感謝大家閱讀📚點贊👍收藏?評論?關注?

博客主頁： 【長毛女士-CSDN博客】?