線性數(shù)據(jù)結(jié)構(gòu)

鏈表 LinkList

鏈表的數(shù)據(jù)結(jié)構(gòu)

一組由節(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，每個元素指向下一個元素，是線性序列。

最簡單的鏈表結(jié)構(gòu)：

• 數(shù)據(jù)
• 指針（存放執(zhí)行下一個節(jié)點的指針）

不適合的場景：

• 需要循環(huán)遍歷將導(dǎo)致時間復(fù)雜度的提升

鏈表分類—單向鏈表

鏈表結(jié)構(gòu)：

• 數(shù)據(jù)
• 指針 Next（指向下一個節(jié)點）

鏈表分類-雙向列表

鏈表結(jié)構(gòu)：

• 數(shù)據(jù)
• 指針 Next(指向下一個節(jié)點)
• 指針 Prev（指向前一個節(jié)點）

鏈表分類-循環(huán)列表

鏈表結(jié)構(gòu)：

• 數(shù)據(jù)
• 指針 Next(指向下一個節(jié)點，最后一個節(jié)點指向第一個節(jié)點)

實現(xiàn)一個雙向鏈表

實現(xiàn)鏈表節(jié)點：

public class Node<E> {
    E item;
    Node<E> prev;
    Node<E> next;

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

在頭節(jié)點之前插入節(jié)點：

void insertNodeBeforeHead(E e){
final Node<E> oldHeadNode=head;
final Node<E> newHeadNode=new Node<E>(e,null,oldHeadNode);
        head=newHeadNode;
        if(oldHeadNode==null){
        // 說明原先鏈表中沒有元素
        tail=newHeadNode;
        }else{
        // 如果有元素，則需要改變頭節(jié)點的指針指向
        oldHeadNode.prev=newHeadNode;
        }
        size++;
        }

在尾節(jié)點之后插入節(jié)點：

void insertNodeAfterTail(E e){
final Node<E> oldTailNode=tail;
final Node<E> newTailNode=new Node<E>(e,oldTailNode,null);
        tail=newTailNode;
        if(oldTailNode==null){
        head=newTailNode;
        }else{
        oldTailNode.next=newTailNode;
        }
        size++;
        }

拆除鏈表：

E unlinkByNode(Node<E> node){
final E element=node.item;
final Node<E> prevNode=node.prev;
final Node<E> nextNode=node.next;
        // 改變前一個元素的next指針指向的元素
        if(prevNode==null){
        // 說明是頭節(jié)點
        head=nextNode;
        }else{
        prevNode.next=nextNode;
        node.prev=null;
        }
        // 改變后一個元素的prev指針指向的元素
        if(nextNode==null){
        // 說明是尾節(jié)點，沒有下一個元素
        tail=prevNode;
        }else{
        nextNode.prev=prevNode;
        node.next=null;
        }

        size--;
        node.item=null;
        return null;
        }

移除元素：

 public boolean removeNodeByElement(E e){
        if(e==null){
        for(Node<E> start=head;start!=null;start=start.next){
        if(start.item==null){
        unlinkByNode(start);
        return true;
        }
        }
        }else{
        for(Node<E> start=head;start!=null;start=start.next){
        if(start.item.equals(e)){
        unlinkByNode(start);
        return true;
        }
        }
        }
        return false;
        }

LinkedList 源碼解讀

繼承關(guān)系

關(guān)鍵屬性

    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

其中節(jié)點 Node 的數(shù)據(jù)結(jié)構(gòu)如下，是 LinkedList 的內(nèi)部類：

 private static class Node<E> {
    E item; // 存儲數(shù)據(jù)
    Node<E> next; // 指向下一個節(jié)點
    Node<E> prev; // 指向前一個節(jié)點

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

transient 的作用

首先，需要理解 Java 中序列化和反序列化的作用：

• 序列化：將內(nèi)存中的對象信息轉(zhuǎn)化為二進制數(shù)組的方法，可以將數(shù)組保存和傳輸，然后使用原來的類模板恢復(fù)對象的信息。
• 反序列化：使用原來的類模板將序列化后的二進制數(shù)組恢復(fù)為 Java 對象。

如何實現(xiàn)序列化和反序列化：

• 實現(xiàn) Serializable 接口：
  • 寫對象信息：ObjectOutputStream.writeObject(Object object)，該方法會判斷 object 是否重寫了 writeObject
    方法，如果重寫了，則通過反射調(diào)用重寫后的方法，完成序列化
  • 讀對象信息：ObjectInputStream.readObject()

什么情況下不需要序列化：

• 節(jié)省空間，去除部分無用的屬性
• 持有對象的引用（對象在內(nèi)存中的地址值）

LinkedList 將 first 和 last 修飾成 transient 的原因：

• 節(jié)省空間
• 重新連接鏈表：結(jié)點中保存前驅(qū)和后繼的引用，序列化之后前序結(jié)點和后繼結(jié)點的地址發(fā)生了改變，需要連接新的節(jié)點。

writeObject && readObject

LinkedList 重寫了 writeObject 和 readObject 方法，自定義了序列化和反序列化的過程，用于重新鏈接節(jié)點：

序列化：writeObject

/**
 * Saves the state of this {@code LinkedList} instance to a stream
 * (that is, serializes it).
 *
 * @serialData The size of the list (the number of elements it
 *             contains) is emitted (int), followed by all of its
 *             elements (each an Object) in the proper order.
 */
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out any hidden serialization magic 調(diào)用默認的序列化方法
        s.defaultWriteObject();

        // Write out size 指定序列化的容量，單位：32 bit int
        s.writeInt(size);

        // Write out all elements in the proper order.
        // 只把結(jié)點中的值序列化，前序和后繼的引用不序列化
        for(Node<E> x=first;x!=null;x=x.next)
        s.writeObject(x.item);
        }

反序列化：readObject

/**
 * Reconstitutes this {@code LinkedList} instance from a stream
 * (that is, deserializes it).
 */
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException,ClassNotFoundException{
        // Read in any hidden serialization magic 用默認的反序列化方法
        s.defaultReadObject();

        // Read in size 指定讀的容量
        int size=s.readInt();

        // Read in all elements in the proper order.
        // 讀取每一個結(jié)點保存的值，創(chuàng)建新結(jié)點，重新連接鏈表。
        for(int i=0;i<size; i++)
        linkLast((E)s.readObject()); // linkLast是向鏈表中的尾部插入節(jié)點的方法
        }

向鏈表的最后一個節(jié)點插入元素值為 e 的節(jié)點：linkLast(E e)

核心流程：

• 拿到當前的尾節(jié)點，記為 l
• 使用需要創(chuàng)建的元素 e 創(chuàng)建一個新的節(jié)點 newNode，prev 屬性為 l 節(jié)點，next 屬性為 null
• 將當前尾節(jié)點設(shè)置為上面新創(chuàng)建的節(jié)點 newNode
• 如果 l 節(jié)點為空則代表當前鏈表為空, 將 newNode 設(shè)置為頭結(jié)點，否則將 l 節(jié)點的 next 屬性設(shè)置為 newNode

    /**
 * 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;
        if(l==null)
        first=newNode;
        else
        l.next=newNode;
        size++;
        modCount++;
        }

向指定節(jié)點前插入元素值為 e 的節(jié)點: linkBefore(E e, Node succ)

核心流程：

• 拿到 succ 節(jié)點的 prev 節(jié)點
• 使用 e 創(chuàng)建一個新的節(jié)點 newNode，其中 prev 屬性為 pred 節(jié)點，next 屬性為 succ 節(jié)點
• 將 succ 節(jié)點的 prev 屬性設(shè)置為 newNode
• 如果 pred 節(jié)點為 null，則代表 succ 節(jié)點為頭結(jié)點，要把 e 插入 succ 前面，因此將 first 設(shè)置為 newNode，否則將 pred 節(jié)點的 next 屬性設(shè)為 newNode

    /**
 * Inserts element e before non-null Node succ.
 */
    void linkBefore(E e,Node<E> succ){
// assert succ != null;
final Node<E> pred=succ.prev;
final Node<E> newNode=new Node<>(pred,e,succ);
        succ.prev=newNode;
        if(pred==null)
        first=newNode;
        else
        pred.next=newNode;
        size++;
        modCount++;
        }

移除鏈接上的節(jié)點 x（取消鏈接 x）：E unlink(Node x)

核心流程：

• 定義 element 為 x 節(jié)點的值，next 為 x 節(jié)點的下一個節(jié)點，prev 為 x 節(jié)點的上一個節(jié)點
• 如果 prev 為空，則代表 x 節(jié)點為頭結(jié)點，則將 first 指向 next 即可；否則，x 節(jié)點不為頭結(jié)點，將 prev 節(jié)點的 next 屬性指向 x 節(jié)點的 next 屬性，并將 x 的 prev 屬性清空
• 如果 next 為空，則代表 x 節(jié)點為尾節(jié)點，則將 last 指向 prev 即可；否則，x 節(jié)點不為尾節(jié)點，將 next 節(jié)點的 prev 屬性指向 x 節(jié)點的 prev 屬性，并將 x 的 next 屬性清空
• 將 x 的 item 屬性清空，以便垃圾收集器回收 x 對象

    /**
 * Unlinks non-null node x.
 */
    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=next;
        }else{
        prev.next=next;
        x.prev=null;
        }

        if(next==null){
        last=prev;
        }else{
        next.prev=prev;
        x.next=null;
        }

        x.item=null;
        size--;
        modCount++;
        return element;
        }

插入元素：add

默認插入方法，尾部插入：boolean add(E e)

直接插入鏈表尾部

    /**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e){
        linkLast(e);
        return true;
        }

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

流程：

• 檢查索引 index 是否越界（只要用到了索引 index，都會判斷是否越界）
• 如果索引 index 和鏈表當前的長度 size 相同，則執(zhí)行尾部插入
• 否則，將 element 插入原 index 位置節(jié)點的前面

    /**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index,E element){
        checkPositionIndex(index);

        if(index==size)
        linkLast(element);
        else
        linkBefore(element,node(index));
        }

獲取節(jié)點：get

核心流程：

• 根據(jù) index，調(diào)用 node 方法,尋找目標節(jié)點，返回目標節(jié)點的 item。

    /**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index){
        checkElementIndex(index);
        return node(index).item;
        }

根據(jù)指定索引 index 位置查找節(jié)點

核心流程：

• 如果 index 的長度是鏈表長度的一半，則在鏈表前半部分，從頭節(jié)點開始遍歷
• 否則，從尾節(jié)點開始遍歷

    /**
 * Returns the (non-null) Node at the specified element index.
 */
    Node<E> node(int index){
        // assert isElementIndex(index);

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

替換指定位置的元素：set

核心流程：

• 調(diào)用 node 方法尋找到目標節(jié)點
• 將目標節(jié)點的 item 屬性，替換為目標元素

    /**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index,E element){
        checkElementIndex(index);
        Node<E> x=node(index);
        E oldVal=x.item;
        x.item=element;
        return oldVal;
        }

移除節(jié)點

移除指定元素的節(jié)點：boolean remove(Object o)

核心流程：

• 因為普通元素值和 null 判斷存在區(qū)別，所以需要判斷 o 是否為 null，如果 o 為 null，則遍歷鏈表尋找 item 屬性為空的節(jié)點，并調(diào)用 unlink 方法將該節(jié)點移除
• 否則，遍歷鏈表尋找 item 屬性跟 o 相同的節(jié)點，并調(diào)用 unlink 方法將該節(jié)點移除。

    /**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
public boolean remove(Object o){
        if(o==null){
        for(Node<E> x=first;x!=null;x=x.next){
        if(x.item==null){
        unlink(x);
        return true;
        }
        }
        }else{
        for(Node<E> x=first;x!=null;x=x.next){
        if(o.equals(x.item)){
        unlink(x);
        return true;
        }
        }
        }
        return false;
        }

移除指定索引位置的節(jié)點：remove(int index)

核心流程：

• 調(diào)用 unlink 方法，移除 index 位置的節(jié)點

    /**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index){
        checkElementIndex(index);
        return unlink(node(index));
        }

清除鏈表中的所有元素：clear

從 first 節(jié)點開始遍歷，將所有的節(jié)點的 item、next、prev 值設(shè)置為 null。

    public void clear(){
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        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++;
        }

question

1. 描述鏈表的數(shù)據(jù)結(jié)構(gòu)
2. Java 中的 LinkedList 的數(shù)據(jù)結(jié)構(gòu)和原理

Node 的源碼：

• 有 Next 指針、Prev 指針，說明是雙向鏈表
  

LinkedList 的 linkLast 向尾元素后插入元素的方法源碼：

• 尾元素的 prev 指針沒有指向頭元素，說明非循環(huán)
  

結(jié)論：非循環(huán)雙向鏈表

3. 鏈表中數(shù)據(jù)的插入、刪除和獲取的時間復(fù)雜度分析

獲?。篛(n)
插入：

• 有前置節(jié)點（頭尾插入）：O(1)
• 無前置節(jié)點：O(n)

4. 什么場景下更適合使用鏈表

在不確定數(shù)據(jù)量且需要頻繁插入和刪除操作的場景下。

leetcode 題目

707 設(shè)計鏈表

707 設(shè)計鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-662180.html

到了這里，關(guān)于Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)和源碼閱讀（線性數(shù)據(jù)結(jié)構(gòu)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！