資訊專欄INFORMATION COLUMN
摘要：鏈表鏈表是最基礎(chǔ)的動態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表是非常重要的線性數(shù)據(jù)結(jié)構(gòu)以下三種，底層都是依托靜態(tài)數(shù)組，靠解決固定容量問題。要清楚什么時候使用數(shù)組這樣的靜態(tài)數(shù)據(jù)結(jié)構(gòu)，什么時候使用鏈表這類的動態(tài)數(shù)據(jù)結(jié)構(gòu)。
前言
【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文章大概的內(nèi)容如下：
Arrays(數(shù)組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優(yōu)先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)
源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)
全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。
本文章適合 對數(shù)據(jù)結(jié)構(gòu)想了解并且感興趣的人群，文章風(fēng)格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人或者正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人群有幫助。
鏈表 Linked List鏈表是最基礎(chǔ)的動態(tài)數(shù)據(jù)結(jié)構(gòu)
鏈表是非常重要的線性數(shù)據(jù)結(jié)構(gòu)
以下三種，底層都是依托靜態(tài)數(shù)組，靠 resize 解決固定容量問題。
動態(tài)數(shù)組：所謂動態(tài)，是從用戶的角度上來看的。
棧
隊列
鏈表是真正的動態(tài)數(shù)據(jù)結(jié)構(gòu)
它是數(shù)據(jù)結(jié)構(gòu)中的一個重點，
也有可能是一個難點，
它是最簡單的一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，
其它更高級的動態(tài)數(shù)據(jù)結(jié)構(gòu)有 二分搜索樹、Trie、
平衡二叉樹、AVL、紅黑樹等等，
熟悉了最簡單的動態(tài)數(shù)據(jù)結(jié)構(gòu)，
那么對于更高級的也會比較容易掌握了。
對于鏈表來說它涉及到了計算機領(lǐng)域一個非常重要的概念
更深入的理解引用（或者指針），
這個概念和內(nèi)存相關(guān)，
在 java 里面不需要手動的管理內(nèi)存，
但是對鏈表這種數(shù)據(jù)結(jié)構(gòu)更加深入的理解，
可以讓你對 引用、指針甚至計算機系統(tǒng)中
和內(nèi)存管理相關(guān)很多話題有更加深入的認(rèn)識。
鏈表本身也是有它非常清晰的遞歸結(jié)構(gòu)的，
只不過由于鏈表這種數(shù)據(jù)結(jié)構(gòu)它本身是一種線性的數(shù)據(jù)結(jié)構(gòu)，
所以依然可以非常容易的使用循環(huán)的方式來對鏈表進行操作，
但是鏈表本身由于它天生也是具有這種遞歸結(jié)構(gòu)的性質(zhì)，
所以它也能讓你更加深入的理解遞歸機制相應(yīng)的這種數(shù)據(jù)結(jié)構(gòu)，
在學(xué)習(xí)更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的時候，
對遞歸這種邏輯機制深入的理解是必不可缺的。
鏈表這種數(shù)據(jù)結(jié)構(gòu)本身就具有功能性
它可以用來組成更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，
比如 圖結(jié)構(gòu)、hash 表、棧(鏈表版)、隊列(鏈表版)，
所以他可以輔助組成其它數(shù)據(jù)結(jié)構(gòu)。
什么是鏈表
數(shù)據(jù)存儲在“節(jié)點”（Node）中
把數(shù)據(jù)存在一種多帶帶的結(jié)構(gòu)中，
這個結(jié)構(gòu)通常管它叫做節(jié)點，
對于鏈表節(jié)點來說他通常只有兩部分，
一部分就是存儲真正的數(shù)據(jù)，
另一部分存儲的是當(dāng)前節(jié)點的下一個節(jié)點，
鏈表其實就像一個火車，每一個節(jié)點都是一節(jié)車廂，
在車廂中存儲數(shù)據(jù)，而車廂和車廂之間還會進行連接，
以使得這些數(shù)據(jù)是整合在一起的，
這樣用戶可以方便的在所有的這些數(shù)據(jù)上進行查詢等等其它的操作，
數(shù)據(jù)與數(shù)據(jù)之間連接就是用下面的這個 next 來完成的
class Node {
E e;
Node next;
}
鏈表的優(yōu)點
真正的動態(tài)，不需要處理固定容量的問題，
它不像靜態(tài)數(shù)組那樣一下子 new 出來一片空間，
也根本不需要考慮這個空間是不是不夠用，
也根本不用去考慮這個空間是不是開多了。
對于鏈表來說，你需要多少個數(shù)據(jù)。
你就可以生成多少個節(jié)點，
把它們掛接起來了，這就是所謂的動態(tài)。
鏈表的缺點
和數(shù)組相比，它喪失了隨機訪問的能力。
不能像數(shù)組那樣給一個索引
就能直接訪問對應(yīng)索引位置的元素，
這是因為從底層機制上數(shù)組所開辟的空間
在內(nèi)存里是連續(xù)分布的，
所以才能夠直接去向索引對應(yīng)的偏移
計算出相應(yīng)的數(shù)據(jù)所存儲的內(nèi)存地址，
然后就能夠直接用O(1)的復(fù)雜度取出這個元素，
但是鏈表不同，鏈表由于是靠 next 一層一層連接的，
所以在計算機的底層，每一個節(jié)點他所在的內(nèi)存的位置是不同的，
只能夠靠這個 next 來一層一層的找到這個元素，
這就是鏈表最大的缺點。
數(shù)組和鏈表的對比
數(shù)組
數(shù)組最好永遠(yuǎn)索引有語意的情況，如 scores[2]
最大的優(yōu)點：支持快速查詢
鏈表
鏈表不適合用于索引有語意的情況。
最大的優(yōu)點：動態(tài)存儲。
對比
數(shù)組也可以沒有語意，并不是所有的時候索引是有語意的，
也并不是所有有語意的這樣的一個標(biāo)志就適合做索引，如身份證號，
將一個靜態(tài)數(shù)組改變?yōu)橐粋€動態(tài)數(shù)組，
就是在應(yīng)付不方便使用索引的時候有關(guān)數(shù)據(jù)存儲的問題，
對于這樣的存儲數(shù)據(jù)的需求使用鏈表是更合適的，
因為鏈表最大的優(yōu)點是動態(tài)存儲。
要清楚什么時候使用數(shù)組這樣的靜態(tài)數(shù)據(jù)結(jié)構(gòu)，
什么時候使用鏈表這類的動態(tài)數(shù)據(jù)結(jié)構(gòu)。
簡單的代碼示例MyLinkedList
public class MyLinkedList在鏈表中進行添加、插入操作{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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(); } } }
鏈表是通過節(jié)點來裝載元素
并且節(jié)點和節(jié)點之間會進行連接。
如果想訪問這條鏈表中所有的節(jié)點，
那么就必須把鏈表的頭給存儲起來，
通常這個鏈表的頭叫做的 head，
應(yīng)該說在MyLinkedList中
應(yīng)該有一個變量指向鏈表中的第一個節(jié)點。
給自定義數(shù)組添加元素是從數(shù)組尾部開始添加，
給鏈表添加元素是從數(shù)組頭部開始添加，
因為自定義數(shù)組有維護一個 size，
這個 size 指向的是下一個待添加元素的位置，
所以你直接將 size 做索引直接賦值即可，
有 size 這個變量在跟蹤數(shù)組的尾巴，
而對于鏈表來說 有設(shè)置一個鏈表的頭這樣的一個變量，
也就是說有一個變量在跟蹤鏈表的頭，
并沒有一個變量去跟蹤鏈表的尾巴，
所以在鏈表頭部添加元素是非常方便。
添加操作原理
將一個新的元素掛接到鏈表頭部，
同時不破壞現(xiàn)在鏈表的這個結(jié)構(gòu)，
添加一個新元素 666，它的名字叫 node，
就只需要使用 node.next = head，
也就是將新添加的元素的 next 指向鏈表的頭，
這個時候新添加的元素也成為新的鏈表頭，
也就是head = node，
這樣 head 就會指向新的元素 666，也就是 node 這個節(jié)點，
如此一來就完成了將 node 這個節(jié)點插入了整個鏈表的頭部，
node 這個變量是在一個函數(shù)中聲明的，
所以函數(shù)結(jié)束之后這個變量的作用域也就結(jié)束了，
鏈表的 head 也等于 node，
鏈表中就新增了一個新元素。
在鏈表頭部添加元素非常簡單，
只需要創(chuàng)建節(jié)點，讓節(jié)點的 next 指向 head，
然后讓 head 重新指向這個節(jié)點，也就是讓 head 變成新的元素，
因為鏈表是從頭部添加元素的。
在鏈表中間添加元素，
定義一個 prev 的變量指向中間元素的前一個元素，
然后讓新增加的元素這樣，node.next = prev.next，
之后這樣，prev.next = node，
這樣一來就在 prev 這個元素和原本 prev 的下一個元素之間
插入了一個新元素，叫做 node，
整個過程就是將 prev 的 next(下一個元素)的引用
傳遞給新元素的 next(下一個元素)，
然后將 prev 的 next(下一個元素)變更為這個新元素，
最后就將新元素插入到中間了。
這個過程的關(guān)鍵是找到待添加的節(jié)點的前一個節(jié)點，
這個就是 prev 變量要做的事情。
在鏈表的操作中很多時候順序非常重要，
如在鏈表中插入一個元素，在指定的元素后面插入一個元素，
并且不影響整個鏈表結(jié)構(gòu)，和在鏈表中間添加元素一樣，
把原本的node.next = prev.next和prev.next = node
的順序變一下，prev.next = node在前，
node.next = prev.next 在后，這樣一來邏輯就不成立了，
鏈表不僅斷開了，而且新節(jié)點的 next 指向的是自己，死循環(huán)了，
所以一樣的代碼，順序顛倒了，得到的結(jié)果就是錯誤的。
在鏈表的 index(0-based)位置添加元素 e
通過索引來操作鏈表，在鏈表中不是一個常用的操作，
因為在選擇使用鏈表的時候通常就選擇不使用索引了，
但是這個需求在面試等一些考題中出現(xiàn)的概率很大，
所以他的主要作用更多的是一個練習(xí)。
學(xué)習(xí)方式
如果剛接觸鏈表，對鏈表不熟悉，
然后很多這種操作在腦子里不能非?？斓姆磻?yīng)出來，
不清楚他的意義是什么，那你可以使用紙筆來稍微畫一下，
每一步程序邏輯的執(zhí)行意味著當(dāng)前這個鏈表變成了什么樣子，
這個過程能夠幫助你更加深入的理解程序，
包括在調(diào)試的時候來看你的程序到底為什么出了錯誤時，
非常非常有幫助的，不要犯懶，為了更加深入的理解你的程序，
不能只盯著你的代碼去想，一定要寫寫畫畫，
必要的時候甚至根據(jù)你的程序進行具體的調(diào)試，
這些都是非常重要非常有幫助的。
代碼示例 (class: MyLinkedList)
MyLinkedList
public class MyLinkedList給鏈表設(shè)立虛擬頭節(jié)點{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = head; // head = node; // 寫法三 head = new Node(e, head); size ++; } // 在鏈表指定索引出插入一個元素 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 { // 第一個prev就是head Node prev = head; // 不斷的搜索 一直通過next來進行檢索 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 ++; } } // 在鏈表尾部添加一個元素 public void addLast (E e) { insert(size, e); } }
在鏈表中進行指定索引處插入元素時
對鏈表頭插入元素與對鏈表其它位置插入元素的邏輯有區(qū)別，
所以就導(dǎo)致每次操作都需要對索引進行判斷，
如果你是在索引 0 的位置插入元素，那么就沒有 prev(前一個元素),
自然就不可以使用node.next = prev.next和prev.next = node了，
那時候你可以直接使用node.next = head和head = node，
不過已經(jīng)有了向鏈表頭添加元素的方法了，
所以向頭部插入元素時根本就不需要這么做，
這時候可以通過給鏈表設(shè)立虛擬頭節(jié)點來解決這個問題。
為什么對鏈表頭插入元素那么特殊？
因為插入元素時，必需要找到該索引位置的節(jié)點之前的一個節(jié)點(prev)，
而鏈表頭(head)之前并沒有任何節(jié)點，所以邏輯上就會特殊一些。
不過在鏈表的具體實現(xiàn)中有一個非常常用的技巧，
可以把鏈表頭的這種特殊的操作與其它的操作一起統(tǒng)一起來，
其實這個方法的想法很簡單，既然它沒有鏈表頭之前的節(jié)點，
那就自己造一個鏈表頭之前的節(jié)點，
這個鏈表頭之前的節(jié)點不會用來存儲任何元素，存儲的數(shù)據(jù)為空，
這個空節(jié)點就稱之為整個鏈表頭的 head，也可以叫它 dummyHead，
因為它就是一個假的 head，它也是為鏈表設(shè)立的虛擬頭節(jié)點，
這樣一來 鏈表的第一個元素就是 dummyHead 的 next 所對應(yīng)的那個節(jié)點，
因為 dummyHead 這個位置的元素是根本不存在的，
對用戶來講也是根本沒有意義的，
這只是為了編寫邏輯方便而出現(xiàn)的一個虛擬的頭節(jié)點，
所以一個這樣的內(nèi)部機制對用戶來說也是不可見的，
用戶不知道鏈表中有沒有虛擬的頭節(jié)點，
這和自定義的循環(huán)隊列有點像，自定義循環(huán)隊列中有一個不可用的空間，
有意識地去浪費一個空間，為了編寫邏輯更加的方便，
從而也讓性能在整體上得到了提升。
有了 dummyHead 之后就不需要處理頭節(jié)點這個特殊的操作
因為當(dāng)你在頭部插入元素時，可以這樣
node.next = dummyHead.next、dummyHead.next = node ，
這樣你就解決了每次插入時都要進行一次邏輯判斷了，
這樣一來就說明了鏈表中所有的節(jié)點都有前一個節(jié)點了，
在初始的時候 dummyHead 指向的是索引為 0 的元素前一個位置的節(jié)點。
鏈表操作的實際原理
在沒有使用虛擬頭節(jié)點之前，一直都是在鏈表頭 head 這個地方不停的添加節(jié)點，
然后將 head 這個變量不停的指向新添加的節(jié)點 node.next = head.next;head = node;。
在使用了虛擬頭節(jié)點之后，
一直是在鏈表虛擬頭 dummyHead 這個地方后面一個位置不停的插入新節(jié)點，
dummyHead 從未變動過，永遠(yuǎn)在鏈表的第一個位置，
node.next = dummyHead.next; dummyHead.next = node;，
但是dummyHead.next才是鏈表中第一個實際記錄的節(jié)點，
用戶會不知道虛擬節(jié)點的存在，因為 dummyHead 并不算在鏈表的實際節(jié)點中，
也就是 size 中不會維護 dummyHead，dummyHead 的存在是為了維護一致的插入操作。
代碼示例 (class: MyLinkedList)
MyLinkedList
public class MyLinkedList在鏈表中進行遍歷、查詢、修改操作{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 寫法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 寫法四 insert(0, e); } // 在鏈表指定索引出插入一個元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add error. index < 0 or index > size"); } // 第一個prev就是dummyHead Node prev = dummyHead; // 不斷的搜索 一直通過next來進行檢索 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 ++; } // 在鏈表尾部添加一個元素 public void addLast (E e) { insert(size, e); } }
如果要找指定索引元素的前一個節(jié)點
那么就要從dummyHead開始遍歷，
如果要找指定索引元素的那個節(jié)點，
那么就要從dummyHead.next開始遍歷。
代碼示例(class: MyLinkedList, class: Main)
MyLinkedList
public class MyLinkedList{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 寫法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 寫法四 insert(0, e); } // 在鏈表指定索引出插入一個元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一個prev就是dummyHead Node prev = dummyHead; // 不斷的搜索 一直通過next來進行檢索，找指定索引的節(jié)點的前一個元素 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 ++; } // 在鏈表尾部添加一個元素 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("鏈表長度：" + size + "，鏈表信息："); // // 寫法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 寫法二 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);
}
}
在鏈表中進行刪除操作
鏈表元素的刪除
假設(shè)要刪除索引為 2 位置的元素
就是要索引為 2 位置的元素的前一個元素，
還要索引為 2 位置的元素的后一個元素，
讓前一個元素的 next 等于后一個元素，
也就是前一個元素的 next 等于索引為 2 的元素的 next。
也就是讓 prev 指向待刪除的那個節(jié)點的前一個節(jié)點，
prev 這個節(jié)點的 next 就是要刪除的那個節(jié)點 delNode，
然后讓prev.next = delNode.next，
這樣就讓待刪除的那個節(jié)點的前一個節(jié)點的 next，
也就是直接指向了待刪除的那個節(jié)點的后一個節(jié)點了，
然后讓delNode.next = null 就完成了刪除，
千萬不要這樣delNode = delNode.next，
這個并不是刪除，而是將待刪除節(jié)點的引用指向了下一個節(jié)點，
通過設(shè)置為 null 才是真正的與當(dāng)前鏈表脫離關(guān)系。
代碼示例(class: MyLinkedList, class: Main)
MyLinkedList
public class MyLinkedList{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 寫法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 寫法四 insert(0, e); } // 在鏈表指定索引出插入一個元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一個prev就是dummyHead Node prev = dummyHead; // 不斷的搜索 一直通過next來進行檢索，找指定索引的節(jié)點的前一個元素 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 ++; } // 在鏈表尾部添加一個元素 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("鏈表長度：" + size + "，鏈表信息："); // // 寫法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 寫法二 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);
}
}
鏈表的時間復(fù)雜度分析
增：O(n)：在只對鏈表頭進行操作時為O(1)
刪：O(n)：在只對鏈表頭進行操作時為O(1)
改：O(n)
查：O(n)：只查鏈表頭的元素時為O(1)
鏈表增刪改查的時間復(fù)雜度
整體上要比數(shù)組增刪改查的時間復(fù)雜度要差，
因為數(shù)組有一個優(yōu)勢，
你有索引的話你就可以快速訪問，
而鏈表沒有這樣的優(yōu)勢
但是鏈表的優(yōu)勢是，
如果你只對鏈表頭進行增刪的操作，
那么它的時間復(fù)雜度是 O(1)級別的，
而且它整體是動態(tài)的，所以不會大量的浪費內(nèi)存空間。 6.鏈表適合做的事情
不去修改、也不去查任意的元素，
就算查，也只能查鏈表頭的元素，
查的時候，只有那樣才是 O(1)級別的時間復(fù)雜度，
并且增加刪除的時候只對鏈表頭進行操作，
只有在這種時候才會和數(shù)組整體的時間復(fù)雜度是一樣的，
不過鏈表整體是動態(tài)的，不會去大量的浪費內(nèi)存空間，
所以它具有一定的優(yōu)勢。
鏈表還有諸多的改進的方式
所以應(yīng)用鏈表在一些情況下仍然是有它的優(yōu)勢的，
最最重要的是 鏈表本身是一種最最基礎(chǔ)的動態(tài)數(shù)據(jù)結(jié)構(gòu)，
對這種動態(tài)數(shù)據(jù)結(jié)構(gòu)要深刻的理解和掌握，
對于學(xué)習(xí)更重要的動態(tài)數(shù)據(jù)結(jié)構(gòu)是有巨大的幫助，
比如說二叉樹、平衡二叉樹、AVL、紅黑樹等等。
添加操作 O(n)
addLast(e)：O(n)
會從頭遍歷到尾，
找到最后一個節(jié)點之后才能添加元素
addFirst(e)：O(1)
直接從頭部添加元素
insert(index, e)：O(n/2) = O(n)
會去遍歷鏈表中每一個節(jié)點，
檢索到合適的位置才會添加這個元素。
刪除操作 O(n)
removeLast()：O(n)
會去遍歷鏈表中每一個節(jié)點，
找到最后一個節(jié)點后才會刪除
removeFirst()：O(1)
直接從頭部刪除這個節(jié)點
remove(index)：O(n/2) = O(n)
會去遍歷鏈表中每一個節(jié)點，
檢索到合適的位置才會移除這個元素
修改操作 O(n)
set(index, e)：O(n)
會去遍歷鏈表中每一個節(jié)點，
找到了合適位置的節(jié)點后，
才會修改元素
查找操作 O(n)
get(index)：O(n)
會去遍歷鏈表中每一個節(jié)點，
找到了合適位置的節(jié)點后，
返回這個元素。
contains(e)：O(n)
會去遍歷鏈表中每一個節(jié)點，
返回 是否有相同元素的 bool 值。
find(e)：O(n)
這個方法對鏈表來說是沒有用的，
就算你拿到了那個索引你也不能快速訪問。
使用鏈表來實現(xiàn)棧
對鏈表進行添加操作時
時間復(fù)雜度為O(n)，
但是在只對鏈表頭進行操作時為O(1)
對鏈表進行刪除操作時
時間復(fù)雜度為O(n)，
但是在只對鏈表頭進行操作時為O(1)
對鏈表進行查詢操作時
時間復(fù)雜度為O(n)，
但是在只查鏈表頭的元素時為O(1)
這些特性很符合棧的需求
棧是后進先出的，并且棧只查棧頂?shù)脑兀?/p>
所以可以使用鏈表來實現(xiàn)棧這樣的數(shù)據(jù)結(jié)構(gòu)。
鏈表實現(xiàn)的棧
首先定義接口IMyLinkedListStack，
然后讓MyLinkedListStack來實現(xiàn)這些接口。
IMyLinkedListStack
void push(E e)：添加一個元素
E pop()：移除一個元素
E peek()：查看棧頂?shù)脑?/p>
int getSize()：獲取棧中實際的元素個數(shù)
boolean isEmpty()：判斷棧是否為空
代碼示例
(Interface: IMyLinkedListStack, class: MyLinkedList,
class: MyLinkedListStack, class: Main)
IMyLinkedListStack
public interface IMyLinkedListStack{ /** * @param e
*/
void push (E e);
/**
* @return e
* 出棧
*/
E pop ();
/**
* @return e
* 查看棧頂?shù)囊粋€元素
*/
E peek ();
/**
* @return size
* 查看棧中實際元素的個數(shù)
*/
int getSize ();
/**
* @return not empty
* 判斷棧中是否為空
*/
boolean isEmpty ();
}
3. `MyLinkedList`
public class MyLinkedList{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 寫法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 寫法四 insert(0, e); } // 在鏈表指定索引出插入一個元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一個prev就是dummyHead Node prev = dummyHead; // 不斷的搜索 一直通過next來進行檢索，找指定索引的節(jié)點的前一個元素 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 ++; } // 在鏈表尾部添加一個元素 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("鏈表長度：" + size + "，鏈表信息："); // // 寫法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 寫法二 for (Node node = dummyHead.next; node != null ; node = node.next) { sb.append(node + "->"); } sb.append("NULL"); return sb.toString(); } }
4. `MyLinkedListStack`
public class MyLinkedListStackimplements IMyLinkedListStack { private MyLinkedList mkl; public MyLinkedListStack () { mkl = new MyLinkedList (); } /** * @param e 入棧 */ @Override public void push (E e) { mkl.addFirst(e); } /** * @return e * 出棧 */ @Override public E pop () { return mkl.removefirst(); } /** * @return e * 查看棧頂?shù)囊粋€元素 */ @Override public E peek () { return mkl.getFirst(); } /** * @return size * 查看棧中實際元素的個數(shù) */ @Override public int getSize () { return mkl.getSize(); } /** * @return not empty * 判斷棧中是否為空 */ @Override public boolean isEmpty () { return mkl.isEmpty(); } @Override public String toString () { int size = getSize(); StringBuilder sb = new StringBuilder(); sb.append("MyLinkedlistStack: 元素個數(shù)=" + size); sb.append(", stack top=[ "); for (int i = 0; i < size ; i++) { sb.append(mkl.get(i)); sb.append("->"); } sb.append("NULL ]"); return sb.toString(); } }
5. `Main`
public class Main {
public static void main(String[] args) {
MyLinkedListStack mkls = new MyLinkedListStack();
for (int i = 1; i <= 5 ; i++) {
mkls.push(i);
System.out.println(mkls);
}
System.out.println(mkls.peek());
for (int i = 0; i < 5 ; i++) {
System.out.println(mkls);
mkls.pop();
}
}
}
## 自定義數(shù)組棧對比自定義鏈表棧 1. 自定義數(shù)組棧與自定義鏈表棧的性能相差很少 1. 但是隨著操作的次數(shù)增長，數(shù)組棧會慢慢強過鏈表棧， 2. 自定義鏈表棧中有太多的 new 操作， 3. new 操作在有一些系統(tǒng)上比較耗費性能的， 4. 因為它在不停的在內(nèi)存中尋找可以開辟空間的地方來進行開辟空間， 5. 自定義數(shù)組棧中有比較多的擴容操作， 6. 所以這個比較是相對比較復(fù)雜的， 7. 和你的語法、操作系統(tǒng)、編譯器、解釋器都有關(guān)系， 8. 不過他們的時間復(fù)雜度都是`O(1)`級別的， 9. 所以他們之間的性能差異無非就 1-2 倍這樣， 10. 在最極端的情況下 3-5 倍就已經(jīng)很難了， 11. 不會有幾百倍的巨大的差異，因為畢竟他們的時間復(fù)雜度一樣。 ### 代碼示例 1. `(Interface: IStack, class: MyLinkedList,` 1. `class: MyLinkedListStack, class: MyArray,` 2. `class: MyStack, class: Main)` 2. `IStack`
public interface IStack{ /** * @param e * 入棧 */ void push (E e); /** * @return e * 出棧 */ E pop (); /** * @return e * 查看棧頂?shù)囊粋€元素 */ E peek (); /** * @return size * 查看棧中實際元素的個數(shù) */ int getSize (); /** * @return not empty * 判斷棧中是否為空 */ boolean isEmpty (); }
3. `MyLinkedList`
public class MyLinkedList{ // 隱藏內(nèi)部實現(xiàn)，不需要讓用戶知道 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ù)，例如傳進來一個數(shù)組，將數(shù)組轉(zhuǎn)換為鏈表 // 獲取鏈表中元素的個數(shù) public int getSize () { return size; } // 返回當(dāng)前鏈表是否為空 public boolean isEmpty () { return size == 0; } // 在鏈表頭部添加一個元素 e public void addFirst (E e) { // 寫法一 // Node node = new Node(e, head); // head = node; // 寫法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 寫法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 寫法四 insert(0, e); } // 在鏈表指定索引出插入一個元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一個prev就是dummyHead Node prev = dummyHead; // 不斷的搜索 一直通過next來進行檢索，找指定索引的節(jié)點的前一個元素 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 ++; } // 在鏈表尾部添加一個元素 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("鏈表長度：" + size + "，鏈表信息："); // // 寫法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 寫法二 for (Node node = dummyHead.next; node != null ; node = node.next) { sb.append(node + "->"); } sb.append("NULL"); return sb.toString(); } }
4. `MyLinkedListStack`
public class MyLinkedListStackimplements IStack { private MyLinkedList mkl; public MyLinkedListStack () { mkl = new MyLinkedList (); } /** * @param e 入棧 */ @Override public void push (E e) { mkl.addFirst(e); } /** * @return e * 出棧 */ @Override public E pop () { return mkl.removefirst(); } /** * @return e * 查看棧頂?shù)囊粋€元素 */ @Override public E peek () { return mkl.getFirst(); } /** * @return size * 查看棧中實際元素的個數(shù) */ @Override public int getSize () { return mkl.getSize(); } /** * @return not empty * 判斷棧中是否為空 */ @Override public boolean isEmpty () { return mkl.isEmpty(); } @Override public String toString () { int size = getSize(); StringBuilder sb = new StringBuilder(); sb.append("MyLinkedlistStack: 元素個數(shù)=" + size); sb.append(", stack top=[ "); for (int i = 0; i < size ; i++) { sb.append(mkl.get(i)); sb.append("->"); } sb.append("NULL ]"); return sb.toString(); } }
5. `MyArray`
public class MyArray{ private E [] data; private int size; // 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造Array public MyArray (int capacity) { data = (E[])new Object[capacity]; size = 0; } // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 獲取數(shù)組中的元素實際個數(shù) public int getSize () { return size; } // 獲取數(shù)組的總?cè)萘? public int getCapacity () { return data.length; } // 返回數(shù)組是否為空 public boolean isEmpty () { return size == 0; } // 重新給數(shù)組擴容 private void resize (int newCapacity) { E[] newData = (E[])new Object[newCapacity]; int index = size - 1; while (index > -1) { newData[index] = get(index); index --; } data = newData; } // 給數(shù)組添加一個新元素 public void add (E e) { if (size == data.length) { // throw new IllegalArgumentException("add error. Array is full."); resize(2 * data.length); } data[size] = e; size++; } // 向所有元素后添加一個新元素 （與 add方法功能一樣） push public void addLast (E e) { // 復(fù)用插入元素的方法 insert(size, e); } // 在所有元素前添加一個新元素 unshift public void addFirst (E e) { insert(0, e); } // 在index索引的位置插入一個新元素e public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("insert error. require index < 0 or index > size"); } if (size == data.length) { // throw new IllegalArgumentException("add error. Array is full."); resize(2 * data.length); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 獲取index索引位置的元素 public E get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } return data[index]; } // 獲取數(shù)組中第一個元素（純查看） public E getFirst () { return get(0); } // 獲取數(shù)組中最后一個元素（純查看） public E getLast () { return get(size - 1); } // 修改index索引位置的元素為e public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } data[index] = e; } // 查找數(shù)組中是否有元素e public boolean contain (E e) { for (int i = 0; i < size; i++) { // if (data[i] == e) { // 值比較 用 == if (data[i].equals(e)) { // 引用比較 用 equals() return true; } } return false; } // 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1 public int find (E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組 public MyArray findAll (E e) { MyArray ma = new MyArray(20); for (int i = 0; i < size; i++) { if (data[i].equals(e)) { ma.add(i); } } return ma; // int[] result = new int[ma.getSize()]; // for (int i = 0; i < ma.getSize(); i++) { // result[i] = ma.get(i); // } // // return result; } // 從數(shù)組中刪除第一個元素, 返回刪除的元素 public E removeFirst () { return remove(0); } // 從數(shù)組中刪除最后一個元素, 返回刪除的元素 public E removeLast () { return remove(size - 1); } // 從數(shù)組中刪除第一個元素e public void removeElement (E e) { int index = find(e); if (index != -1) { remove(index); } // if (contain(e)) { // int index = find(e); // remove(index); // } } // 從數(shù)組中刪除所有元素e public void removeAllElement (E e) { int index = find(e); while (index != -1) { remove(index); index = find(e); } // while (contain(e)) { // removeElement(e); // } } // 從數(shù)組中刪除index位置的元素, 返回刪除的元素 public E remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } E temp = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } // for (int i = index + 1; i < size; i++) { // data[i - 1] = data[i]; // } size --; // data[size] = 0; data[size] = null; // 防止復(fù)雜度震蕩 防止容量為4，size為1時，data.length / 2 為 0 if(size == data.length / 4 && data.length / 2 != 0) { resize(data.length / 2); } return temp; } @Override // @Override: 方法名 日期-開發(fā)人員 public String toString () { StringBuilder sb = new StringBuilder(); String arrInfo = "Array: size = %d，capacity = %d "; sb.append(String.format(arrInfo, size, data.length)); sb.append("["); for (int i = 0; i < size - 1; i ++) { sb.append(data[i]); sb.append(","); } sb.append(data[size - 1]); sb.append("]"); return sb.toString(); } }
6. `MyStack`
public class MyStackimplements IStack { // 借用自定義個動態(tài)數(shù)組 private MyArray ma; public MyStack () { ma = new MyArray (); } public MyStack (int capacity) { ma = new MyArray (capacity); } /** * @param e * @return 入棧 */ @Override public void push(E e) { ma.addLast(e); } /** * @return 出棧 */ @Override public E pop() { return ma.removeLast(); } /** * @return 查看棧頂?shù)脑? */ @Override public E peek() { return ma.getLast(); } /** * @return 獲取棧中實際元素的個數(shù) */ @Override public int getSize() { return ma.getSize(); } /** * @return 判斷棧是否為空 */ @Override public boolean isEmpty() { return ma.isEmpty(); } // 返回棧的容量 public int getCapacity () { return ma.getCapacity(); } @Override // @Override: 方法名 日期-開發(fā)人員 public String toString () { int size = ma.getSize(); // int capacity = ma.getCapacity(); StringBuilder sb = new StringBuilder(); // String arrInfo = "Stack: size = %d，capacity = %d "; // sb.append(String.format(arrInfo, size, capacity)); sb.append("Stack: ["); for (int i = 0; i < size - 1; i ++) { sb.append(ma.get(i)); sb.append(","); } if (!ma.i
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/102904.html
摘要：鏈表與遞歸已經(jīng)從底層完整實現(xiàn)了一個單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了棧和隊列，在實現(xiàn)隊列的時候?qū)︽湵磉M行了一些改進。計算這個區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文...
摘要：鏈表與遞歸已經(jīng)從底層完整實現(xiàn)了一個單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了棧和隊列，在實現(xiàn)隊列的時候?qū)︽湵磉M行了一些改進。計算這個區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文...
摘要：鏈表鏈表是最基礎(chǔ)的動態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表是非常重要的線性數(shù)據(jù)結(jié)構(gòu)以下三種，底層都是依托靜態(tài)數(shù)組，靠解決固定容量問題。要清楚什么時候使用數(shù)組這樣的靜態(tài)數(shù)據(jù)結(jié)構(gòu)，什么時候使用鏈表這類的動態(tài)數(shù)據(jù)結(jié)構(gòu)。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解...
摘要：棧的實現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)非常有用但其實是非常簡單的。其實棧頂元素反映了在嵌套的層級關(guān)系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文章大概的內(nèi)容如下：Arrays(數(shù)組)、Stacks(棧)...
摘要：棧的實現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)非常有用但其實是非常簡單的。其實棧頂元素反映了在嵌套的層級關(guān)系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文章大概的內(nèi)容如下：Arrays(數(shù)組)、Stacks(棧)...
閱讀 784·2021-08-17 10:11
閱讀 1653·2019-08-30 11:15
閱讀 1090·2019-08-26 13:54
閱讀 3556·2019-08-26 11:47
閱讀 1289·2019-08-26 10:20
閱讀 2894·2019-08-23 18:35
閱讀 1264·2019-08-23 17:52
閱讀 1351·2019-08-23 16:19
