LinkedList

[TOC]

一、頂部注釋分析

1.1 首句定義

  • Doubly-linked list implementation of the List and Deque interfaces
  • LinkedList 是 List 接口和 Deque 接口的雙向鏈表實(shí)現(xiàn)

1.2 從注釋中得到的結(jié)論

  • permits all elements (including null)：LinkList 允許null元素
  • All of the operations perform as could be expected for a doubly-linked：所有的操作都針對(duì)雙向鏈表
  • Note that this implementation is not synchronized：LinkedList不是線程安全的
  • Collections.synchronizedList方法可以實(shí)現(xiàn)線程安全的操作
  • 由 iterator() 和 listIterator() 返回的迭代器是 fail-fast 的

二、源碼分析

2.1 定義

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  • LinkedList<E>：說(shuō)明它支持泛型。
  • extends AbstractSequentialList<E>：繼承自 AbstractSequentialList， 只支持按次序訪問(wèn)
  • implements List<E>：實(shí)現(xiàn)了 List 接口
  • implements Deque<E>：Deque，Double ended queue，雙端隊(duì)列。LinkedList可用作隊(duì)列或雙端隊(duì)列就是因?yàn)閷?shí)現(xiàn)了它。
  • implements Cloneable：可以調(diào)用 clone() 方法來(lái)返回實(shí)例的 field-for-field 拷貝
  • implements java.io.Serializable：具有序列化功能
  • 沒有實(shí)現(xiàn) RandomAccess 接口，因此不像 ArrayList 一樣支持快速隨機(jī)訪問(wèn)

2.2 字段

// LinkedList節(jié)點(diǎn)個(gè)數(shù)
transient int size = 0;

// 指向頭節(jié)點(diǎn)的指針
transient Node<E> first;

// 指向尾節(jié)點(diǎn)的指針
transient Node<E> 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;
    }
}

2.3 構(gòu)造方法

  1. public LinkedList() {}：構(gòu)造一個(gè)空鏈表
  2. public LinkedList(Collection<? extends E> c)：根據(jù)指定集合構(gòu)造LinkedList。步驟為先構(gòu)造一個(gè)空Linkedlist，再把指定集合中的所有元素都添加到LinkedList中

2.4 添加元素

  • add 方法實(shí)際上會(huì)調(diào)用 linkLast 方法，即在鏈表最后添加元素
public boolean add(E e) 
{
    linkLast(e);
    return true;
}

void linkLast(E e) 
{
    // 使節(jié)點(diǎn)l指向原來(lái)的尾結(jié)點(diǎn)
    final Node<E> l = last; 
    
    //新建節(jié)點(diǎn)newNode，節(jié)點(diǎn)的前指針指向l，后指針為null
    final Node<E> newNode = new Node<>(l, e, null); 
    
    // 尾指針指向新的頭節(jié)點(diǎn)newNode
    last = newNode;
    
    // 如果原來(lái)的尾結(jié)點(diǎn)為null，更新頭指針，否則將原來(lái)尾結(jié)點(diǎn)的后指針指向新節(jié)點(diǎn)newNode，構(gòu)成雙向
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

2.5 get、set、remove

  • 三者中都調(diào)用了 node(index) 方法，用于返回在指定索引處的非空元素
  • 在查找時(shí)有一個(gè)優(yōu)化點(diǎn)是：若 index 小于總長(zhǎng)度的一半，則從頭開始遍歷；否則從尾開始遍歷 
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;
    }
}
  • get先檢測(cè)范圍，然后找到指定元素
public E get(int index) 
{
    checkElementIndex(index);
    return node(index).item;
}
  • set先檢測(cè)范圍，然后找到指定元素替換，并返回舊值
public E set(int index, E element) 
{
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
  • remove先檢測(cè)范圍，然后找到指定元素更新連接，并返回舊值
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 = 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;
}

2.6 隊(duì)列操作（添加、刪除、獲?。?/h3>
  • 總結(jié)：
    1. 常用的插入、刪除、獲取方法都存在兩種形式：在操作失敗時(shí)，一種拋出異常，另一種返回一個(gè)特殊值（null 或 false，具體取決于操作）
    2. 其中插入操作的 offer 方法是用于專門為有容量限制的 Queue 實(shí)現(xiàn)設(shè)計(jì)的
  • 添加元素：offer 和 add，實(shí)際上 offer 內(nèi)部就是調(diào)用了 add ()，但是兩者的區(qū)別為：
方法 操作失敗時(shí)的處理方式 來(lái)源
add 拋出異常，如隊(duì)列滿拋出IllegalStateException Collection接口
offer 不拋出異常，只是返回 false Queue接口 
public boolean offer(E e) 
{
    return add(e);
}

public boolean add(E e) 
{
    linkLast(e);
    return true;
}
  • 刪除頭部元素：poll 和 remove，兩者最終調(diào)用的都是 unlinkFirst(f)，但是兩者的區(qū)別為：
方法 操作失敗時(shí)的處理方式
remove 若頭部元素為空會(huì)拋出NoSuchElementException
poll 不拋出異常，只是返回 null 
public E poll() 
{
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E remove() 
{
    return removeFirst();
}

public E removeFirst() 
{
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
  • 獲取頭部元素：element 和 peek，兩者最終都是訪問(wèn) f.item，但是兩者的區(qū)別為：
方法 操作失敗時(shí)的處理方式
element 若頭部元素為空會(huì)拋出NoSuchElementException
peek 不拋出異常，只是返回 null 
public E peek() 
{
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E element() 
{
    return getFirst();
}

public E getFirst() 
{
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

2.7 棧操作（入棧、出棧、獲取棧頂）

  • 具體實(shí)現(xiàn)方式和隊(duì)列類似，當(dāng)利用LinkedList實(shí)現(xiàn)棧時(shí)使用
public void push(E e) 
{
    addFirst(e);
}

public E pop() 
{
    return removeFirst();
}

public E peek() 
{
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容