深入理解鏈表和手寫鏈表以及面試中常問鏈表的問題

02-25

雙鏈表

上一期講到了順序表與鏈表的基本知識了解鏈表的基本知識。並且分析了ArrayList的源碼。順序表(隨機訪問速度快，插入和刪除效率低)和鏈表(隨機訪問速度慢，插入和刪除效率高)的優缺點。在開始寫雙鏈表之前我們分析一下LinkedList(典型的雙鏈表)源碼，來看一下Java 中是如何實現雙鏈表的。

LinkedList 源碼解析

在分析一個類時，首先分析類的繼承關係，再分析構造方法和屬性。

LinkedList 繼承關係

public class LinkedList extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable

LinkedList 繼承 AbstractSequentialList,而 AbstractSequentialList extends AbstractList 在上一期中 ArrayList 繼承AbstractList ，AbstractSequentialList 它實現了list 的一些位置相關的操作。
實現list 介面能對它進行隊列操作。
Deque雙端隊列，雙端隊列中的元素可以從兩端彈出，插入和刪除操作限定在隊列的兩邊進行
Cloneable 覆蓋了函數clone()
Serializable 支持序列化，能通過序列化傳輸數據

LinkedList 屬性

關鍵字transient 標識的欄位的生命周期僅存於調用者的內存中而不會寫到磁碟里持久化。

我們都知道一個對象只要實現了Serilizable介面，這個對象就可以被序列化，java的這種序列
化模式為開發者提供了很多便利，我們可以不必關係具體序列化的過程，只要這個類實現了Seril
izable介面，這個類的所有屬性和方法都會自動序列化。
然而在實際開發過程中，我們常常會遇到這樣的問題，這個類的有些屬性需要序列化，而其他屬
性不需要被序列化，打個比方，如果一個用戶有一些敏感信息（如密碼，銀行卡號等），為了安
全起見，不希望在網路操作（主要涉及到序列化操作，本地序列化緩存也適用）中被傳輸，這些信
息對應的變數就可以加上transient關鍵字。換句話說，這個欄位的生命周期僅存於調用者的內存
中而不會寫到磁碟里持久化。
總之，java 的transient關鍵字為我們提供了便利，你只需要實現Serilizable介面，將不需要
序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目

的地中。

transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;

每個節點都是存儲對象Node，包括(E item;Node next;Node prev;)這就意味著LinkedList 佔用的內存會比較大,ArrayList 只包括 E,LinkedList 比ArrayList 佔用內存大

private static class Node<E> { //當前節點的 item 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; } }

LinkedList 構造方法

/** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collections * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

LinkedList 有兩個構造方法，第一個就不必說了，第二個構造一個鏈表，傳入的是一個list(interface List extends Collection)

addAll(c) 方法

public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { //判斷 index >= 0 && index <= size; checkPositionIndex(index); //將list 轉換成一個數組 Object[] a = c.toArray(); int numNew = a.length; //若數組的長度為0 返回false 不能構造鏈表 if (numNew == 0) return false; Node<E> pred, succ; //若插入的位置 == 鏈表的大小 if (index == size) { succ = null; //準備要插入的節點 == last 鏈表的最後一個節點，準備循環從最後一個節點添加 pred = last; } else { //若插入的位置！= 鏈表的大小找到要插入的位置 succ = node(index); //準備插入的節點 == 插入位置的前一個節點 pred = succ.prev; } //循環數組中的Object 創建Node 節點 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //創建新的節點Node Node<E> newNode = new Node<>(pred, e, null); //若準備插入的節點為null 說明 index == size 而 pred = last鏈表為空 if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } //succ == null 說明 index == size if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }

LinkedList 添加節點

add(E e) 尾部插入

public boolean add(E e) {

    linkLast(e);
    return

true;
}
/**
 * Links e as last element.

*/ void linkLast(E e) {

//尾部節點

final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    //尾部 == 新的節點
    last = newNode;
    //注意判斷尾部是否為空，若尾部last為空 則說明鏈表為空

if (l == null)
        //第一個節點 == newNode
        first = newNode;
    else

//之前的尾部節點的next 指向新添加的節點
        l.next = newNode;

 
    //鏈表大小加一
    size++;
    modCount++;
}

add(int index, E element) 中間插入

public void add(int index, E element) {

 //插入的位置必須>=0 並且<= size
    checkPositionIndex(index);
    //尾部插入

if (index == size)
        linkLast(element);

else //中間插入首先找到插入位置的節點

        linkBefore(element, node(index));
}
void

linkBefore(E e, Node<E> succ)

{
    // assert succ != null;

//插入位置的節點的前一個節點

final Node<E> pred = succ.prev;
    //new 要插入的節點

final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else

 
        pred.next = newNode;
    size++;
    modCount++;
}
Node<E> node(int index)

{
    // assert isElementIndex(index);

//插入的位置 < 鏈表大小的一半則從左側 first 節點查找

if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;

 
    } else {
        //插入的位置 > 鏈表大小的一半則從右側  last 節點查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList 刪除節點

public E remove(int index) { checkElementIndex(index); //要刪除某個節點同樣要找到該位置的節點 return unlink(node(index)); }E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //刪除的節點前一個為空則說明刪除的是第一個節點 if (prev == null) { //第一個節點first = 刪除節點的下一個節點 first = next; } else { //刪除的節點前一個不為空刪除節點的前一個節點的next //指向刪除節點的下一個節點 prev.next = next; //將刪除節點 prev 置為null x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //將刪除節點的item 置為null x.item = null; //鏈表減一 size--; modCount++; return element; }

LinkedList 查找節點

查找節點為耗時較長，演算法複雜度為 o(n) = n

Node<E> node(int index) { // assert isElementIndex(index); //插入的位置 < 鏈表大小的一半則從左側 first 節點查找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //插入的位置 > 鏈表大小的一半則從右側 last 節點查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

鏈表總結

從上述分析我們可以得出，鏈表(LinkedList)的尾插效率高，中間插入和刪除演算法複雜度為 o
(n) = n,對比順序表（ArrayList ）插入刪除都用到了複製System.arraycopy(
elementData, index, elementData, index + 1,size - index);
演算法複雜度要比雙鏈表的插入和刪除複雜度高。如果頻繁的插入和刪除操作建議用鏈表的存儲結構；
如果要想快速的查找到某條數據建議用順序表的存儲結構。

手寫雙鏈表

如何手寫一個雙鏈表，我們可以仿照LinkedList 的源碼寫一個簡單的雙鏈表

首先雙鏈表的模型類：

class Node{ Object data; Node next; Node per;}

需要的屬性

int size; Node frist; Node last;

Node靜態類

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; } }

完整的代碼如下：

public class LinkedList<E> { public LinkedList() { } Node<E> frist; Node<E> last; int size; /** * 向鏈表的尾部添加一個元素 * * @param e */ public void add(E e) { linkLast(e); } public void add(int index, E e) { if (index < 0 || index > size) return; if (index == size) {//插入尾部 linkLast(e); } else { Node<E> currentNode = node(index);//拿到當前位置要插入的節點 Node<E> prev = currentNode.prev; Node<E> newNode = new Node<>(prev, e, currentNode); if (prev == null) {//頭部插入 frist = newNode; } else {//中間插入 prev.next = newNode;//Note : 這裡兩個位置不能換 } currentNode.prev = newNode;//Note: 查到的節點prev 要指向新的節點 size++; } } public void remove(int index) { if (index < 0 || index > size) return; unLinkNode(node(index)); } private void unLinkNode(Node<E> node) { Node<E> prev = node.prev; Node<E> next = node.next; if (prev == null){ frist = next; }else { prev.next = next; node.prev = null; } if (next == null){ last = prev; }else { next.prev = prev; node.next = null; } size --; } /** * 獲取某個節點的元素 * * @param index * @return */ public E get(int index) { if (index < 0 || index > size) return null; return node(index).item; } private Node<E> node(int index) { if ((size >> 1) < index) {//從尾部開始循環 Node<E> node = last; for (int i = size - 1; i > index; i--) { node = last.prev; } return node; } else {//從頭部開始循環 Node<E> node = frist; for (int i = 0; i < index; i++) { node = node.next; } return node; } } private void linkLast(E e) { Node<E> newNode = new Node<>(last, e, null); Node<E> l = last;//拿到之前的最後一個節點 last = newNode;//將添加的新節點newNode 賦給last 最後一個節點 if (l == null) {//如果之前的最後一個節點為空 frist = newNode; } else {//如果之前的最後一個節點不為空 l.next = newNode; } size++; } 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; } }}

知道如何寫一個雙鏈表，那麼寫一個單鏈表就更簡單了。

在面試中經常問到，如何將一個單鏈表逆置?

在實現逆置之前我們寫一個單鏈表，代碼如下:

public class SingleList<E> { private static class Node<E> { E item; Node<E> next; public Node(E item, Node<E> next) { this.item = item; this.next = next; } } private Node<E> frist; private Node<E> last; public int size; /** * 向尾部添加一個元素 * * @param e */ public void add(E e) { lastList(e); } /** * 在某個位置插入一個元素 * * @param e * @param index */ public void add(E e, int index) { if (index < 0 || index > size) return; if (index == size) {//插入尾部 lastList(e); } else { if (index == 0) { Node<E> l = frist; Node<E> newNode = new Node<>(e, l);//新的元素在插入位置的前一個位置 frist = newNode; } else { Node<E> fNode = node(index - 1);//找到要插入位置的前一個位置 Node<E> lNode = fNode.next; Node<E> newNode = new Node<>(e, lNode); fNode.next = newNode; } size++; } } /** * 刪除某個節點 * * @param index */ public void remove(int index) { unLink(index); } private void unLink(int index) { if (index < 0 || index > size) return; if (index == size) {//刪尾部 Node<E> node = node(index - 1); node.next = null; last = node; } else if (index == 0) {//刪頭部 Node<E> l = this.frist; frist = l.next; } else { Node<E> node = node(index - 1);//要刪除的前一個節點 Node<E> removeNode = node.next;//要刪除的節點 Node<E> lNode = removeNode.next;//要刪除的後一個節點 node.next = lNode; } size--; } public void remove(E e) { Node<E> newNode = frist; int index = -1; for (int i = 0; i < size; i++) { newNode = newNode.next; if (e.equals(newNode.item)) { index = i; break; } } if (index != -1) unLink(index); } private void lastList(E e) { Node<E> newNode = new Node<>(e, null);//一個新的節點 Node<E> l = last; last = newNode;//將最後一個節點賦值 if (l == null) { frist = newNode; } else { l.next = newNode; } size++; } /** * 獲取節點的某個元素 * * @param index * @return */ public E get(int index) { if (index < 0 || index > size) { return null; } return node(index).item; } public Node<E> node(int index) { Node<E> newNode = frist; for (int i = 0; i < index; i++) { newNode = newNode.next; } return newNode; }}

測試單鏈表的添加個刪除

SingleList<Integer> singleList = new SingleList<>(); singleList.add(1); singleList.add(2); singleList.add(3); singleList.add(4); singleList.add(5);// singleList.add(9,0);// singleList.add(8,5);// singleList.add(7,2);// singleList.remove(6);// singleList.remove(3); for (int i = 0; i < singleList.size; i++) { System.out.print(singleList.get(i) + " "); }

如何實現逆置？

第一種方法，循環法

/** * 單鏈表的逆置 * 第一種方法實現循環 */ public void inverse() { Node<E> l = this.last; Node<E> curr = this.frist; Node<E> reve = null; while (curr != null) { Node<E> temp = curr; curr = curr.next; temp.next = reve; reve = temp; } frist = reve; }

如上圖所示：

第一次循環後得到的 --》 temp = 1 curr =2 temp.next = null reve = temp = 1 ;鏈表的結構就變為 1 --> null 2 --> 3 --> 4.

第二次循環後得到的 --》 temp = 2 curr = 3 temp.next = 1 reve = temp = 2 ;鏈表的結構就變為 2 --> 1 --> null 3 --> 4

第三次循環後得到的 --》 temp = 3 curr = 4 temp.next = 2 reve = temp = 3 ;鏈表的結構就變為 3 --> 2 --> 1 --> null 4

….

如此類推就可以得到一個逆置的單鏈表。

第二種方法，遞歸法

/** * 遞歸的方式轉置 */ public Node<T> reverse(Node<T> head) { if (head == null || head.next == null) { return head; } Node<T> tail = reverse(head.next); head.next.next = head; head.next = null; return tail; } public void transterReverse() { this.frist = reverse(this.frist); }

如上圖所示遞歸法的逆置邏輯：

1 --> 2 --> 3 <-- 4

1 --> 2 <-- 3 <--4

1 <-- 2 <-- 3 <--4

至此，數據結構線性表的內容基本講完。