如何學習并掌握鏈表

本篇內容介紹了“如何學習并掌握鏈表”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

簡介

鏈表(Linked  List)是一種常見的基礎數(shù)據結構，是一種線性表，但是并不會按線性的順序存儲數(shù)據，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。

鏈表是由數(shù)據域和指針域兩部分組成的，它的組成結構如下：

復雜度分析

由于鏈表無需按順序存儲，因此鏈表在插入的時可以達到 O(1) 的復雜度，比順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要 O(n)  的時間，而順序表插入和查詢的時間復雜度分別是 O(log n) 和 O(1)。

優(yōu)缺點分析

使用鏈表結構可以克服數(shù)組鏈表需要預先知道數(shù)據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現(xiàn)靈活的內存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大。

分類

鏈表通常會分為以下三類：

• 單向鏈表

• 雙向鏈表

• 循環(huán)鏈表

• 單循鏈表

• 雙循環(huán)鏈表

1.單向鏈表

鏈表中最簡單的一種是單向鏈表，或叫單鏈表，它包含兩個域，一個數(shù)據域和一個指針域，指針域用于指向下一個節(jié)點，而最后一個節(jié)點則指向一個空值，如下圖所示：

單鏈表的遍歷方向單一，只能從鏈頭一直遍歷到鏈尾。它的缺點是當要查詢某一個節(jié)點的前一個節(jié)點時，只能再次從頭進行遍歷查詢，因此效率比較低，而雙向鏈表的出現(xiàn)恰好解決了這個問題。

接下來，我們用代碼來實現(xiàn)一下單向鏈表的節(jié)點：

private static class Node<E> {     E item;     Node<E> next;      Node(E element, Node<E> next) {         this.item = element;         this.next = next;     } }

2.雙向鏈表

雙向鏈表也叫雙面鏈表，它的每個節(jié)點由三部分組成：prev 指針指向前置節(jié)點，此節(jié)點的數(shù)據和 next 指針指向后置節(jié)點，如下圖所示：

接下來，我們用代碼來實現(xiàn)一下雙向鏈表的節(jié)點：

private static class Node<E> {     E item;     Node<E> next;     Node<E> prev;      Node(Node<E> prev, E element, Node<E> next) {         this.item = element;         this.next = next;         this.prev = prev;     } }

3.循環(huán)鏈表

循環(huán)鏈表又分為單循環(huán)鏈表和雙循環(huán)鏈表，也就是將單向鏈表或雙向鏈表的首尾節(jié)點進行連接，這樣就實現(xiàn)了單循環(huán)鏈表或雙循環(huán)鏈表了，如下圖所示：

Java中的鏈表

學習了鏈表的基礎知識之后，我們來思考一個問題：Java 中的鏈表 LinkedList  是屬于哪種類型的鏈表呢?單向鏈表還是雙向鏈表?

要回答這個問題，首先我們要來看 JDK 中的源碼，如下所示：

package java.util;  import java.util.function.Consumer;  public class LinkedList<E>     extends AbstractSequentialList<E>     implements List<E>, Deque<E>, Cloneable, java.io.Serializable {  // 鏈表大小     transient int size = 0;      // 鏈表頭部     transient Node<E> first;      // 鏈表尾部     transient Node<E> last;      public LinkedList() {     }      public LinkedList(Collection<? extends E> c) {         this();         addAll(c);     }       // 獲取頭部元素     public E getFirst() {         final Node<E> f = first;         if (f == null)             throw new NoSuchElementException();         return f.item;     }      // 獲取尾部元素     public E getLast() {         final Node<E> l = last;         if (l == null)             throw new NoSuchElementException();         return l.item;     }      // 刪除頭部元素     public E removeFirst() {         final Node<E> f = first;         if (f == null)             throw new NoSuchElementException();         return unlinkFirst(f);     }      // 刪除尾部元素     public E removeLast() {         final Node<E> l = last;         if (l == null)             throw new NoSuchElementException();         return unlinkLast(l);     }      // 添加頭部元素     public void addFirst(E e) {         linkFirst(e);     }          // 添加頭部元素的具體執(zhí)行方法     private void linkFirst(E e) {         final Node<E> f = first;         final Node<E> newNode = new Node<>(null, e, f);         first = newNode;         if (f == null)             last = newNode;         else             f.prev = newNode;         size++;         modCount++;     }      // 添加尾部元素     public void addLast(E e) {         linkLast(e);     }          // 添加尾部元素的具體方法     void linkLast(E e) {         final Node<E> l = last;         final Node<E> newNode = new Node<>(l, e, null);         last = newNode;         if (l == null)             first = newNode;         else             l.next = newNode;         size++;         modCount++;     }      // 查詢鏈表個數(shù)     public int size() {         return size;     }      // 清空鏈表     public void clear() {         for (Node<E> x = first; x != null; ) {             Node<E> next = x.next;             x.item = null;             x.next = null;             x.prev = null;             x = next;         }         first = last = null;         size = 0;         modCount++;     }        // 根據下標獲取元素     public E get(int index) {         checkElementIndex(index);         return node(index).item;     }      private static class Node<E> {         E item;         Node<E> next;         Node<E> prev;          Node(Node<E> prev, E element, Node<E> next) {             this.item = element;             this.next = next;             this.prev = prev;         }     }     // 忽略其他方法...... }

從上述節(jié)點 Node 的定義可以看出：LinkedList 其實是一個雙向鏈表，因為它定義了兩個指針 next 和 prev  分別用來指向自己的下一個和上一個節(jié)點。

鏈表常用方法

LinkedList 的設計還是很巧妙的，了解了它的實現(xiàn)代碼之后，下面我們來看看它是如何使用的?或者說它的常用方法有哪些。

1.增加

接下來我們來演示一下增加方法的使用：

public class LinkedListTest {     public static void main(String[] a) {         LinkedList list = new LinkedList();         list.add("Java");         list.add("中文");         list.add("社群");         list.addFirst("頭部添加"); // 添加元素到頭部         list.addLast("尾部添加");  // 添加元素到最后         System.out.println(list);     } }

以上代碼的執(zhí)行結果為：

• [頭部添加, Java, 中文, 社群, 尾部添加]

出來以上的 3 個增加方法之外，LinkedList 還包含了其他的添加方法，如下所示：

• add(int index, E element)：向指定位置插入元素;

• offer(E e)：向鏈表末尾添加元素，返回是否成功;

• offerFirst(E e)：頭部插入元素，返回是否成功;

• offerLast(E e)：尾部插入元素，返回是否成功。

add 和 offer 的區(qū)別

它們的區(qū)別主要體現(xiàn)在以下兩點：

offer 方法屬于 Deque接口，add 方法屬于 Collection的接口;

當隊列添加失敗時，如果使用 add 方法會報錯，而 offer 方法會返回 false。

2.刪除

刪除功能的演示代碼如下：

import java.util.LinkedList;  public class LinkedListTest {     public static void main(String[] a) {         LinkedList list = new LinkedList();         list.offer("頭部");         list.offer("中間");         list.offer("尾部");          list.removeFirst(); // 刪除頭部元素         list.removeLast();  // 刪除尾部元素          System.out.println(list);     } }

以上代碼的執(zhí)行結果為：

[中間]

除了以上刪除方法之外，更多的刪除方法如下所示：

• clear()：清空鏈表;

• removeFirst()：刪除并返回第一個元素;

• removeLast()：刪除并返回最后一個元素;

• remove(Object o)：刪除某一元素，返回是否成功;

• remove(int index)：刪除指定位置的元素;

• poll()：刪除并返回第一個元素;

• remove()：刪除并返回第一個元素。

3.修改

修改方法的演示代碼如下：

import java.util.LinkedList;  public class LinkedListTest {     public static void main(String[] a) {         LinkedList list = new LinkedList();         list.offer("Java");         list.offer("MySQL");         list.offer("DB");                  // 修改         list.set(2, "Oracle");          System.out.println(list);     } }

以上代碼的執(zhí)行結果為：

[Java, MySQL, Oracle]

4.查詢查詢方法的演示代碼如下：

import java.util.LinkedList;  public class LinkedListTest {     public static void main(String[] a) {         LinkedList list = new LinkedList();         list.offer("Java");         list.offer("MySQL");         list.offer("DB");          // --- getXXX() 獲取 ---         // 獲取最后一個         System.out.println(list.getLast());         // 獲取首個         System.out.println(list.getFirst());         // 根據下標獲取         System.out.println(list.get(1));          // peekXXX() 獲取         System.out.println("--- peek() ---");         // 獲取最后一個         System.out.println(list.peekLast());         // 獲取首個         System.out.println(list.peekFirst());         // 根據首個         System.out.println(list.peek());     } }

以上代碼的執(zhí)行結果為：

DB  Java  MySQL  --- peek() ---  DB  Java  Java

5.遍歷

LinkedList 的遍歷方法包含以下三種。

遍歷方法一：

for (int size = linkedList.size(), i = 0; i < size; i++) {     System.out.println(linkedList.get(i)); }

遍歷方法二：

for (String str: linkedList) {     System.out.println(str); }

遍歷方法三：

Iterator iter = linkedList.iterator(); while (iter.hasNext()) {     System.out.println(iter.next()); }

鏈表應用：隊列 & 棧

1.用鏈表實現(xiàn)棧

接下來我們用鏈表來實現(xiàn)一個先進先出的“隊列”，實現(xiàn)代碼如下：

LinkedList list = new LinkedList(); // 元素入列 list.add("Java"); list.add("中文"); list.add("社群");  while (!list.isEmpty()) {     // 打印并移除隊頭元素     System.out.println(list.poll()); }

以上程序的執(zhí)行結果如下：

• Java

• 中文

• 社群

2.用鏈表實現(xiàn)隊列

然后我們用鏈表來實現(xiàn)一個后進先出的“?！?，實現(xiàn)代碼如下：

LinkedList list = new LinkedList(); // 元素入棧 list.add("Java"); list.add("中文"); list.add("社群");  while (!list.isEmpty()) {     // 打印并移除棧頂元素     System.out.println(list.pollLast()); }

以上程序的執(zhí)行結果如下：

• 社群

• 中文

• Java

鏈表使用場景

鏈表作為一種基本的物理結構，常被用來構建許多其它的邏輯結構，如堆棧、隊列都可以基于鏈表實現(xiàn)。

所謂的物理結構是指可以將數(shù)據存儲在物理空間中，比如數(shù)組和鏈表都屬于物理數(shù)據結構;而邏輯結構則是用于描述數(shù)據間的邏輯關系的，它可以由多種不同的物理結構來實現(xiàn)，比如隊列和棧都屬于邏輯結構。

鏈表常見筆試題

鏈表最常見的筆試題就是鏈表的反轉了，之前的文章《鏈表反轉的兩種實現(xiàn)方法，后一種擊敗了100%的用戶!》我們提供了 2  種鏈表反轉的方法，而本文我們再來擴充一下，提供 3 種鏈表反轉的方法。

實現(xiàn)方法 1：Stack我們先用圖解的方式來演示一下，使用棧實現(xiàn)鏈表反轉的具體過程，如下圖所示。

全部入棧：

全部入棧：

因為棧是先進后出的數(shù)據結構，因此它的執(zhí)行過程如下圖所示：

最終的執(zhí)行結果如下圖所示：

實現(xiàn)代碼如下所示：

public ListNode reverseList(ListNode head) {     if (head == null) return null;     Stack<ListNode> stack = new Stack<>();     stack.push(head); // 存入第一個節(jié)點     while (head.next != null) {         stack.push(head.next); // 存入其他節(jié)點         head = head.next; // 指針移動的下一位     }     // 反轉鏈表     ListNode listNode = stack.pop(); // 反轉第一個元素     ListNode lastNode = listNode; // 臨時節(jié)點，在下面的 while 中記錄上一個節(jié)點     while (!stack.isEmpty()) {         ListNode item = stack.pop(); // 當前節(jié)點         lastNode.next = item;         lastNode = item;     }     lastNode.next = null; // 最后一個節(jié)點賦為null（不然會造成死循環(huán)）     return listNode; }

LeetCode 驗證結果如下圖所示：

可以看出使用棧的方式來實現(xiàn)鏈表的反轉執(zhí)行的效率比較低。

實現(xiàn)方法2：遞歸

同樣的，我們先用圖解的方式來演示一下，此方法實現(xiàn)的具體過程，如下圖所示。

實現(xiàn)代碼如下所示：

public static ListNode reverseList(ListNode head) {     if (head == null || head.next == null) return head;     // 從下一個節(jié)點開始遞歸     ListNode reverse = reverseList(head.next);     head.next.next = head; // 設置下一個節(jié)點的 next 為當前節(jié)點     head.next = null; // 把當前節(jié)點的 next 賦值為 null，避免循環(huán)引用     return reverse; }

LeetCode 驗證結果如下圖所示：

可以看出這種實現(xiàn)方法在執(zhí)行效率方面已經滿足我們的需求了，性能還是很高的。

實現(xiàn)方法 3：循環(huán)

我們也可以通過循環(huán)的方式來實現(xiàn)鏈表反轉，只是這種方法無需重復調用自身方法，只需要一個循環(huán)就搞定了，實現(xiàn)代碼如下：

class Solution {     public ListNode reverseList(ListNode head) {         if (head == null) return null;         // 最終排序的倒序鏈表         ListNode prev = null;         while (head != null) {             // 循環(huán)的下個節(jié)點             ListNode next = head.next;             // 反轉節(jié)點操作             head.next = prev;             // 存儲下個節(jié)點的上個節(jié)點             prev = head;             // 移動指針到下一個循環(huán)             head = next;         }         return prev;     } }

LeetCode 驗證結果如下圖所示：

從上述圖片可以看出，使用此方法在時間復雜度和空間復雜度上都是目前的最優(yōu)解，比之前的兩種方法更加理想。

“如何學習并掌握鏈表”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！