本章我們介紹鏈表

前面我們已經(jīng)介紹了動態(tài)數(shù)組，棧和隊列。

它們的底層依托靜態(tài)數(shù)組;靠resize解決固定容量問題

鏈表是我們接觸的第一個真正的動態(tài)數(shù)組。

為什么鏈表很重要

鏈表是重點，也是難點。它是最簡單動態(tài)數(shù)據(jù)結(jié)構(gòu);后續(xù)我們還會學(xué)習(xí)更多的，比如二分搜索樹，平衡二叉樹，紅黑樹，后面很多的動態(tài)數(shù)據(jù)結(jié)構(gòu)都可以在理解鏈表的基礎(chǔ)上學(xué)習(xí)。

鏈表可以讓我們更深入的理解引用(C++中指針)，內(nèi)存管理等有更深理解。對于更深入的理解遞歸有好處，樹形中遞歸必須理解。

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

鏈表Linked List

數(shù)據(jù)存儲在“節(jié)點”(Node)中;

class Node{E e;Node next; }

車廂和車廂進(jìn)行連接，使用next進(jìn)行連接。

最后一個節(jié)點的next指向空，說明這個節(jié)點是最后一個節(jié)點了。優(yōu)點:真正的動態(tài)，不需要處理固定容量的問題

不像數(shù)組一下子必須new出來一片空間，需要考慮空間不夠用或浪費(fèi)。鏈表是你需要多少個數(shù)據(jù)，就生成多少個節(jié)點將他掛接起來，這就是所謂的動態(tài)的意思。

缺點: 喪失了隨機(jī)訪問的能力。不能像數(shù)組一樣，給定一個索引直接拿出對應(yīng)元素。底層機(jī)制中數(shù)組開辟的空間在內(nèi)存中是連續(xù)分布的，我們可以直接尋找索引對應(yīng)的偏移，直接計算出數(shù)據(jù)所存儲的內(nèi)存地址，直接用O(1)復(fù)雜度拿出。鏈表靠next連接，每個節(jié)點存儲地址不同，我們只能通過next順藤摸瓜找到我們要找的元素。

數(shù)組最好用于索引有語意的情況。scores[2] 2是學(xué)號，身份證號不能做索引;最大的優(yōu)點:支持快速查詢。

我們在編寫動態(tài)數(shù)組，但是其實這類索引沒有語義的情況更適合鏈表。

鏈表不適合用于索引有語意的情況。最大的優(yōu)點:動態(tài)

什么時候適合使用數(shù)組，什么時候適合使用鏈表。

鏈表實現(xiàn)

package cn.mtianyan;public class LinkedList<E> {// private設(shè)計，不被用戶感知private class Node{public E e;public Node next; // c++實現(xiàn)時是指針public Node(E e, Node next) {this.e = e;this.next = next;}public Node(E e) {this.e = e;this.next = null;}public Node() {this(null,null);}@Overridepublic String toString() {return "Node[" +"e=" + e +", next=" + next +']';}} }

上面是我們對于鏈表節(jié)點的設(shè)計。注意private設(shè)計，以及Node的成員變量Node

應(yīng)該有一個鏈表頭,聲明出LinkedList基本的成員變量。

private Node head;private int size;public LinkedList() {head = null;size = 0;}public LinkedList(Node head, int size) {this.head = head;this.size = size;}/*** 從數(shù)組創(chuàng)建鏈表的方法，待完善。** @param e*/public LinkedList(E[] e){}/*** 獲取鏈表中元素個數(shù)** @return*/public int getSize(){return size;}/*** 返回鏈表是否為空** @return*/public boolean isEmpty(){return size == 0;}

上面是鏈表中應(yīng)該有的成員變量和一些普通方法。

在鏈表頭添加元素是非常方便的，數(shù)組在數(shù)組尾部添加元素不用挪位會非常方便。數(shù)組中有size指向下一個空位置跟蹤隊尾，鏈表中有head來標(biāo)識鏈表的頭部。

node.next = head head = node public void addFirst(E e){// Node node = new Node(e);// node.next = head;// head = node;// 上面三行代碼的等價實現(xiàn)head = new Node(e,head); // 值為e的Node的next是head;head = 這個Nodesize++;}

上面有兩種等價的實現(xiàn)。

在索引為2的地方添加元素666,要找到之前的節(jié)點。關(guān)鍵:找到要添加的節(jié)點的前一個節(jié)點。前一個節(jié)點要特殊處理

順序是很重要的，不能顛倒。否則會丟失原本的prev.next。大多時候順序可以省下一個old的備份臨時變量。

/*** 在鏈表的index(0-based)位置添加新的元素e* 在鏈表中不是一個常用的操作，練習(xí)題用,面試用。* @param index* @param e*/public void add(int index,E e){// index可以取到size，在鏈表末尾空位置添加元素。if (index < 0 || index >size){throw new IllegalArgumentException("Add failed. Illegal index");}Node prevNode = head;// 因為有了dummyHead，多遍歷一次，遍歷index次for (int i = 0; i < index-1; i++) {// 驗證。 12 index 1添加，index-1=0一次也不執(zhí)行，正好是head。符合// 驗證。 1234 index 2添加，index-1=1 運(yùn)行一次pre指向head下一個也就是2，符合。prevNode = prevNode.next;}// Node insertNode = new Node(e);// insertNode.next = prevNode.next;// prevNode.next = insertNode;prevNode.next = new Node(e,prevNode.next); // 后半截是前兩句完成任務(wù)size++;}

鏈表的添加操作時，要找的是前一個節(jié)點。而我們之前定義的頭結(jié)點因為沒有前一個節(jié)點，需要進(jìn)行特殊處理,這樣不夠優(yōu)雅。而如果我們往前面加一個虛擬的頭結(jié)點，則可以將我們現(xiàn)在的頭結(jié)點和其他節(jié)點統(tǒng)一起來。

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

虛擬頭結(jié)點對用戶屏蔽不可見。

/*** 在鏈表的index(0-based)位置添加新的元素e* 在鏈表中不是一個常用的操作，練習(xí)題用,面試用。* @param index* @param e*/public void add(int index,E e){// index可以取到size，在鏈表末尾空位置添加元素。if (index < 0 || index >size){throw new IllegalArgumentException("Add failed. Illegal index");}Node prevNode = dummyHead;// 因為有了dummyHead，多遍歷一次，遍歷index次for (int i = 0; i < index; i++) {// 驗證。 12 index 1添加，index-1=0一次也不執(zhí)行，正好是head。符合// 驗證。 1234 index 2添加，index-1=1 運(yùn)行一次pre指向head下一個也就是2，符合。prevNode = prevNode.next;}// Node insertNode = new Node(e);// insertNode.next = prevNode.next;// prevNode.next = insertNode;prevNode.next = new Node(e,prevNode.next); // 后半截是前兩句完成任務(wù)size++;}/*** 在鏈表頭添加新元素e*/public void addFirst(E e){add(0,e);}/*** 在鏈表末尾添加新的元素e*/public void addLast(E e){add(size,e);}

添加元素操作時，注意指向，以及循環(huán)次數(shù)的驗證。

/*** 獲得鏈表的第index(0-based)位置元素* 鏈表中不是常用操作，練習(xí)用* @param index* @return*/public E get(int index){// index不可以取到size，索引從0開始，最多取到size-1if (index < 0 || index >=size){throw new IllegalArgumentException("Add failed. Illegal index");}Node cur = dummyHead.next; // 從索引為0元素開始// 下面與找index-1個節(jié)點保持一致。上面執(zhí)行了一次。所以從index-1個元素變成了找index個元素。for (int i = 0; i < index; i++) {cur = cur.next;}return cur.e;}public E getFirst(){return get(0);}public E getLast(){return get(size-1);}

插入時我們要尋找的是index的前一個位置，而get時，我們要找的就是index的當(dāng)前位置，因此要多找一次，在for循環(huán)不變情況下，從虛擬頭結(jié)點下一個節(jié)點開始遍歷。

/*** 修改鏈表的第index(0-based)個位置的元素為e* 在鏈表中不是一個常用的操作，練習(xí)用*/public void set(int index,E e){// index不可以取到size，索引從0開始，最多取到size-1if (index < 0 || index >=size){throw new IllegalArgumentException("Set failed. Illegal index");}Node cur = dummyHead.next; // 從索引為0元素開始// 下面與找index-1個節(jié)點保持一致。上面執(zhí)行了一次。所以從index-1個元素變成了找index個元素。for (int i = 0; i < index; i++) {cur = cur.next;}cur.e = e;}/*** 查找鏈表中是否有元素e*/public boolean contains(E e){Node cur = dummyHead.next;while (cur != null){if (cur.e.equals(e)){return true;}cur = cur.next;}return false;} @Overridepublic String toString() {StringBuilder res = new StringBuilder(); // Node cur = dummyHead.next; // while (cur != null){ // res.append(cur.e +"->"); // cur = cur.next; // } // res.append("NULL");res.append("head: ");for (Node cur=dummyHead.next;cur !=null;cur=cur.next){res.append(cur.e +"->");}res.append("NULL");return res.toString();}

兩種不同的遍歷方式是等價的。

package cn.mtianyan;public class Main {public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<>();for (int i = 0; i < 5; i++) {linkedList.addFirst(i);System.out.println(linkedList);}linkedList.add(2,888);System.out.println(linkedList);} }

運(yùn)行結(jié)果:

刪除元素

刪除索引為2位置的元素

要找到它之前的元素。

prev.next = delNode.next delNode.next = null

• 鏈表元素刪除時常見的錯誤。

cur 指向cur.next的位置。本質(zhì)是對于引用概念糊涂，Java中類的對象都是一個引用，理解成一個實際內(nèi)存的指向。cur = cur.next從原來指的位置，指到下一個位置，但對于鏈表來說沒有發(fā)生任何改變。要想改變鏈表就應(yīng)該改變節(jié)點的next指向。

/*** 刪除鏈表中指定index位置的元素* @param index* @return*/public E remove(int index){if (index < 0 || index >=size){throw new IllegalArgumentException("Set failed. Illegal index");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}Node retNode = prev.next;prev.next = retNode.next;retNode.next = null;size--;return retNode.e;}public E removeFirst(){return remove(0);}public E removeLast(){return remove(size-1);} linkedList.remove(2);System.out.println(linkedList);linkedList.removeFirst();System.out.println(linkedList);linkedList.removeLast();System.out.println(linkedList);

運(yùn)行結(jié)果:

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

• 添加操作:

O(n)是因為往鏈表尾部添加，要遍歷整個鏈表節(jié)點。O(n/2)可以看做操作中間的節(jié)點。

• 刪除操作:

• 修改操作:

set(index e) // O(n/2) = O(n)

• 查找操作:

get 和 contains 都是O(n/2) find操作是根據(jù)元素找index，鏈表中index沒啥用。

看起來，鏈表的增刪改查全都是O(n)級別的，比數(shù)組看起來差。鏈表沒有索引，無法像數(shù)組一樣快速訪問。

此時我們能利用的方法復(fù)雜度都是O(1)了;鏈表的改進(jìn)，比數(shù)組節(jié)省空間。最基礎(chǔ)動態(tài)數(shù)據(jù)結(jié)構(gòu)，對二叉樹平衡二叉樹的學(xué)習(xí)都能有輔助作用。

鏈表實現(xiàn)棧

只對鏈表頭進(jìn)行操作，也就是只能對一端進(jìn)行操作，很明顯是棧。隊列是要對兩端都進(jìn)行操作的。鏈表頭作為棧頂。

Interface Stack<E> implement LinkedListStack<E>int getSize();boolean isEmpty();void push(E e);E pop();E peek();

比較兩個棧的性能差異。

package cn.mtianyan;public class LinkedListStack<E> implements Stack<E> {private LinkedList<E> list;public LinkedListStack() {list = new LinkedList<>();}@Overridepublic int getSize() {return list.getSize();}@Overridepublic boolean isEmpty() {return list.isEmpty();}@Overridepublic void push(E e) {list.addFirst(e);}@Overridepublic E pop() {return list.removeFirst();}@Overridepublic E peek() {return list.getFirst();}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append("LinkedList Stack ：");res.append(list);return res.toString();} } public static void main(String[] args) {LinkedListStack stack = new LinkedListStack();for (int i = 0; i < 5; i++) {stack.push(i);System.out.println(stack);}stack.pop();System.out.println(stack);}

運(yùn)行結(jié)果:

package cn.mtianyan;import java.util.Random;public class mainTwoTest {// 測試使用stack運(yùn)行opCount個push和pop操作所需要的時間，單位：秒private static double testStack(Stack<Integer> stack, int opCount){long startTime = System.nanoTime();Random random = new Random();for(int i = 0 ; i < opCount ; i ++)stack.push(random.nextInt(Integer.MAX_VALUE));for(int i = 0 ; i < opCount ; i ++)stack.pop();long endTime = System.nanoTime();return (endTime - startTime) / 1e9;}public static void main(String[] args) {int opCount = 100000000;ArrayStack<Integer> arrayStack = new ArrayStack<>();double time1 = testStack(arrayStack, opCount);System.out.println("ArrayStack, time: " + time1 + " s");LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();double time2 = testStack(linkedListStack, opCount);System.out.println("LinkedListStack, time: " + time2 + " s");// 其實這個時間比較很復(fù)雜，因為LinkedListStack中包含更多的new操作} }

其實這個時間是比較不確定誰大誰小的。

運(yùn)行結(jié)果:

100000000 數(shù)據(jù):

10000000 數(shù)據(jù):

1000000 數(shù)據(jù):

100000 數(shù)據(jù):

基本可以看出，數(shù)據(jù)量小于100萬的時候LinkedList比較有優(yōu)勢，數(shù)據(jù)量大時ArrayList更優(yōu)。但它們實際是同樣級別時間復(fù)雜度的,最多相差幾倍。

鏈表實現(xiàn)隊列

隊列勢必會在鏈表的兩端同時操作，一端為O(1）一端為O(n)；使用數(shù)組時我們也遇到了這個問題，因此我們產(chǎn)生了使用循環(huán)隊列的方式。

鏈表中我們?yōu)槭裁磳τ阪湵眍^部的操作都簡單一些呢，因為我們有一個標(biāo)識的head。那么想讓尾部也可以操作簡單，設(shè)置一個tail變量。從兩端插入元素都是很容易的。

tail端前一個節(jié)點不容易找，得遍歷一遍。此時: head添加刪除都容易，tail添加容易，刪除不易。

因此隊列從head端刪除元素，從tail端插入元素。head 隊首負(fù)責(zé)出隊，tail隊尾負(fù)責(zé)入隊。由于沒有dummyHead，要注意鏈表為空的情況

package cn.mtianyan;public class LinkedListQueue<E> implements Queue<E> {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);}@Overridepublic String toString(){return e.toString();}}private Node head, tail;private int size;public LinkedListQueue(){head = null;tail = null;size = 0;}@Overridepublic int getSize(){return size;}@Overridepublic boolean isEmpty(){return size == 0;}@Overridepublic void enqueue(E e){// 如果隊尾為空，說明隊列是空的。因為tail一直指向最后一個非空節(jié)點。if(tail == null){tail = new Node(e);head = tail;}else{// 使用tail.next把新Node掛載上來。tail.next = new Node(e);// tail后挪tail = tail.next;}size ++;}@Overridepublic E dequeue(){if(isEmpty())throw new IllegalArgumentException("Cannot dequeue from an empty queue.");Node retNode = head;head = head.next; // head后移retNode.next = null; // 元素置空if(head == null) // 如果頭結(jié)點都沒得刪了tail = null;size --;return retNode.e;}@Overridepublic E getFront(){if(isEmpty())throw new IllegalArgumentException("Queue is empty.");return head.e;}@Overridepublic String toString(){StringBuilder res = new StringBuilder();res.append("Queue: front ");Node cur = head;while(cur != null) {res.append(cur + "->");cur = cur.next;}res.append("NULL tail");return res.toString();}public static void main(String[] args){LinkedListQueue<Integer> queue = new LinkedListQueue<>();for(int i = 0 ; i < 5 ; i ++){queue.enqueue(i);System.out.println(queue);if(i % 3 == 2){queue.dequeue();System.out.println(queue);}}} }

運(yùn)行結(jié)果:

測試性能差異:

package cn.mtianyan;import java.util.Random;public class MainThree {// 測試使用q運(yùn)行opCount個enqueueu和dequeue操作所需要的時間，單位：秒private static double testQueue(Queue<Integer> q, int opCount){long startTime = System.nanoTime();Random random = new Random();for(int i = 0 ; i < opCount ; i ++)q.enqueue(random.nextInt(Integer.MAX_VALUE));for(int i = 0 ; i < opCount ; i ++)q.dequeue();long endTime = System.nanoTime();return (endTime - startTime) / 1000000000.0;}public static void main(String[] args) {int opCount = 100000;ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();double time1 = testQueue(arrayQueue, opCount);System.out.println("ArrayQueue, time: " + time1 + " s");LoopQueue<Integer> loopQueue = new LoopQueue<>();double time2 = testQueue(loopQueue, opCount);System.out.println("LoopQueue, time: " + time2 + " s");LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();double time3 = testQueue(linkedListQueue, opCount);System.out.println("LinkedListQueue, time: " + time3 + " s");} }

運(yùn)行結(jié)果:

鏈表是一種適合用來學(xué)習(xí)遞歸的數(shù)據(jù)結(jié)構(gòu)。下一章我們將對于鏈表和遞歸的相關(guān)知識進(jìn)行學(xué)習(xí)。

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的4-玩转数据结构-链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。