【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)-鏈表

Mr_zhang 發(fā)布于2019-08-23 16:19 / 1296人閱讀

摘要：鏈表鏈表是最基礎(chǔ)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表是非常重要的線性數(shù)據(jù)結(jié)構(gòu)以下三種，底層都是依托靜態(tài)數(shù)組，靠解決固定容量問(wèn)題。要清楚什么時(shí)候使用數(shù)組這樣的靜態(tài)數(shù)據(jù)結(jié)構(gòu)，什么時(shí)候使用鏈表這類(lèi)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。

前言

【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文章大概的內(nèi)容如下：
Arrays(數(shù)組)、Stacks(棧)、Queues(隊(duì)列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹(shù))、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優(yōu)先隊(duì)列)、SegmentTree(線段樹(shù))、Trie(字典樹(shù))、UnionFind(并查集)、AVLTree(AVL 平衡樹(shù))、RedBlackTree(紅黑平衡樹(shù))、HashTable(哈希表)

源代碼有三個(gè)：ES6（單個(gè)單個(gè)的 class 類(lèi)型的 js 文件） | JS + HTML（一個(gè) js 配合一個(gè) html）| JAVA (一個(gè)一個(gè)的工程)

全部源代碼已上傳 github，點(diǎn)擊我吧，光看文章能夠掌握兩成，動(dòng)手敲代碼、動(dòng)腦思考、畫(huà)圖才可以掌握八成。

本文章適合對(duì)數(shù)據(jù)結(jié)構(gòu)想了解并且感興趣的人群，文章風(fēng)格一如既往如此，就覺(jué)得手機(jī)上看起來(lái)比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時(shí)間跨度也算將近半年時(shí)間了，希望對(duì)想學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人或者正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人群有幫助。

鏈表 Linked List

鏈表是最基礎(chǔ)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

鏈表是非常重要的線性數(shù)據(jù)結(jié)構(gòu)

以下三種，底層都是依托靜態(tài)數(shù)組，靠 resize 解決固定容量問(wèn)題。

動(dòng)態(tài)數(shù)組：所謂動(dòng)態(tài)，是從用戶(hù)的角度上來(lái)看的。

棧

隊(duì)列

鏈表是真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

它是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重點(diǎn)，

也有可能是一個(gè)難點(diǎn)，

它是最簡(jiǎn)單的一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，

其它更高級(jí)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)有二分搜索樹(shù)、Trie、

平衡二叉樹(shù)、AVL、紅黑樹(shù)等等，

熟悉了最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，

那么對(duì)于更高級(jí)的也會(huì)比較容易掌握了。

對(duì)于鏈表來(lái)說(shuō)它涉及到了計(jì)算機(jī)領(lǐng)域一個(gè)非常重要的概念

更深入的理解引用（或者指針），

這個(gè)概念和內(nèi)存相關(guān)，

在 java 里面不需要手動(dòng)的管理內(nèi)存，

但是對(duì)鏈表這種數(shù)據(jù)結(jié)構(gòu)更加深入的理解，

可以讓你對(duì) 引用、指針甚至計(jì)算機(jī)系統(tǒng)中

和內(nèi)存管理相關(guān)很多話題有更加深入的認(rèn)識(shí)。

鏈表本身也是有它非常清晰的遞歸結(jié)構(gòu)的，

只不過(guò)由于鏈表這種數(shù)據(jù)結(jié)構(gòu)它本身是一種線性的數(shù)據(jù)結(jié)構(gòu)，

所以依然可以非常容易的使用循環(huán)的方式來(lái)對(duì)鏈表進(jìn)行操作，

但是鏈表本身由于它天生也是具有這種遞歸結(jié)構(gòu)的性質(zhì)，

所以它也能讓你更加深入的理解遞歸機(jī)制相應(yīng)的這種數(shù)據(jù)結(jié)構(gòu)，

在學(xué)習(xí)更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的時(shí)候，

對(duì)遞歸這種邏輯機(jī)制深入的理解是必不可缺的。

鏈表這種數(shù)據(jù)結(jié)構(gòu)本身就具有功能性

它可以用來(lái)組成更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，

比如圖結(jié)構(gòu)、hash 表、棧(鏈表版)、隊(duì)列(鏈表版)，

所以他可以輔助組成其它數(shù)據(jù)結(jié)構(gòu)。

什么是鏈表

數(shù)據(jù)存儲(chǔ)在“節(jié)點(diǎn)”（Node）中

把數(shù)據(jù)存在一種多帶帶的結(jié)構(gòu)中，

這個(gè)結(jié)構(gòu)通常管它叫做節(jié)點(diǎn)，

對(duì)于鏈表節(jié)點(diǎn)來(lái)說(shuō)他通常只有兩部分，

一部分就是存儲(chǔ)真正的數(shù)據(jù)，

另一部分存儲(chǔ)的是當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，

鏈表其實(shí)就像一個(gè)火車(chē)，每一個(gè)節(jié)點(diǎn)都是一節(jié)車(chē)廂，

在車(chē)廂中存儲(chǔ)數(shù)據(jù)，而車(chē)廂和車(chē)廂之間還會(huì)進(jìn)行連接，

以使得這些數(shù)據(jù)是整合在一起的，

這樣用戶(hù)可以方便的在所有的這些數(shù)據(jù)上進(jìn)行查詢(xún)等等其它的操作，

數(shù)據(jù)與數(shù)據(jù)之間連接就是用下面的這個(gè) next 來(lái)完成的

   class Node {
      E e;
      Node next;
   }

鏈表的優(yōu)點(diǎn)

真正的動(dòng)態(tài)，不需要處理固定容量的問(wèn)題，

它不像靜態(tài)數(shù)組那樣一下子 new 出來(lái)一片空間，

也根本不需要考慮這個(gè)空間是不是不夠用，

也根本不用去考慮這個(gè)空間是不是開(kāi)多了。

對(duì)于鏈表來(lái)說(shuō)，你需要多少個(gè)數(shù)據(jù)。

你就可以生成多少個(gè)節(jié)點(diǎn)，

把它們掛接起來(lái)了，這就是所謂的動(dòng)態(tài)。

鏈表的缺點(diǎn)

和數(shù)組相比，它喪失了隨機(jī)訪問(wèn)的能力。

不能像數(shù)組那樣給一個(gè)索引

就能直接訪問(wèn)對(duì)應(yīng)索引位置的元素，

這是因?yàn)閺牡讓訖C(jī)制上數(shù)組所開(kāi)辟的空間

在內(nèi)存里是連續(xù)分布的，

所以才能夠直接去向索引對(duì)應(yīng)的偏移

計(jì)算出相應(yīng)的數(shù)據(jù)所存儲(chǔ)的內(nèi)存地址，

然后就能夠直接用O(1)的復(fù)雜度取出這個(gè)元素，

但是鏈表不同，鏈表由于是靠 next 一層一層連接的，

所以在計(jì)算機(jī)的底層，每一個(gè)節(jié)點(diǎn)他所在的內(nèi)存的位置是不同的，

只能夠靠這個(gè) next 來(lái)一層一層的找到這個(gè)元素，

這就是鏈表最大的缺點(diǎn)。

數(shù)組和鏈表的對(duì)比

數(shù)組

數(shù)組最好永遠(yuǎn)索引有語(yǔ)意的情況，如 scores[2]

最大的優(yōu)點(diǎn)：支持快速查詢(xún)

鏈表

鏈表不適合用于索引有語(yǔ)意的情況。

最大的優(yōu)點(diǎn)：動(dòng)態(tài)存儲(chǔ)。

對(duì)比

數(shù)組也可以沒(méi)有語(yǔ)意，并不是所有的時(shí)候索引是有語(yǔ)意的，

也并不是所有有語(yǔ)意的這樣的一個(gè)標(biāo)志就適合做索引，如身份證號(hào)，

將一個(gè)靜態(tài)數(shù)組改變?yōu)橐粋€(gè)動(dòng)態(tài)數(shù)組，

就是在應(yīng)付不方便使用索引的時(shí)候有關(guān)數(shù)據(jù)存儲(chǔ)的問(wèn)題，

對(duì)于這樣的存儲(chǔ)數(shù)據(jù)的需求使用鏈表是更合適的，

因?yàn)殒湵碜畲蟮膬?yōu)點(diǎn)是動(dòng)態(tài)存儲(chǔ)。

要清楚什么時(shí)候使用數(shù)組這樣的靜態(tài)數(shù)據(jù)結(jié)構(gòu)，

什么時(shí)候使用鏈表這類(lèi)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。

簡(jiǎn)單的代碼示例MyLinkedList

   public class MyLinkedList {

         // 隱藏內(nèi)部實(shí)現(xiàn)，不需要讓用戶(hù)知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }
   }

在鏈表中進(jìn)行添加、插入操作

鏈表是通過(guò)節(jié)點(diǎn)來(lái)裝載元素

并且節(jié)點(diǎn)和節(jié)點(diǎn)之間會(huì)進(jìn)行連接。

如果想訪問(wèn)這條鏈表中所有的節(jié)點(diǎn)，

那么就必須把鏈表的頭給存儲(chǔ)起來(lái)，

通常這個(gè)鏈表的頭叫做的 head，

應(yīng)該說(shuō)在MyLinkedList中

應(yīng)該有一個(gè)變量指向鏈表中的第一個(gè)節(jié)點(diǎn)。

給自定義數(shù)組添加元素是從數(shù)組尾部開(kāi)始添加，

給鏈表添加元素是從數(shù)組頭部開(kāi)始添加，

因?yàn)樽远x數(shù)組有維護(hù)一個(gè) size，

這個(gè) size 指向的是下一個(gè)待添加元素的位置，

所以你直接將 size 做索引直接賦值即可，

有 size 這個(gè)變量在跟蹤數(shù)組的尾巴，

而對(duì)于鏈表來(lái)說(shuō) 有設(shè)置一個(gè)鏈表的頭這樣的一個(gè)變量，

也就是說(shuō)有一個(gè)變量在跟蹤鏈表的頭，

并沒(méi)有一個(gè)變量去跟蹤鏈表的尾巴，

所以在鏈表頭部添加元素是非常方便。

添加操作原理

將一個(gè)新的元素掛接到鏈表頭部，

同時(shí)不破壞現(xiàn)在鏈表的這個(gè)結(jié)構(gòu)，

添加一個(gè)新元素 666，它的名字叫 node，

就只需要使用 node.next = head，

也就是將新添加的元素的 next 指向鏈表的頭，

這個(gè)時(shí)候新添加的元素也成為新的鏈表頭，

也就是head = node，

這樣 head 就會(huì)指向新的元素 666，也就是 node 這個(gè)節(jié)點(diǎn)，

如此一來(lái)就完成了將 node 這個(gè)節(jié)點(diǎn)插入了整個(gè)鏈表的頭部，

node 這個(gè)變量是在一個(gè)函數(shù)中聲明的，

所以函數(shù)結(jié)束之后這個(gè)變量的作用域也就結(jié)束了，

鏈表的 head 也等于 node，

鏈表中就新增了一個(gè)新元素。

在鏈表頭部添加元素非常簡(jiǎn)單，

只需要?jiǎng)?chuàng)建節(jié)點(diǎn)，讓節(jié)點(diǎn)的 next 指向 head，

然后讓 head 重新指向這個(gè)節(jié)點(diǎn)，也就是讓 head 變成新的元素，

因?yàn)殒湵硎菑念^部添加元素的。

在鏈表中間添加元素，

定義一個(gè) prev 的變量指向中間元素的前一個(gè)元素，

然后讓新增加的元素這樣，node.next = prev.next，

之后這樣，prev.next = node，

這樣一來(lái)就在 prev 這個(gè)元素和原本 prev 的下一個(gè)元素之間

插入了一個(gè)新元素，叫做 node，

整個(gè)過(guò)程就是將 prev 的 next(下一個(gè)元素)的引用

傳遞給新元素的 next(下一個(gè)元素)，

然后將 prev 的 next(下一個(gè)元素)變更為這個(gè)新元素，

最后就將新元素插入到中間了。

這個(gè)過(guò)程的關(guān)鍵是找到待添加的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，

這個(gè)就是 prev 變量要做的事情。

在鏈表的操作中很多時(shí)候順序非常重要，

如在鏈表中插入一個(gè)元素，在指定的元素后面插入一個(gè)元素，

并且不影響整個(gè)鏈表結(jié)構(gòu)，和在鏈表中間添加元素一樣，

把原本的node.next = prev.next和prev.next = node

的順序變一下，prev.next = node在前，

node.next = prev.next 在后，這樣一來(lái)邏輯就不成立了，

鏈表不僅斷開(kāi)了，而且新節(jié)點(diǎn)的 next 指向的是自己，死循環(huán)了，

所以一樣的代碼，順序顛倒了，得到的結(jié)果就是錯(cuò)誤的。

在鏈表的 index(0-based)位置添加元素 e

通過(guò)索引來(lái)操作鏈表，在鏈表中不是一個(gè)常用的操作，

因?yàn)樵谶x擇使用鏈表的時(shí)候通常就選擇不使用索引了，

但是這個(gè)需求在面試等一些考題中出現(xiàn)的概率很大，

所以他的主要作用更多的是一個(gè)練習(xí)。

學(xué)習(xí)方式

如果剛接觸鏈表，對(duì)鏈表不熟悉，

然后很多這種操作在腦子里不能非常快的反應(yīng)出來(lái)，

不清楚他的意義是什么，那你可以使用紙筆來(lái)稍微畫(huà)一下，

每一步程序邏輯的執(zhí)行意味著當(dāng)前這個(gè)鏈表變成了什么樣子，

這個(gè)過(guò)程能夠幫助你更加深入的理解程序，

包括在調(diào)試的時(shí)候來(lái)看你的程序到底為什么出了錯(cuò)誤時(shí)，

非常非常有幫助的，不要犯懶，為了更加深入的理解你的程序，

不能只盯著你的代碼去想，一定要寫(xiě)寫(xiě)畫(huà)畫(huà)，

必要的時(shí)候甚至根據(jù)你的程序進(jìn)行具體的調(diào)試，

這些都是非常重要非常有幫助的。

代碼示例 (class: MyLinkedList)

MyLinkedList

   public class MyLinkedList {

         // 隱藏內(nèi)部實(shí)現(xiàn)，不需要讓用戶(hù)知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node head;
         private int size;

         public MyLinkedList () {
               head = null;
               size = 0;
         }

         // ...
         // 其它的構(gòu)造函數(shù)，例如傳進(jìn)來(lái)一個(gè)數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表

         // 獲取鏈表中元素的個(gè)數(shù)
         public int getSize () {
               return size;
         }

         // 返回當(dāng)前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個(gè)元素 e
         public void addFirst (E e) {
   //        寫(xiě)法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫(xiě)法二
   //        Node node = new Node(e);
   //        node.next = head;
   //        head = node;

   //        寫(xiě)法三
               head = new Node(e, head);
               size ++;
         }

         // 在鏈表指定索引出插入一個(gè)元素
         public void insert (int index, E e) {

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("add error. index < 0 or index > size");
               }
               if (index == 0) {
                     addFirst(e);
               }else {
                     // 第一個(gè)prev就是head
                     Node prev = head;
   //            不斷的搜索 一直通過(guò)next來(lái)進(jìn)行檢索
                     for (int i = 0; i < index - 1 ; i++) {
                           prev = prev.next;
                     }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
                     prev.next = new Node(e, prev.next);
                     size ++;

               }
         }

         // 在鏈表尾部添加一個(gè)元素
         public void addLast (E e) {

               insert(size, e);
         }
   }

給鏈表設(shè)立虛擬頭節(jié)點(diǎn)

在鏈表中進(jìn)行指定索引處插入元素時(shí)

對(duì)鏈表頭插入元素與對(duì)鏈表其它位置插入元素的邏輯有區(qū)別，

所以就導(dǎo)致每次操作都需要對(duì)索引進(jìn)行判斷，

如果你是在索引 0 的位置插入元素，那么就沒(méi)有 prev(前一個(gè)元素),

自然就不可以使用node.next = prev.next和prev.next = node了，

那時(shí)候你可以直接使用node.next = head和head = node，

不過(guò)已經(jīng)有了向鏈表頭添加元素的方法了，

所以向頭部插入元素時(shí)根本就不需要這么做，

這時(shí)候可以通過(guò)給鏈表設(shè)立虛擬頭節(jié)點(diǎn)來(lái)解決這個(gè)問(wèn)題。

為什么對(duì)鏈表頭插入元素那么特殊？

因?yàn)椴迦朐貢r(shí)，必需要找到該索引位置的節(jié)點(diǎn)之前的一個(gè)節(jié)點(diǎn)(prev)，

而鏈表頭(head)之前并沒(méi)有任何節(jié)點(diǎn)，所以邏輯上就會(huì)特殊一些。

不過(guò)在鏈表的具體實(shí)現(xiàn)中有一個(gè)非常常用的技巧，

可以把鏈表頭的這種特殊的操作與其它的操作一起統(tǒng)一起來(lái)，

其實(shí)這個(gè)方法的想法很簡(jiǎn)單，既然它沒(méi)有鏈表頭之前的節(jié)點(diǎn)，

那就自己造一個(gè)鏈表頭之前的節(jié)點(diǎn)，

這個(gè)鏈表頭之前的節(jié)點(diǎn)不會(huì)用來(lái)存儲(chǔ)任何元素，存儲(chǔ)的數(shù)據(jù)為空，

這個(gè)空節(jié)點(diǎn)就稱(chēng)之為整個(gè)鏈表頭的 head，也可以叫它 dummyHead，

因?yàn)樗褪且粋€(gè)假的 head，它也是為鏈表設(shè)立的虛擬頭節(jié)點(diǎn)，

這樣一來(lái) 鏈表的第一個(gè)元素就是 dummyHead 的 next 所對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)，

因?yàn)?dummyHead 這個(gè)位置的元素是根本不存在的，

對(duì)用戶(hù)來(lái)講也是根本沒(méi)有意義的，

這只是為了編寫(xiě)邏輯方便而出現(xiàn)的一個(gè)虛擬的頭節(jié)點(diǎn)，

所以一個(gè)這樣的內(nèi)部機(jī)制對(duì)用戶(hù)來(lái)說(shuō)也是不可見(jiàn)的，

用戶(hù)不知道鏈表中有沒(méi)有虛擬的頭節(jié)點(diǎn)，

這和自定義的循環(huán)隊(duì)列有點(diǎn)像，自定義循環(huán)隊(duì)列中有一個(gè)不可用的空間，

有意識(shí)地去浪費(fèi)一個(gè)空間，為了編寫(xiě)邏輯更加的方便，

從而也讓性能在整體上得到了提升。

有了 dummyHead 之后就不需要處理頭節(jié)點(diǎn)這個(gè)特殊的操作

因?yàn)楫?dāng)你在頭部插入元素時(shí)，可以這樣

node.next = dummyHead.next、dummyHead.next = node ，

這樣你就解決了每次插入時(shí)都要進(jìn)行一次邏輯判斷了，

這樣一來(lái)就說(shuō)明了鏈表中所有的節(jié)點(diǎn)都有前一個(gè)節(jié)點(diǎn)了，

在初始的時(shí)候 dummyHead 指向的是索引為 0 的元素前一個(gè)位置的節(jié)點(diǎn)。

鏈表操作的實(shí)際原理

在沒(méi)有使用虛擬頭節(jié)點(diǎn)之前，一直都是在鏈表頭 head 這個(gè)地方不停的添加節(jié)點(diǎn)，

然后將 head 這個(gè)變量不停的指向新添加的節(jié)點(diǎn) node.next = head.next;head = node;。

在使用了虛擬頭節(jié)點(diǎn)之后，

一直是在鏈表虛擬頭 dummyHead 這個(gè)地方后面一個(gè)位置不停的插入新節(jié)點(diǎn)，

dummyHead 從未變動(dòng)過(guò)，永遠(yuǎn)在鏈表的第一個(gè)位置，

node.next = dummyHead.next; dummyHead.next = node;，

但是dummyHead.next才是鏈表中第一個(gè)實(shí)際記錄的節(jié)點(diǎn)，

用戶(hù)會(huì)不知道虛擬節(jié)點(diǎn)的存在，因?yàn)?dummyHead 并不算在鏈表的實(shí)際節(jié)點(diǎn)中，

也就是 size 中不會(huì)維護(hù) dummyHead，dummyHead 的存在是為了維護(hù)一致的插入操作。

代碼示例 (class: MyLinkedList)

MyLinkedList

   public class MyLinkedList {

         // 隱藏內(nèi)部實(shí)現(xiàn)，不需要讓用戶(hù)知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構(gòu)造函數(shù)，例如傳進(jìn)來(lái)一個(gè)數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表

         // 獲取鏈表中元素的個(gè)數(shù)
         public int getSize () {
               return size;
         }

         // 返回當(dāng)前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個(gè)元素 e
         public void addFirst (E e) {
   //        寫(xiě)法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫(xiě)法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫(xiě)法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫(xiě)法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個(gè)元素
         public void insert (int index, E e) {

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("add error. index < 0 or index > size");
               }

               // 第一個(gè)prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過(guò)next來(lái)進(jìn)行檢索
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個(gè)元素
         public void addLast (E e) {

               insert(size, e);
         }
   }

在鏈表中進(jìn)行遍歷、查詢(xún)、修改操作

如果要找指定索引元素的前一個(gè)節(jié)點(diǎn)

那么就要從dummyHead開(kāi)始遍歷，

如果要找指定索引元素的那個(gè)節(jié)點(diǎn)，

那么就要從dummyHead.next開(kāi)始遍歷。

代碼示例(class: MyLinkedList, class: Main)

MyLinkedList

   public class MyLinkedList {

         // 隱藏內(nèi)部實(shí)現(xiàn)，不需要讓用戶(hù)知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構(gòu)造函數(shù)，例如傳進(jìn)來(lái)一個(gè)數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表

         // 獲取鏈表中元素的個(gè)數(shù)
         public int getSize () {
               return size;
         }

         // 返回當(dāng)前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個(gè)元素 e
         public void addFirst (E e) {
   //        寫(xiě)法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫(xiě)法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫(xiě)法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫(xiě)法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個(gè)元素
         public void insert (int index, E e) {

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("add or insert error. index < 0 or index > size");
               }

               // 第一個(gè)prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過(guò)next來(lái)進(jìn)行檢索，找指定索引的節(jié)點(diǎn)的前一個(gè)元素
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個(gè)元素
         public void addLast (E e) {

               insert(size, e);
         }

         // get
         public E get (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size");
               }

               Node cur = dummyHead.next;
               for (int i = 0; i < index ; i++) {
                     cur = cur.next;
               }

               return cur.e;
         }

         // getFirst
         public E getFirst () {
               return get(0);
         }

         // getLast
         public E getLast () {
               return get(size - 1);
         }

         // set
         public void set (int index, E e) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("set error. index < 0 or index >= size");
               }

               Node node = dummyHead.next;
               for (int i = 0; i < index; i++) {
                     node = node.next;
               }
               node.e = e;
         }

         // contains
         public boolean contains (E e) {

   //        第一種方式
   //        Node node = dummyHead;
   //        for (int i = 0; i < size - 1 ; i++) {
   //            node = node.next;
   //
   //            if (node.e.equals(e)) {
   //                return true;
   //            }
   //        }

   //        第二種方式
               Node node = dummyHead.next;
               while (node != null) {
                     if (node.e.equals(e)) {
                           return true;
                     } else {
                           node = node.next;
                     }
               }
               return  false;
         }

         @Override
         public String toString () {

               StringBuilder sb = new StringBuilder();
               sb.append("鏈表長(zhǎng)度：" + size + "，鏈表信息：");
   //        // 寫(xiě)法一
   //        Node node = dummyHead.next;
   //        while (node != null) {
   //            sb.append(node + "->");
   //            node = node.next;
   //        }
   //        寫(xiě)法二
               for (Node node = dummyHead.next; node != null ; node = node.next) {
                     sb.append(node + "->");
               }

               sb.append("NULL");
               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
               MyLinkedList mkl = new MyLinkedList();

               for (int i = 1; i <= 5 ; i++) {
                     mkl.addFirst(i);
                     System.out.println(mkl);
               }
               mkl.insert(2, 88888);
               System.out.println(mkl);
         }
   }

在鏈表中進(jìn)行刪除操作

鏈表元素的刪除

假設(shè)要?jiǎng)h除索引為 2 位置的元素

就是要索引為 2 位置的元素的前一個(gè)元素，

還要索引為 2 位置的元素的后一個(gè)元素，

讓前一個(gè)元素的 next 等于后一個(gè)元素，

也就是前一個(gè)元素的 next 等于索引為 2 的元素的 next。

也就是讓 prev 指向待刪除的那個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，

prev 這個(gè)節(jié)點(diǎn)的 next 就是要?jiǎng)h除的那個(gè)節(jié)點(diǎn) delNode，

然后讓prev.next = delNode.next，

這樣就讓待刪除的那個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的 next，

也就是直接指向了待刪除的那個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)了，

然后讓delNode.next = null 就完成了刪除，

千萬(wàn)不要這樣delNode = delNode.next，

這個(gè)并不是刪除，而是將待刪除節(jié)點(diǎn)的引用指向了下一個(gè)節(jié)點(diǎn)，

通過(guò)設(shè)置為 null 才是真正的與當(dāng)前鏈表脫離關(guān)系。

代碼示例(class: MyLinkedList, class: Main)

MyLinkedList

   public class MyLinkedList {

         // 隱藏內(nèi)部實(shí)現(xiàn)，不需要讓用戶(hù)知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構(gòu)造函數(shù)，例如傳進(jìn)來(lái)一個(gè)數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表

         // 獲取鏈表中元素的個(gè)數(shù)
         public int getSize () {
               return size;
         }

         // 返回當(dāng)前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個(gè)元素 e
         public void addFirst (E e) {
   //        寫(xiě)法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫(xiě)法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫(xiě)法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫(xiě)法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個(gè)元素
         public void insert (int index, E e) {

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("add or insert error. index < 0 or index > size");
               }

               // 第一個(gè)prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過(guò)next來(lái)進(jìn)行檢索，找指定索引的節(jié)點(diǎn)的前一個(gè)元素
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個(gè)元素
         public void addLast (E e) {

               insert(size, e);
         }

         // get
         public E get (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size");
               }

               Node cur = dummyHead.next;
               for (int i = 0; i < index ; i++) {
                     cur = cur.next;
               }

               return cur.e;
         }

         // getFirst
         public E getFirst () {
               return get(0);
         }

         // getLast
         public E getLast () {
               return get(size - 1);
         }

         // set
         public void set (int index, E e) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("set error. index < 0 or index >= size");
               }

               Node node = dummyHead.next;
               for (int i = 0; i < index; i++) {
                     node = node.next;
               }
               node.e = e;
         }

         // contains
         public boolean contains (E e) {

   //        第一種方式
   //        Node node = dummyHead;
   //        for (int i = 0; i < size - 1 ; i++) {
   //            node = node.next;
   //
   //            if (node.e.equals(e)) {
   //                return true;
   //            }
   //        }

   //        第二種方式
               Node node = dummyHead.next;
               while (node != null) {
                     if (node.e.equals(e)) {
                           return true;
                     } else {
                           node = node.next;
                     }
               }
               return  false;
         }

         // remove
         public E remove (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("remove error. index < 0 or index >= size");
               }

               Node prev = dummyHead;
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
               Node delNode = prev.next;
               prev.next = delNode.next;
               size --;

               E e = delNode.e;
               delNode.next = null;

               return e;
         }

         // removeFirst
         public E removeFirst () {
             return remove(0);
         }

         // removeLast
         public E removeLast () {
               return remove(size - 1);
         }

         @Override
         public String toString () {

               StringBuilder sb = new StringBuilder();
               sb.append("鏈表長(zhǎng)度：" + size + "，鏈表信息：");
   //        // 寫(xiě)法一
   //        Node node = dummyHead.next;
   //        while (node != null) {
   //            sb.append(node + "->");
   //            node = node.next;
   //        }
   //        寫(xiě)法二
               for (Node node = dummyHead.next; node != null ; node = node.next) {
                     sb.append(node + "->");
               }

               sb.append("NULL");
               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
               MyLinkedList mkl = new MyLinkedList();

               for (int i = 1; i <= 5 ; i++) {
                     mkl.addFirst(i);
                     System.out.println(mkl);
               }
               mkl.insert(2, 88888);
               System.out.println(mkl);

               mkl.remove(2);
               System.out.println(mkl);

               mkl.removeFirst();
               System.out.println(mkl);

               mkl.removeLast();
               System.out.println(mkl);
         }
   }

鏈表的時(shí)間復(fù)雜度分析

增：O(n)：在只對(duì)鏈表頭進(jìn)行操作時(shí)為O(1)

刪：O(n)：在只對(duì)鏈表頭進(jìn)行操作時(shí)為O(1)

改：O(n)

查：O(n)：只查鏈表頭的元素時(shí)為O(1)

鏈表增刪改查的時(shí)間復(fù)雜度

整體上要比數(shù)組增刪改查的時(shí)間復(fù)雜度要差，

因?yàn)閿?shù)組有一個(gè)優(yōu)勢(shì)，

你有索引的話你就可以快速訪問(wèn)，

而鏈表沒(méi)有這樣的優(yōu)勢(shì)

但是鏈表的優(yōu)勢(shì)是，

如果你只對(duì)鏈表頭進(jìn)行增刪的操作，

那么它的時(shí)間復(fù)雜度是 O(1)級(jí)別的，

而且它整體是動(dòng)態(tài)的，所以不會(huì)大量的浪費(fèi)內(nèi)存空間。 6.鏈表適合做的事情

不去修改、也不去查任意的元素，

就算查，也只能查鏈表頭的元素，

查的時(shí)候，只有那樣才是 O(1)級(jí)別的時(shí)間復(fù)雜度，

并且增加刪除的時(shí)候只對(duì)鏈表頭進(jìn)行操作，

只有在這種時(shí)候才會(huì)和數(shù)組整體的時(shí)間復(fù)雜度是一樣的，

不過(guò)鏈表整體是動(dòng)態(tài)的，不會(huì)去大量的浪費(fèi)內(nèi)存空間，

所以它具有一定的優(yōu)勢(shì)。

鏈表還有諸多的改進(jìn)的方式

所以應(yīng)用鏈表在一些情況下仍然是有它的優(yōu)勢(shì)的，

最最重要的是鏈表本身是一種最最基礎(chǔ)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，

對(duì)這種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)要深刻的理解和掌握，

對(duì)于學(xué)習(xí)更重要的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)是有巨大的幫助，

比如說(shuō)二叉樹(shù)、平衡二叉樹(shù)、AVL、紅黑樹(shù)等等。

　添加操作 O(n)

addLast(e)：O(n)

會(huì)從頭遍歷到尾，

找到最后一個(gè)節(jié)點(diǎn)之后才能添加元素

addFirst(e)：O(1)

直接從頭部添加元素

insert(index, e)：O(n/2) = O(n)