連結清單之LinkedList

寫在前面

在日常開發中，一般在對于List的場景，基本上都是通過ArrayList去封裝資料的，而對于連結清單LinkedList相對來說用的比較少。對我而言，好像ArrayList熟練度高一些，是以基本上也很少用LinkedList，也就是在面試的時候去背過八股文。

連結清單：資料分散的存儲在實體空間中，通過一根線儲存着它們之間的邏輯關系，這種存儲結構稱為鍊式存儲結構，簡稱連結清單。

連結清單的前驅和後繼

資料結構中，一組資料中的每個個體被稱為“資料元素”（簡稱“元素”）。

另外，對于具有“一對一”邏輯關系的資料，我們一直在用“某一進制素的左側（前邊）或右側（後邊）”這樣不專業的詞，其實線性表中有更準确的術語：

某一進制素的左側相鄰元素稱為“直接前驅”，位于此元素左側的所有元素都統稱為“前驅元素”；
某一進制素的右側相鄰元素稱為“直接後繼”，位于此元素右側的所有元素都統稱為“後繼元素”；

連結清單之LinkedList

單連結清單

概念：單連結清單，用于存儲邏輯關系為 "一對一" 的資料。與順序表不同，連結清單不限制資料的實體存儲狀态，換句話說，使用連結清單存儲的資料元素，其實體存儲位置是随機的。HashMap在1.7就是通過單連結清單來解決hash沖突的。

節點

在上圖中無法提現出元素之間的邏輯關系，對此，連結清單的解決方案是，每個資料元素在存儲時都配備一個指針，用于指向自己的直接後繼元素。表示一個節點如下：

//節點資訊
class Node {
    E data;
    Node next;

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

    public Node(E data) {
        this.data = data;
    }
}

是以，在連結清單中，每個資料的存儲有以下2部分組成

資料本身，其所在的區域叫做資料域
指向後繼元素的指針，叫指針域

連結清單之LinkedList

上圖所示的結構在連結清單中稱為節點。也就是說，連結清單實際存儲的是一個一個的節點，真正的資料元素包含在這些節點中

單連結清單---增

/**
  * 頭部添加節點
  *
  * @param e
  */
 public void add(E e) {
     //頭結點
     Node cur = new Node(e, list);
     list = cur;
     size++;
 }

 /**
   * 指定位置添加節點
   *
   * @param index
   * @param e     0 1 2 3 4
   */
 public void add(int index, E e) {
 	  //越界檢查
     checkElementIndex(index);
     Node preNode = list;
     for (int i = 0; i < index - 1; i++) {
         //找到插入位置的前一個節點
         preNode = preNode.next;
     }
     Node node = new Node(e);
     node.next = preNode.next;
     preNode.next = node;
     size++;
 }

單連結清單---删

/**
 * 删除頭部節點
 */
public void remove() {
    if (list != null) {
        Node node = list;
        list = node.next;
        //GC
        node.next = null;
        size--;
    }
}

/**
 * 删除指定位置節點
 * 1 2 3 4 5
 * 0 1 2 3 4
 *
 * @param index
 */
public void remove(int index) {
    checkElementIndex(index);
    Node preNode = list;
    for (int i = 0; i < index - 1; i++) {
        //找到指定位置元素的前一個節點
        preNode = preNode.next;
    }
    //指定位置的節點
    Node next = preNode.next;
    preNode.next = next.next;
    //GC
    next = null;
    size--;
}

/**
 * 删除最後一個節點
 */
public void removeLast() {
    if (list != null) {
        //目前節點
        Node cur = list;
        //最後一個節點的前一個節點
        Node preNode = list;
        while (cur.next != null) {
            preNode = cur;
            cur = cur.next;
        }
        preNode = null;//此時cur已經為null
        size--;
    }
}

單連結清單---改

/**
 * 修改指定索引的元素
 *
 * @param index
 * @param e
 */
public void set(int index, E e) {
    checkElementIndex(index);
    Node cur = list;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.data = e;
}

單連結清單---查

/**
  * 擷取頭部節點
  */
 public E get() {
     if (list != null) {
         return list.data;
     } else {
         return null;
     }
 }

  /**
   * 擷取指定位置的元素
   *
   * @param index
   * @return
   */
  public E get(int index) {
      checkElementIndex(index);
      Node cur = list;
      for (int i = 0; i < index; i++) {
          cur = cur.next;
      }
      return cur.data;
  }

完整代碼

/**
 * 單連結清單
 *
 */
public class SingleLinkedList<E> {

    int size = 0;

    /**
     * 指向第一個節點的指針
     */
    Node list;

    /**
     * 頭部添加節點
     *
     * @param e
     */
    public void add(E e) {
        //頭結點
        Node cur = new Node(e, list);
        list = cur;
        size++;
    }

    /**
     * 指定位置添加節點
     *
     * @param index
     * @param e     0 1 2 3 4
     */
    public void add(int index, E e) {
        checkElementIndex(index);
        Node preNode = list;
        for (int i = 0; i < index - 1; i++) {
            //找到插入位置的前一個節點
            preNode = preNode.next;
        }
        Node node = new Node(e);
        node.next = preNode.next;
        preNode.next = node;
        size++;
    }


    /**
     * 删除頭部節點
     */
    public void remove() {
        if (list != null) {
            Node node = list;
            list = node.next;
            //GC
            node.next = null;
            size--;
        }
    }

    /**
     * 删除指定位置節點
     * 1 2 3 4 5
     * 0 1 2 3 4
     *
     * @param index
     */
    public void remove(int index) {
        checkElementIndex(index);
        Node preNode = list;
        for (int i = 0; i < index - 1; i++) {
            //找到指定位置元素的前一個節點
            preNode = preNode.next;
        }
        //指定位置的節點
        Node next = preNode.next;
        preNode.next = next.next;
        //GC
        next = null;
        size--;
    }

    /**
     * 删除最後一個節點
     */
    public void removeLast() {
        if (list != null) {
            //目前節點
            Node cur = list;
            //最後一個節點的前一個節點
            Node preNode = list;
            while (cur.next != null) {
                preNode = cur;
                cur = cur.next;
            }
            preNode = null;//此時cur已經為null
            size--;
        }
    }

    /**
     * 修改指定索引的元素
     *
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        checkElementIndex(index);
        Node cur = list;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.data = e;
    }

    /**
     * 擷取頭部節點
     */
    public E get() {
        if (list != null) {
            return list.data;
        } else {
            return null;
        }
    }

    /**
     * 擷取指定位置的元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        checkElementIndex(index);
        Node cur = list;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.data;
    }


    class Node {
        E data;
        Node next;

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

        public Node(E data) {
            this.data = data;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 判斷參數是否為現有元素的索引  即邊界
     *
     * @param index
     */
    private void checkElementIndex(int index) {
        if (!(index >= 0 && index < size))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    @Override
    public String toString() {
        Node node = list;
        for (int i = 0; i < size; i++) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        return super.toString();
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.add(5);
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
        list.toString();
        System.out.println();
        list.add(2, 5);
        list.toString();
        list.removeLast();
        System.out.println();
        list.toString();
        list.set(1, 1);
        System.out.println();
        list.toString();
        System.out.println();
        System.out.println(list.get());
    }
}

雙連結清單LinkedList源碼分析

雙連結清單，指各節點之間的邏輯關系是雙向的。

是以，在雙向連結清單中各節點包含以下 3 部分資訊

指針域：用于指向目前節點的直接前驅節點；
資料域：用于存儲資料元素。
指針域：用于指向目前節點的直接後繼節點；

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 void add(int index, E element) {
    checkPositionIndex(index);
	//如果索引和size相等直接尾部插入
    if (index == size)
    	linkLast(element);
    else
    	linkBefore(element, node(index));
}


/**
 * first 指向第一個節點的指針
 * @param e 要插入的元素
 * @param succ index位置的節點
 *  a1        a3
 * 在a3索引出插入新的元素  a2
 *  a1    a2    a3
 */
void linkBefore(E e, Node<E> succ) {
    // succ：原a3的前置節點a1
    final Node<E> pred = succ.prev;
    //pred(a1) e(a2) succ(a3)形成新的節點
    //即把e(a2)prev指向pred(a1)節點，把e(a2)next指向succ(a3)節點
    final Node<E> newNode = new Node<>(pred, e, succ);
    //把succ(a3)的prev指向新的節點newNode
    succ.prev = newNode;
    //pred為空代表newNode為首節點
    if (pred == null)
    	first = newNode;
    else
    	//a1的next節點由a3變為a2
    	pred.next = newNode;
    size++;
    modCount++;
}

雙連結清單---删

public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));    }/** * Unlinks non-null node x. */ E unlink(Node<E> x) {     // assert x != null;     //擷取該節點的值     final E element = x.item;     //擷取該節點的next節點     final Node<E> next = x.next;     //擷取該節點的prev節點     final Node<E> prev = x.prev;     //把該節點的前節點的next指向該節點的next節點，并清除該節點的prev指向     if (prev == null) {     	first = next;     } else {     	prev.next = next;     	x.prev = null;     }     //把該節點的next節點的prev指向該節點的prev節點，并清除該節點的next指向     if (next == null) {     	last = prev;     } else {     	next.prev = prev;     	x.next = null;     }     x.item = null;//gc清除     size--;     modCount++;     return element; }

總結

前面講過ArrayList源碼分析及擴容機制,如果你看了應該知道不管是用ArrayList還是LinkedList主要是看場景，LinkedList增删快，因為隻用調整指向即可，對于ArrayList而言卻要移動整個數組，但是如果說是在尾部插入的話，使用兩者都可以。而查找和修改卻要ArrayList隻需要知道下标即可，而對于LinkedList卻要通過循環查找。

對于LinkendList，其中還有很多方法，例如addFirst，addLast，remove等，如果你學會了單連結清單，其實雙連結清單也是一樣的，主要在于思維。

參考

線性表詳解

拓展延伸

ArrayList和LinkedList有什麼差別？

什麼時候用ArrayList,什麼時候用LinkedList？

連結清單之LinkedList

寫在前面

連結清單的前驅和後繼

單連結清單

節點

單連結清單---增

單連結清單---删

單連結清單---改

單連結清單---查

雙連結清單LinkedList源碼分析

類的繼承關系

雙連結清單---增

雙連結清單---删

總結

參考

拓展延伸

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器