(超詳細) 動手撰寫 — 鏈表 （Java實作）

目錄

• 前言
• 概念
• 鏈表的設計
• 完整代碼
  • List介面
  • 抽象父類設計
  • 鏈表—LinkedList
• 虛擬頭結點
  • 概念
  • 結構設計
  • 方法變動
• 雙向鏈表
  • 概念
  • 雙向鏈表設計
  • 方法變動
• 回圈鏈表
  • 單向回圈鏈表
  • 雙向回圈鏈表
• 小結
  • 單向鏈表 VS 雙向鏈表
  • 動態陣列 VS 鏈表
• 宣告

前言

在前面的實作的動手寫個Java動態陣列里，雖然對于用戶而言，看是實作了動態擴容的功能，實際上，只是依托底層寫的方法ensureCapacity在陣列容量不足的時候，對重新申請一個原陣列1.5倍容量的新陣列，再將原有陣列中存放的元素復制到新陣列來，陣列指標指向新陣列，從根本上來說，這并不是真正的動態，

同時，陣列的拷貝，以及陣列申請的空間并未全部存盤元素，會降低效率，也會造成記憶體空間的浪費，但這對于鏈表來說，并不是個問題，鏈表是做到了用多少記憶體就申請多少記憶體空間，這才是真正的動態資料結構，

概念

什么是鏈表？

鏈表是一種鏈式存盤的線性表，所有元素的記憶體地址不一定是連續的

鏈表的結構

對鏈表而言，資料是存盤在“結點”（Node）中的，可以使用一個資料域來存盤資料，這里我稱為 element；然后結點中還有一個用來指向下一個結點位置的結點域，一般稱為 next，而對于鏈表的結尾，一般是以 NULL 作為結尾，所以鏈表中的最后一個結點的結點域 next 指向的是 NULL，圖示鏈表結構：

鏈表的設計

/**
  * 定義鏈表第一結點，指向鏈表頭一個元素
  */
private Node<E> first;

/**
  * 定義結點類Node，包含元素和指向下一個結點的地址參考
  * @param <E>
  */
private static class Node<E>{
    E element;
    Node<E> next;

    public Node(E element, Node<E> next) {
        this.element = element;
        this.next = next;
    }
}

Node類是鏈表中結點的定義，first節點，size并不是存盤鏈表元素，而是用于存盤鏈表的元素數量，在上一節動手實作Java動態陣列的時候說到了，鏈表的大部分介面和動態陣列是一致的，Java語言長久不衰的原因有一點就是使用Java這種靜態編譯型的語言能夠寫出可維護性高的代碼，提倡OCP原則，面向介面編程，面向抽象編程，

在這里把鏈表和動態陣列是一致的方法及屬性抽取成List介面和AbstractList抽象類，畫一下類圖關系：

List介面中定義的屬性與方法

1、屬性：

• int ELEMENT_NOT_FOUND = -1; —— 查無元素的回傳標志

2、介面方法：

• int size(); —— 查詢當前鏈表元素的數量
• boolean isEmpty(); —— 判斷鏈表是否為空
• E set(int index, E element); —— 設定index位置的元素
• E get(int index); —— 獲取index位置的元素
• boolean contains(E element); —— 是否包含element元素
• int indexOf(E element); —— 查看元素的索引
• void add(E element); —— 添加元素到尾部
• void add(int index, E element);—— 在index位置插入一個元素
• E remove(int index); —— 洗掉index位置的元素
• void clear(); —— 清除所有元素

AbstractList抽象類定義的屬性與方法

將不影響編碼的共同方法，在抽象類AbstractList實作，其他方法放到鏈表類LinkedList或動態陣列DynamicArray具體編碼實作，這樣做的好處就是，提高了代碼的復用性和可維護性

1、屬性：

• protected int size; —— 查無元素的回傳標志

2、抽象類方法：

• int size(); —— 查詢當前鏈表元素的數量
• boolean isEmpty(); —— 判斷鏈表是否為空
• boolean contains(E element); —— 是否包含element元素
• void add(E element); —— 添加元素到尾部
• protected void outOfBounds(int index) —— 非法索引訪問拋出例外
• protected void rangeCheck(int index) —— 索引檢查函式
• protected void rangeCheckForAdd(int index) —— 添加元素的索引檢查函式

LinkedList鏈表類定義的屬性與方法

1、屬性

• private Node<E> first; —— 定義鏈表第一結點，指向鏈表頭一個元素

2、方法

• E set(int index, E element); —— 設定index位置的元素
• E get(int index); —— 獲取index位置的元素
• int indexOf(E element); —— 查看元素的索引
• void add(int index, E element);—— 在index位置插入一個元素
• E remove(int index); —— 洗掉index位置的元素
• public E remove(E element); —— 洗掉指定元素
• void clear(); —— 清除所有元素
• private Node<E> node(int index) —— 獲取index位置對應的結點物件

完成設計后，是具體的方法編碼實作，一些簡單的方法在這里就不作解釋了，注釋已經很清楚了，這里講一些重點的方法

鏈表初始化

定義在LinkedList 中的private Node<E> first; 以及抽象父類AbstractList中的protected int size;是組成鏈表的第一結點，在沒有添加元素結點之前，它的值是這樣的：

再看一下void add(int index, E element);方法，這是向指定索引添加元素的方法，我們往指定索引添加元素時，需要找到該索引前的節點，再修改指標指向，完成添加元素結點的操作，將該操作提取成private Node<E> node(int index)方法，

講一下node方法吧，首先這里，我們要明白，first是一個地址參考，也就是鏈表第一節結點，如果size為0，first指向的是null,如果size不為0，則指向的是鏈表頭結點，來看看node的代碼實作：

/**
  * 獲取index位置對應的結點物件
  * @param index
  * @return
  */
private Node<E> node(int index){
    rangeCheck(index);

    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

要查找index索引位置的結點，從first出發，需要next尋找index次，例如我們查找索引為2的結點，程序如下圖：

講完上面的方法，回到add方法，添加的程序是將新結點指向要插入的索引結點，修改索引前一結點的指向，將其指向新結點，然后size++，這里依據index = 0條件成立與否要劃分兩種情況，因為index = 0 ,前面是沒有元素結點的，只有first節點地址參考，上代碼，分析：

/**
 * 在index位置插入一個元素
 *
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == 0){
        first = new Node<>(element,first);
    }else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}

如果index != 0,就很好理解了，先是Node<E> prev = node(index - 1);，找到索引位置的前一結點，然后修改指標指向，prev.next = new Node<>(element,prev.next);，畫圖解釋：

當然index = 0 ，也是很好理解的，這里以size = 0,index = 0 為例，畫圖演示：

洗掉結點，和添加的原理是差不多的，這里就不畫圖解說了，看完上面對于幾個重點方法的分析后，相信對于上面鏈表的結構就不會帶有疑惑了

完整代碼

List介面

public interface List<E> {

    //查無元素的回傳標志
    int ELEMENT_NOT_FOUND = -1;

    /**
     * 元素的數量
     * @return
     */
    int size();

    /**
     * 是否為空
     * @return
     */
    boolean isEmpty();

    /**
     * 設定index位置的元素
     * @param index
     * @param element
     * @return 原來的元素?
     */
    E set(int index, E element);

    /**
     * 獲取index位置的元素
     * @param index
     * @return
     */
    E get(int index);

    /**
     * 是否包含某個元素
     * @param element
     * @return
     */
    boolean contains(E element);

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    int indexOf(E element);

    /**
     * 添加元素到尾部
     * @param element
     */
    void add(E element);


    /**
     * 在index位置插入一個元素
     * @param index
     * @param element
     */
    void add(int index, E element);

    /**
     * 洗掉index位置的元素
     * @param index
     * @return
     */
    E remove(int index);

    /**
     * 洗掉指定元素
     * @param element
     * @return
     */
    public E remove(E element);

    /**
     * 清除所有元素
     */
    void clear();
}

抽象父類設計

抽象父類AbstractList是對介面List的實作

public abstract class AbstractList<E> implements List<E>  {
    /**
     * 元素的數量
     */
    protected int size;

    /**
     * 元素的數量
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 是否為空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 是否包含某個元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 非法索引訪問陣列例外
     * @param index
     */
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /**
     * 索引檢查函式
     * @param index
     */
    protected void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    /**
     * 陣列添加元素的索引檢查函式
     * @param index
     */
    protected void rangeCheckForAdd(int index) {
        //index > size,元素可以添加在陣列size位置，即陣列尾部下一存盤單元
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

鏈表—LinkedList

public class LinkedList<E> extends AbstractList<E> {

    /**
     * 定義鏈表第一結點，指向鏈表頭一個元素
     */
    private Node<E> first;

    /**
     * 定義結點類Node，包含元素和指向下一個結點的地址參考
     * @param <E>
     */
    private static class Node<E>{
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

    /**
     * 設定index位置的元素
     *
     * @param index
     * @param element
     * @return 原來的元素?
     */
    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    /**
     * 獲取index位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 查看元素的索引
     *
     * @param element
     * @return
     */
    @Override
    public int indexOf(E element) {
        //如果元素為空
        if (element == null){
            Node<E> node = first;
            for (int i = 0;i < size;i++){
                if (node.element == null) return i;
                node = node.next;
            }
        }else {
            //元素不為空
            Node<E> node = first;
            for (int i = 0;i < size;i++){
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        //查無此元素
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 在index位置插入一個元素
     *
     * @param index
     * @param element
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if (index == 0){
            first = new Node<>(element,first);
        }else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element,prev.next);
        }
        size++;
    }

    /**
     * 洗掉index位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node =first;
        if (index == 0){
            first = first.next;
        }else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

    /**
     * 洗掉指定元素
     *
     * @param element
     * @return
     */
    @Override
    public E remove(E element) {
        return remove(indexOf(element));
    }

    /**
     * 清除所有元素
     */
    @Override
    public void clear() {
        size = 0;
        first =null;
    }

    /**
     * 獲取index位置對應的結點物件
     * @param index
     * @return
     */
    private Node<E> node(int index){
        rangeCheck(index);

        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(node.element);

            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}

虛擬頭結點

概念

改進鏈表：創建帶有虛擬頭結點的鏈表

Why：有時候為了讓代碼更加精筒，統一所有節點的處理邏輯，可以在最前面增加一個虛擬的頭結點（不存盤資料）

類圖關系： 在繼承關系與抽象介面設計上，Virtual_LinkedList與LinkedList一樣，并未改動

結構設計

帶虛擬頭結點鏈表的結構

Virtual_LinkedList 鏈表類定義的屬性與方法

1、屬性

• private Node<E> first; —— 定義鏈表第一結點，指向鏈表頭一個元素

2、方法

• public Virtual_LinkedList() —— 構造方法，用于初始化創建虛擬頭結點

• E set(int index, E element); —— 設定index位置的元素

• E get(int index); —— 獲取index位置的元素

• int indexOf(E element); —— 查看元素的索引

• void add(int index, E element);—— 在index位置插入一個元素

• E remove(int index); —— 洗掉index位置的元素

• public E remove(E element); —— 洗掉指定元素

• void clear(); —— 清除所有元素

• private Node<E> node(int index) —— 獲取index位置對應的結點物件

方法變動

1、第一個需要變動的地方是增加構造方法public Virtual_LinkedList()，用于初始化創建虛擬頭結點

/**
 * 建構式，無論有無資料都要創建虛擬頭結點
 */
public Virtual_LinkedList() {

    first = new Node<>(null,null);
}

2、變動方法 — private Node<E> node(int index)

前面說到該方法是通過index索引對應的結點物件,是從索引為 0 的元素結點開始查找，現在是從虛擬頭結點開始遍歷查找，指標應該從first改為first.next,讓指標還是指向索引為 0 的元素結點

/**
 * 獲取index位置對應的結點物件
 * @param index
 * @return
 */
private Node<E> node(int index){
    rangeCheck(index);

    Node<E> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

3、變動方法 — public int indexOf(E element)，增加了頭結點，遍歷時應該從fiirst.next開始

/**
 * 查看元素的索引
 *
 * @param element
 * @return
 */
@Override
public int indexOf(E element) {
    //如果元素為空
    if (element == null){
        Node<E> node = first.next;
        for (int i = 0;i < size;i++){
            if (node.element == null) return i;
            node = node.next;
        }
    }else {
        //元素不為空
        Node<E> node = first.next;
        for (int i = 0;i < size;i++){
            if (element.equals(node.element)) return i;
            node = node.next;
        }
    }
    //查無此元素
    return ELEMENT_NOT_FOUND;
}

4、變動方法 — void add(int index, E element);

之前我們說到添加新結點的方法的思想，是要找到插入的索引位置的前一位置，再來改動指標指向，但是索引為 0 的位置，前面是沒有元素結點了，所以這種情況是不通用的，需要根據index == 0的情況分為兩種情況，但是有了虛擬頭結點，那就變成通用的了，同時也是精簡了代碼，統一所有結點的處理邏輯

/**
 * 在index位置插入一個元素
 *
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    //這里區分index = 0，是為了應對索引檢查函式，node(0 - 1)，-1是沒法通過檢查的，但是添加的邏輯是統一的
    Node<E> prev = (index == 0 ? first : node(index - 1));
    prev.next = new Node<>(element,prev.next);
    size++;
}

5、變動方法 — E remove(int index);同樣的，洗掉方法也是跟 add方法一樣，統一所有結點的處理邏輯

/**
 * 洗掉index位置的元素
 *
 * @param index
 * @return
 */
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node;
    Node<E> prev =(index == 0 ? first : node(index - 1));
    node = prev.next;
    prev.next = node.next;
    size--;
    return node.element;
}

雙向鏈表

概念

此前，我們在上面撰寫的都是單向鏈表，缺點是比較明顯的，每次是獲取結點元素都需要從頭結點開始遍歷，而使用雙向鏈表能有效的提升鏈表的綜合性能

類圖關系： 在繼承關系與抽象介面設計上，Both_LinkedList與LinkedList一樣，并未改動

雙向鏈表設計

/**
 * 定義鏈表尾結點指標，指向鏈表尾元素
 */
private Node<E> last;

/**
 * 定義結點類Node，包含元素和指向下一個結點的地址參考
 * @param <E>
 */
private static class Node<E>{
    E element;
    Node<E> prev;
    Node<E> next;

    public Node(Node<E> prev, E element, Node<E> next) {
        this.prev = prev;
        this.element = element;
        this.next = next;
    }
}

方法變動

1、變動方法 — private Node<E> node(int index)

此前的node方法，由于是單向鏈表，所以都是從頭開始遍歷尋找，現在是雙向鏈表，根據索引位于中間結點位置的前后，決定遍歷方向

/**
 * 獲取index位置對應的結點物件
 * @param index
 * @return
 */
private Node<E> node(int index){
    rangeCheck(index);

    //如果查找的元素在鏈表前半部分
    if (index < (size >> 1)) {
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
    //如果查找的元素在鏈表后半部分
        Node<E> node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }
}

2、變動方法 — void add(int index, E element);

/**
 * 在index位置插入一個元素
 *
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    //往最后面添加元素
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, null);
        //這是鏈表添加的第一個元素
        if (oldLast == null) {
            first = last;
        } else {
            oldLast.next = last;
        }
    } else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        //index == 0，往最前面添加
        if (prev == null) {
            first = node;
        } else {
            prev.next = node;
        }
    }
    size++;
}

按照 3 種情形分析，通用的插入于中間位置，插入index == 0頭部位置，和插入index == size尾部部位置

1、插入中間位置

2、插入頭部位置

3、插入尾部位置

這里需要注意的是，如果此時的雙向鏈表是空鏈表，那么尾部插入的就是第一個元素

3、變動方法 — E remove(int index);

事實上，移除結點元素也是跟上面的添加元素一樣，在這里就不畫圖做解釋了，讀一遍代碼不懂的話，可以看著雙向鏈表結構圖，讀或者DeBug一遍

/**
 * 洗掉index位置的元素
 *
 * @param index
 * @return
 */
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;

    // index == 0
    if (prev == null){
        first = next;
    }else {
        prev.next = next;
    }
    // index == size - 1 
    if (next == null){
        last = prev;
    }else {
        next.prev = prev;
    }
    size--;
    return node.element;
    
}

回圈鏈表

單向回圈鏈表

結構設計：

方法變動：

1、變動方法 — void add(int index, E element);

實際上，單向回圈鏈表只是在單向鏈表的基礎上，將尾結點的next指向頭結點，所以添加操作只需要注意往頭結點插入的情況改動方法就好，注意點有兩個，index == 0``size == 0

/**
 * 在index位置插入一個元素
 *
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == 0){
        first = new Node<>(element,first);
        Node<E> last =(size == 0) ? first : node(size - 1);
        last.next = first;

    }else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}

當size == 0,添加的操作就是下圖的樣子，同時當鏈表只有一個結點時，也是洗掉要注意的點

1、變動方法 — public E remove(int index);

/**
 * 洗掉index位置的元素
 *
 * @param index
 * @return
 */
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = first;
    if (index == 0) {
        if (size == 1) {
            first = null;
        } else {
            Node<E> last = node(size - 1);
            first = first.next;
            last.next = first;
        }
    } else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

雙向回圈鏈表

結構設計：

方法變動：

1、變動方法 — void add(int index, E element);

實際上，雙向回圈鏈表只是在雙鏈表的基礎上，將尾結點的next指向頭結點，頭結點的prev指向尾結點，所以其實很多都是不變的，我們只需要關注添加操作與洗掉操作就好了

/**
 * 在index位置插入一個元素
 *
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    //往最后面添加元素
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, first);
        //這是鏈表添加的第一個元素
        if (oldLast == null) {
            first = last;
            first.next = first;
            first.prev = first;
        } else {
            oldLast.next = last;
            first.prev = last;
        }
    } else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        prev.next = node;
        //index == 0，往最前面添加
        if (index == 0) {
            first = node;
        }
    }
    size++;
}

注意當size == 0，插入鏈表的頭結點指標指向如下

1、變動方法 — public E remove(int index);

/**
 * 洗掉index位置的元素
 *
 * @param index
 * @return
 */
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = first;
    if (size == 1){
        first = null;
        last = null;
    }else {
        node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        prev.next = next;
        next.prev = prev;

        // index == 0
        if (node == first){
            first = next;
        }
        // index == size - 1
        if (node == last){
            last = prev;
        }
    }
    size--;
    return node.element;

}

小結

單向鏈表 VS 雙向鏈表

粗略對比一下洗掉的運算元量：

相比之下，雙向鏈表的操作縮減了一半，但是其占用的記憶體空間也增加了

動態陣列 VS 鏈表

1、動態陣列：開辟、銷毀記憶體空間的次數相對較少，但可能造成記憶體空間浪費（可以通過縮容解決）
2、雙向鏈表：開辟、銷毀記憶體空間的次數相對較多，但不會造成記憶體空間的浪費

應用場景：

• 如果頻繁在尾部進行添加、洗掉操作，動態陣列、雙向鏈表均可選擇

• 如果頻繁在頭部進行添加、洗掉操作，建議選擇使用雙向鏈表

• 如果有頻繁的（在任意位置）添加、洗掉操作，建議選擇使用雙向鏈表

• 如果有頻繁的查詢操作（隨機訪問操作），建議選擇使用動態陣列

宣告

個人能力有限，有不正確的地方，還請指正

文章為原創，歡迎轉載，注明出處即可

本文的代碼已上傳github,歡迎star

GitHub地址

標籤：其他

上一篇：劍指offer題解（一） - JZ1 ~ JZ10

下一篇：重建二叉樹