自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

LinkedList 源碼分析，你想知道的都在這里

作者：PlayInJava
開發(fā) 后端
LinkedList是一種可以在任何位置進(jìn)行高效地插入和移除操作的有序序列，它是基于雙向鏈表實(shí)現(xiàn)的，是線程不安全的，允許元素為null的雙向鏈表。

概述

LinkedList是一種可以在任何位置進(jìn)行高效地插入和移除操作的有序序列，它是基于雙向鏈表實(shí)現(xiàn)的，是線程不安全的，允許元素為null的雙向鏈表。

源碼分析

變量

/**
 * 集合元素?cái)?shù)量
 **/
transient int size = 0;

/**
 * 指向第一個(gè)節(jié)點(diǎn)的指針
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向最后一個(gè)節(jié)點(diǎn)的指針
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

構(gòu)造方法

/**
 * 無參構(gòu)造方法
 */
public LinkedList() {
}

/**
 * 將集合c所有元素插入鏈表中
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Node節(jié)點(diǎn)

private static class Node<E> {
    // 值
    E item;
    // 后繼
    Node<E> next;
    // 前驅(qū)
    Node<E> prev;

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

因?yàn)橐粋€(gè)Node既有prev也有next,所以證明它是一個(gè)雙向鏈表。

添加元素

addAll(Collection c)

將集合c添加到鏈表，如果不傳index，則默認(rèn)是添加到尾部。如果調(diào)用addAll(int index, Collection c)方法，則添加到index后面。

/**
 * 將集合添加到鏈尾
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/** 
 * 
 */
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    // 拿到目標(biāo)集合數(shù)組
    Object[] a = c.toArray();
    //新增元素的數(shù)量
    int numNew = a.length;
    //如果新增元素?cái)?shù)量為0，則不增加，并返回false
    if (numNew == 0)
        return false;
    
    //定義index節(jié)點(diǎn)的前置節(jié)點(diǎn)，后置節(jié)點(diǎn)
    Node<E> pred, succ;
    // 判斷是否是鏈表尾部，如果是：在鏈表尾部追加數(shù)據(jù)
    //尾部的后置節(jié)點(diǎn)一定是null，前置節(jié)點(diǎn)是隊(duì)尾
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 如果不在鏈表末端(而在中間部位)
        // 取出index節(jié)點(diǎn)，并作為后繼節(jié)點(diǎn)
        succ = node(index);
        // index節(jié)點(diǎn)的前節(jié)點(diǎn) 作為前驅(qū)節(jié)點(diǎn)
        pred = succ.prev;
    }

    // 鏈表批量增加，是靠for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點(diǎn)操作
    for (Object o : a) {
        @SuppressWarnings("unchecked") 
        // 類型轉(zhuǎn)換
        E e = (E) o;
        // 前置節(jié)點(diǎn)為pred，后置節(jié)點(diǎn)為null，當(dāng)前節(jié)點(diǎn)值為e的節(jié)點(diǎn)newNode
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果前置節(jié)點(diǎn)為空， 則newNode為頭節(jié)點(diǎn)，否則為pred的next節(jié)點(diǎn)
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    // 循環(huán)結(jié)束后，如果后置節(jié)點(diǎn)是null，說明此時(shí)是在隊(duì)尾追加的
    if (succ == null) {
        // 設(shè)置尾節(jié)點(diǎn)
        last = pred;
    } else {
    //否則是在隊(duì)中插入的節(jié)點(diǎn) ，更新前置節(jié)點(diǎn) 后置節(jié)點(diǎn)
        pred.next = succ;
        succ.prev = pred;
    }

    // 修改數(shù)量size
    size += numNew;
    //修改modCount
    modCount++;
    return true;
}
/**
  * 取出index節(jié)點(diǎn)
  */ 
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果index 小于 size/2,則從頭部開始找
    if (index < (size >> 1)) {
        // 把頭節(jié)點(diǎn)賦值給x
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            // x=x的下一個(gè)節(jié)點(diǎn)
            x = x.next;
        return x;
    } else {
        // 如果index 大與等于 size/2，則從后面開始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
// 檢測(cè)index位置是否合法
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 檢測(cè)index位置是否合法
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

假設(shè)我們要在index=2處添加{1,2}到鏈表中，圖解如下：

第一步：拿到index=2的前驅(qū)節(jié)點(diǎn) prev=ele1。

第二步：遍歷集合prev.next=newNode，并實(shí)時(shí)更新prev節(jié)點(diǎn)以便下一次。
遍歷:prev=newNode

第三步：將index=2的節(jié)點(diǎn)ele2接上:prev.next=ele2,ele2.prev=prev。

注意node(index)方法:尋找處于index的節(jié)點(diǎn)，有一個(gè)小優(yōu)化，結(jié)點(diǎn)在前半段則從頭開始遍歷，在后半段則從尾開始遍歷，這樣就保證了只需要遍歷最多一半結(jié)點(diǎn)就可以找到指定索引的結(jié)點(diǎn)。

addFirst(E e)方法

將e元素添加到鏈表并設(shè)置其為頭節(jié)點(diǎn)(first)。

public void addFirst(E e) {
    linkFirst(e);
}

//將e鏈接成列表的第一個(gè)元素
private void linkFirst(E e) {

    final Node<E> f = first;
    // 前驅(qū)為空，值為e，后繼為f
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    //若f為空，則表明列表中還沒有元素，last也應(yīng)該指向newNode
    if (f == null)
        last = newNode;
    else
    //否則，前first的前驅(qū)指向newNode
        f.prev = newNode;
    size++;
    modCount++;
}
  • 拿到first節(jié)點(diǎn)命名為f。
  • 新創(chuàng)建一個(gè)節(jié)點(diǎn)newNode設(shè)置其next節(jié)點(diǎn)為f節(jié)點(diǎn)。
  • 將newNode賦值給first。
  • 若f為空，則表明列表中還沒有元素，last也應(yīng)該指向newNode；否則，前first的前驅(qū)指向newNode。

addLast(E e)方法

將e元素添加到鏈表并設(shè)置其為尾節(jié)點(diǎn)(last)。

public void addLast(E e) {
    linkLast(e);
}
/**
 * 將e鏈接成列表的last元素
 */
void linkLast(E e) {
    final Node<E> l = last;
    // 前驅(qū)為前l(fā)ast，值為e，后繼為null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    //最后一個(gè)節(jié)點(diǎn)為空，說明列表中無元素
    if (l == null)
        //first同樣指向此節(jié)點(diǎn)
        first = newNode;
    else
        //否則，前l(fā)ast的后繼指向當(dāng)前節(jié)點(diǎn)
        l.next = newNode;
    size++;
    modCount++;
}

過程與linkFirst()方法類似，這里略過。

add(E e)方法

在尾部追加元素e。

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    // 前驅(qū)為前l(fā)ast，值為e，后繼為null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    //最后一個(gè)節(jié)點(diǎn)為空，說明列表中無元素
    if (l == null)
        //first同樣指向此節(jié)點(diǎn)
        first = newNode;
    else
        //否則，前l(fā)ast的后繼指向當(dāng)前節(jié)點(diǎn)
        l.next = newNode;
    size++;
    modCount++;
}

add(int index, E element)方法

在鏈表的index處添加元素element.

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
/**
 * 在succ節(jié)點(diǎn)前增加元素e(succ不能為空)
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 拿到succ的前驅(qū)
    final Node<E> pred = succ.prev;
    // 新new節(jié)點(diǎn)：前驅(qū)為pred，值為e，后繼為succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 將succ的前驅(qū)指向當(dāng)前節(jié)點(diǎn)
    succ.prev = newNode;
    // pred為空，說明此時(shí)succ為首節(jié)點(diǎn)
    if (pred == null)
        // 指向當(dāng)前節(jié)點(diǎn)
        first = newNode;
    else
        // 否則，將succ之前的前驅(qū)的后繼指向當(dāng)前節(jié)點(diǎn)
        pred.next = newNode;
    size++;
    modCount++;
}

linkLast方法上文有講。
linkBefore(E e, Node<E> succ)方法步驟：

  • 拿到succ的前驅(qū)節(jié)點(diǎn)。
  • 新new節(jié)點(diǎn)：前驅(qū)為pred，值為e，后繼為succ : Node<>(pred, e, succ)。
  • 將succ的前驅(qū)指向當(dāng)前節(jié)點(diǎn)。
  • pred為空，說明此時(shí)succ為首節(jié)點(diǎn),first指向當(dāng)前節(jié)點(diǎn);否則，將succ之前的前驅(qū)的后繼指向當(dāng)前節(jié)點(diǎn)。

5、獲取/查詢?cè)?/h2>

get(int index)方法

根據(jù)索引獲取鏈表中的元素。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 檢測(cè)index合法性
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 根據(jù)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;
    }
}

node方法上文有詳細(xì)講解，這里不做介紹。

getFirst()方法

獲取頭節(jié)點(diǎn)。

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

getLast()方法

獲取尾節(jié)點(diǎn)。

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

6、刪除元素

remove(Object o)

根據(jù)Object對(duì)象刪除元素。

public boolean remove(Object o) {
    // 如果o是空
    if (o == null) {
        // 遍歷鏈表查找 item==null 并執(zhí)行unlink(x)方法刪除
        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;
}

E unlink(Node<E> x) {
    // assert x != null;
    // 保存x的元素值
    final E element = x.item;
    //保存x的后繼
    final Node<E> next = x.next;
    //保存x的前驅(qū)
    final Node<E> prev = x.prev;

    //如果前驅(qū)為null，說明x為首節(jié)點(diǎn)，first指向x的后繼
    if (prev == null) {
        first = next;
    } else {
        //x的前驅(qū)的后繼指向x的后繼，即略過了x
        prev.next = next;
        // x.prev已無用處，置空引用
        x.prev = null;
    }

    // 后繼為null，說明x為尾節(jié)點(diǎn)
    if (next == null) {
        // last指向x的前驅(qū)
        last = prev;
    } else {
        // x的后繼的前驅(qū)指向x的前驅(qū)，即略過了x
        next.prev = prev;
        // x.next已無用處，置空引用
        x.next = null;
    }
    // 引用置空
    x.item = null;
    size--;
    modCount++;
    // 返回所刪除的節(jié)點(diǎn)的元素值
    return element;
}
  • 遍歷鏈表查找 item==null 并執(zhí)行unlink(x)方法刪除。
  • 如果前驅(qū)為null，說明x為首節(jié)點(diǎn)，first指向x的后繼,x的前驅(qū)的后繼指向x的后繼，即略過了x。
  • 如果后繼為null，說明x為尾節(jié)點(diǎn)，last指向x的前驅(qū)；否則x的后繼的前驅(qū)指向x的前驅(qū)，即略過了x，置空x.next。
  • 引用置空：x.item = null。
  • 圖解。

remove(int index)方法

根據(jù)鏈表的索引刪除元素。

public E remove(int index) {
    checkElementIndex(index);
    //node(index)會(huì)返回index對(duì)應(yīng)的元素
    return unlink(node(index));
}

E unlink(Node<E> x)  方法上文有詳解。

removeFirst()方法

刪除頭節(jié)點(diǎn)。

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

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //取出首節(jié)點(diǎn)中的元素
    final E element = f.item;
    //取出首節(jié)點(diǎn)中的后繼
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    // first指向前first的后繼，也就是列表中的2號(hào)位
    first = next;
    //如果此時(shí)2號(hào)位為空，那么列表中此時(shí)已無節(jié)點(diǎn)
    if (next == null)
        //last指向null
        last = null;
    else
        // 首節(jié)點(diǎn)無前驅(qū) 
        next.prev = null;
    size--;
    modCount++;
    return element;
}

原理與添加頭節(jié)點(diǎn)類似。

removeLast()方法

刪除尾節(jié)點(diǎn)(last)

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 取出尾節(jié)點(diǎn)中的元素
    final E element = l.item;
    // 取出尾節(jié)點(diǎn)中的后繼
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    // last指向前l(fā)ast的前驅(qū)，也就是列表中的倒數(shù)2號(hào)位
    last = prev;
    // 如果此時(shí)倒數(shù)2號(hào)位為空，那么列表中已無節(jié)點(diǎn)
    if (prev == null)
        // first指向null
        first = null;
    else
        // 尾節(jié)點(diǎn)無后繼
        prev.next = null;
    size--;
    modCount++;
    // 返回尾節(jié)點(diǎn)保存的元素值
    return element;
}

7、修改元素

修改元素比較簡(jiǎn)單，先找到index對(duì)應(yīng)節(jié)點(diǎn)，然后對(duì)值進(jìn)行修改。

public E set(int index, E element) {
    checkElementIndex(index);
    // 獲取到需要修改元素的節(jié)點(diǎn)
    Node<E> x = node(index);
    // 保存之前的值
    E oldVal = x.item;
    // 執(zhí)行修改
    x.item = element;
    // 返回舊值
    return oldVal;
}

8、與ArrayList的對(duì)比

優(yōu)點(diǎn)：

  • 不需要擴(kuò)容和預(yù)留空間,空間效率高。
  • 增刪效率高。

缺點(diǎn)：

  • 隨機(jī)訪問時(shí)間效率低。
  • 改查效率低。
責(zé)任編輯：姜華 來源： 今日頭條
LinkedList雙向鏈表線程
相關(guān)推薦

2021-06-17 13:40:47

區(qū)塊鏈比特幣公有鏈

2019-11-04 09:07:48

DevOps互聯(lián)網(wǎng)IT

2019-04-24 08:31:43

分布式限流kafka

2020-03-18 18:20:19

區(qū)塊鏈數(shù)字貨幣比特幣

2018-11-28 10:39:01

5G網(wǎng)絡(luò)運(yùn)營(yíng)商

2017-08-15 15:35:21

大數(shù)據(jù)數(shù)據(jù)分析薪資秘密

2017-08-15 16:05:18

大數(shù)據(jù)數(shù)據(jù)分析薪資秘密

2018-03-31 08:45:52

iPhone交通卡iOS 11.3

2019-04-26 09:38:36

中臺(tái)平臺(tái)化轉(zhuǎn)型

2021-07-01 09:00:00

安全數(shù)字化轉(zhuǎn)型滲透

2022-11-08 15:55:34

鴻蒙開發(fā)套件

2021-07-02 14:09:36

開發(fā)技能代碼

2017-01-11 08:37:07

Apache SparStreamingDataFrames

2017-12-13 14:24:08

Google 開發(fā)者瀏覽器

2015-10-12 15:50:40

2018-05-10 08:50:31

AndroidGoogle 移動(dòng)系統(tǒng)

2021-02-23 09:28:48

大數(shù)據(jù)數(shù)據(jù)分析

2019-10-29 15:28:40

Refs組件前端

2018-08-23 11:58:53

區(qū)塊鏈數(shù)字貨幣比特幣

2022-09-15 14:22:19

協(xié)作規(guī)范前后端
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)