LinkedList的介紹和源碼解析

ArrayList的介紹

1、LinkedList的簡介

List 接口的鏈接列表實現(xiàn)。實現(xiàn)所有可選的列表操作，并且允許所有元素（包括 null）。除了實現(xiàn) List 接口外，LinkedList 類還為在列表的開頭及結(jié)尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

2、ArrayList的構(gòu)造函數(shù)

//構(gòu)造一個默認(rèn)函數(shù)
public LinkedList()
//構(gòu)造一個構(gòu)造函數(shù)，并添加數(shù)據(jù)
public LinkedList(Collection<? extends E> c)

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

LinkedList的重要字段說明

first：雙向列表的表頭
last：雙向列表的尾
size：列表的大小
modCount：實現(xiàn)fail-fast機制，不同線程對同一個集合進行操作是的錯誤機制

LinkedList的重要方法源碼解析

LinkedList實際上是通過雙向鏈表去實現(xiàn)的。既然是雙向鏈表，那么它的順序訪問會非常高效，而隨機訪問效率比較低。但是它也實現(xiàn)了List接口，也可以用索引值的方式獲取數(shù)據(jù)

//添加數(shù)據(jù)到鏈表中
public boolean add(E e) {  //添加一個元素
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null); //通過數(shù)據(jù)新建節(jié)點
        last = newNode;   //把新建的節(jié)點賦值為最后的節(jié)點
        if (l == null)    //如果當(dāng)前鏈表沒有數(shù)據(jù) 就把新節(jié)點，賦值為表頭，否則就在指向表尾
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

public void add(int index, E element) {
        checkPositionIndex(index);   //判斷當(dāng)前下標(biāo)是否越界

        if (index == size)    //如果下標(biāo)跟鏈表大小相等，就接在表尾
            linkLast(element);
        else
            linkBefore(element, node(index));   //否則就把節(jié)點加到通過下標(biāo)位置查出的節(jié)點前面
    }

Node<E> node(int index) {  //根據(jù)下標(biāo)查詢節(jié)點
        if (index < (size >> 1)) {  // size/2<下標(biāo)從末尾往前遞歸 index < size/2 從表前往后遞歸
            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;
        }
    }

void linkLast(E e) {   //往表尾添加數(shù)據(jù)，跟默認(rèn)添加一個節(jié)點一樣
        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++;
    }
 //先把succ的前節(jié)點設(shè)置為新節(jié)點，然后判斷succ的前節(jié)點是否為空，為空就把新節(jié)點賦值為表頭，否則置為succ最開始前節(jié)點的下一個子節(jié)點
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); //新建節(jié)點
        succ.prev = newNode;   
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

public boolean addAll(Collection<? extends E> c) {  //添加一組數(shù)據(jù)到鏈表中
        return addAll(size, c);
    }

//添加一組數(shù)據(jù)到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);   

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;  //通過下標(biāo)查到指定位置的前節(jié)點和后節(jié)點 
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) { //循環(huán)添加到鏈表中
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

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

        size += numNew;
        modCount++;
        return true;
    }

//從鏈表獲取數(shù)據(jù)
public E get(int index) {  //通過下標(biāo)獲取數(shù)據(jù)  先檢測是否下標(biāo)越界 然后通過node(index)獲取節(jié)點，并獲取節(jié)點的數(shù)據(jù)
        checkElementIndex(index);
        return node(index).item;
    }
//獲取頭節(jié)點
public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
//獲取尾節(jié)點
public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

//節(jié)點的刪除
public boolean remove(Object o) { //從頭往尾遍歷 如果存在數(shù)據(jù) 就刪除
        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;
    }

public E remove() {  //刪除表頭
        return removeFirst();
    }

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

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

public E remove(int index) {  //刪除下標(biāo)數(shù)據(jù)
        checkElementIndex(index);
        return unlink(node(index));
    }

E unlink(Node<E> x) {  //刪除數(shù)據(jù)
        // 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;
    }

public boolean removeLastOccurrence(Object o) { //刪除相同數(shù)據(jù)的末尾一個
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

private E unlinkLast(Node<E> l) {  //刪除末尾數(shù)據(jù)
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

public boolean removeFirstOccurrence(Object o) {  //刪除第一個數(shù)據(jù)
        return remove(o);
    }

//實現(xiàn)Deque接口其中的重要方法源碼
public E peek() {  //只是返回節(jié)點
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

public E pop() {  //返回并刪除節(jié)點
        return removeFirst();
    }

public E poll() {  //返回并刪除頭節(jié)點
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

從它的數(shù)據(jù)結(jié)構(gòu)可以知道，它是沒有容量限制的，它的克隆函數(shù)，就是把LinkedList克隆到一個新的LinkedList中，subList調(diào)用的AbstractList中的方法，返回不是一個擁有LinkedList所有方法和功能的對象，是一個繼承了AbstractList重寫的對象,LinkedList可以作為隊列（先進先出），也可以做為棧（先進后出）

LinkedList的遍歷方式

1、通過迭代器的方式去實現(xiàn)，既Iterator的方式

Iterator iterator = list.iterator;
while(iterator.hasNext()){
    String value = iterator.next();
}

2、通過索引隨機訪問，ArrayList默認(rèn)實現(xiàn)了RandomAccess

  for(int i = 0;i<size;i++){
    String value = list.get(i);
}

3、通過ForEach循環(huán)遍歷

 for(String str:list){
    String value = str;
}

4、通過pollFirst()來遍歷

white(list.pollFirst() != null){
}

5、通過PollLast來遍歷

white(list.pollLast() != null){
}

6、通過removeFirst()來遍歷

white(list.removeFirst() != null){
}

6、通過removeLast()來遍歷

white(list.removeLast() != null){
}

4、5、6、7的效率會高點(他們的實現(xiàn)方式基本相同) 他們會刪除原始數(shù)據(jù) 如果只想去除數(shù)據(jù)3的效率會高點

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

  • ? 在編寫java程序中，我們最常用的除了八種基本數(shù)據(jù)類型，String對象外還有一個集合類，在我們的的程序中到處...
    Java幫幫閱讀 1,560評論 0贊 6
  • 前言 今天來介紹下LinkedList，在集合框架整體框架一章中，我們介紹了List接口，LinkedList與A...
    嘟爺MD閱讀 3,841評論 11贊 37
  • 上一章進行了ArrayList源碼分析，這一章分析一下另一個重要的List集合LinkedList。 Linked...
    wo883721閱讀 631評論 0贊 0
  • hashmap實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組、桶等。 如圖所示 JDK 1.7，是以數(shù)組+鏈表組成的，鏈表為相同hash的鍵...
    不需要任何閱讀 946評論 0贊 1
  • 今天電瓶車掉了，剛買十天，全新的玫瑰之約。就放在社區(qū)大門口。人來人往的大門口。車子居然丟了。直到中午還在。臨到下班...
    卡卡2000閱讀 118評論 0贊 0

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