教育行業(yè)A股IPO第一股（股票代碼 003032）

全國咨詢/投訴熱線：400-618-4000

java培訓(xùn)：LinkedList的原理介紹

更新時間:2020年03月15日22時35分 來源:傳智播客 瀏覽次數(shù):

一、LinkedList的概述

1. LinkedList是雙向鏈表實現(xiàn)的List

2. LinkedList是非線程安全的

3. LinkedList元素允許為null，允許重復(fù)元素

4. LinkedList是基于鏈表實現(xiàn)的，因此插入刪除效率高，查找效率低(雖然有一個加速動作)

5. LinkedList是基于鏈表實現(xiàn)的，因此不存在容量不足的問題，所以沒有擴(kuò)容的方法

6. LinkedList還實現(xiàn)了棧和隊列的操作方法，因此也可以作為棧、隊列和雙端隊列來使用。推薦了解java培訓(xùn)課程。

LinkedList01


二、LinkedList的分析

2.1LinkedList的存儲結(jié)構(gòu)

LinkedList是由雙鏈表的數(shù)據(jù)結(jié)構(gòu)組成的

public class LinkedList{
    // 元素個數(shù)
    transient int size = 0;
    /**
    * 指向第一個節(jié)點的指針
    * 不變性:
    * 1. 如果first = null，則last=null
    * 2. 如果first.prev == null，則first.item != null
    */
    transient Node<E> first;
    /**
    * 指向最后一個節(jié)點的指針
    * 不變性:
    * 1. 如果first = null，則last = null
    * 2. 如果last.next == null，則last.item != null
    */
     transient Node<E> last;
     private static class Node<E> {
        E item;
        Node<E> next; // 下一個Node的引用
        Node<E> prev; // 上一個Node的引用
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}
/**
  * 創(chuàng)建一個空list
  * */
    public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
}
LinkedList02


2.2添加元素

2.2.1從頭部添加

// 從頭插入
public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) // 當(dāng)前List中沒有元素，size=0
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
LinkedList03


2.2.2從尾部添加

public boolean add(E e) {
    linkLast(e);
    eturn true;
}
public void addLast(E e) {
    linkLast(e);
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)// 當(dāng)前List中沒有元素，size=0
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
LinkedList04

2.3.刪除節(jié)點

2.3.1從頭部刪除

// 移除首節(jié)點，并返回該節(jié)點的元素值
public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
    throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 刪除首節(jié)點f
private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null) // size=1
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

LinkedList05


2.3.2從尾部移除

LinkedList06


2.3.3根據(jù)索引移除

public E remove(int index) {
    checkElementIndex(index);// 檢查索引index范圍
    return unlink(node(index));
}
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {// x為首節(jié)點
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
   }
    if (next == null) {// x為尾節(jié)點
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}
LinkedList07

2.4獲取節(jié)點數(shù)據(jù)

2.4.1獲取頭部數(shù)據(jù)
// 獲取首節(jié)點的數(shù)據(jù)

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

2.4.2獲取尾部數(shù)據(jù)
// 獲取尾節(jié)點的數(shù)據(jù)

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

2.4.3根據(jù)索引獲取節(jié)點數(shù)據(jù)

// 獲取索引對應(yīng)節(jié)點的數(shù)據(jù)
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
// 類似折半查找
Node<E> node(int 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;
    }
}


三、總結(jié):LinkedList和ArrayList的比較

1. 順序插入速度ArrayList會比較快，因為ArrayList是基于數(shù)組實現(xiàn)的，數(shù)組是事先new好的，只要往指定位置塞一個數(shù)據(jù)就好了

2. LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來，如果對象比較大，那么new的時間勢必會長一點，再加上一些引用賦值的操作，所以順序插入LinkedList必然慢于ArrayList

3. ArrayList的遍歷效率會比LinkedList的遍歷效率高一些

4. LinkedList做插入、刪除的時候，慢在尋址，快在只需要改變前后Node的引用地址

5. ArrayList做插入、刪除的時候，慢在數(shù)組元素的批量copy，快在尋址

(1) 如果確定插入、刪除的元素是在前半段，那么就使用LinkedList

(2) 如果確定插入、刪除的元素在比較靠后的位置，那么可以考慮使用ArrayList

(3) 如果不能確定插入、刪除是在哪兒呢?建議使用LinkedList，

·一來LinkedList整體插入、刪除的執(zhí)行效率比較穩(wěn)定，沒有ArrayList這種越往后越快的情況

·二來插入元素的時候，弄得不好ArrayList就要進(jìn)行一次擴(kuò)容，而ArrayList底層數(shù)組擴(kuò)容是一個既消耗時間又消耗空間的操作


猜你喜歡

北京比較好的Java培訓(xùn)機(jī)構(gòu)

0 分享到：
和我們在線交談！