Java基于JDK 1.8的LinkedList源碼詳析

更新時間：2018年11月01日 15:46:07 作者：阿呆哥哥

這篇文章主要給大家介紹了關(guān)于Java基于JDK 1.8的LinkedList源碼的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

前言

上周末我們一起分析了ArrayList的源碼并進行了一些總結(jié)，因為最近在看Collection這一塊的東西，下面的圖也是大致的總結(jié)了Collection里面重要的接口和類，如果沒有意外的話后面基本上每一個都會和大家一起學習學習，所以今天也就和大家一起來看看LinkedList吧！

2，記得首次接觸LinkedList還是在大學Java的時候，當時說起LinkedList的特性和應用場景：LinkedList基于雙向鏈表適用于增刪頻繁且查詢不頻繁的場景，線程不安全的且適用于單線程（這點和ArrayList很像）。然后還記得一個很深刻的是可以用LinkedList來實現(xiàn)棧和隊列，那讓我們一起看一看源碼到底是怎么來實現(xiàn)這些特點的

2.1 構(gòu)造函數(shù)

public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 transient int size = 0;
 transient Node<E> first;
 transient Node<E> last;
 
 public LinkedList() {
 }
 
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
 
 public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }
 
 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;
 if (index == size) {
  succ = null;
  pred = last;
 } else {
  succ = node(index);
  pred = succ.prev;
 }
 
 for (Object o : a) {
  @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;
 }
 
 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;
 }
 }
 
 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;
 }
 } 
 
}

首先我們知道常見的構(gòu)造是LinkedList()和LinkedList(Collection<? extends E> c)兩種，然后再來看看我們繼承的類和實現(xiàn)的接口

LinkedList 集成AbstractSequentialList抽象類，內(nèi)部使用listIterator迭代器來實現(xiàn)重要的方法
LinkedList 實現(xiàn) List 接口，能對它進行隊列操作。
LinkedList 實現(xiàn) Deque 接口，即能將LinkedList當作雙端隊列使用。
LinkedList 實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能克隆。
LinkedList 實現(xiàn)java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。

可以看到，相對于ArrayList，LinkedList多實現(xiàn)了Deque接口而少實現(xiàn)了RandomAccess接口，且LinkedList繼承的是AbstractSequentialList類，而ArrayList繼承的是AbstractList類。那么我們現(xiàn)在有一個疑問，這些多實現(xiàn)或少實現(xiàn)的接口和類會對我們LinkedList的特點產(chǎn)生影響嗎？這里我們先將這個疑問放在心里，我們先走正常的流程，先把LinkedList的源碼看完（主要是要解釋這些東西看Deque的源碼，還要去看Collections里面的邏輯，我怕扯遠了）

　　第5-7行：定義記錄元素數(shù)量size，因為我們之前說過LinkedList是個雙向鏈表，所以這里定義了鏈表鏈表頭節(jié)點first和鏈表尾節(jié)點last

　　第60-70行：定義一個節(jié)點Node類，next表示此節(jié)點的后置節(jié)點，prev表示側(cè)節(jié)點的前置節(jié)點，element表示元素值

　　第22行：檢查當前的下標是否越界，因為是在構(gòu)造函數(shù)中所以我們這邊的index為0，且size也為0

　　第24-29行：將集合c轉(zhuǎn)化為數(shù)組a，并獲取集合的長度；定義節(jié)點pred、succ，pred用來記錄前置節(jié)點，succ用來記錄后置節(jié)點

　第70-89行：node()方法是獲取LinkedList中第index個元素，且根據(jù)index處于前半段還是后半段進行一個折半，以提升查詢效率

　　第30-36行：如果index==size，則將元素追加到集合的尾部，pred = last將前置節(jié)點pred指向之前結(jié)合的尾節(jié)點，如果index！=size表明是插入集合，通過node(index)獲取當前要插入index位置的節(jié)點，且pred = succ.prev表示將前置節(jié)點指向于當前要插入節(jié)點位置的前置節(jié)點

　　第38-46行：鏈表批量增加，是靠for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點操作，第40行以前置節(jié)點和元素值e，構(gòu)建new一個新節(jié)點；第41行如果前置節(jié)點是空，說明是頭結(jié)點，且將成員變量first指向當前節(jié)點，如果不是頭節(jié)點，則將上一個節(jié)點的尾節(jié)點指向當前新建的節(jié)點；第45行將當前的節(jié)點為前置節(jié)點了，為下次添加節(jié)點做準備。這些走完基本上我們的新節(jié)點也都創(chuàng)建出來了，可能這塊代碼有點繞，大家多看看

　　第48-53行：循環(huán)結(jié)束后，判斷如果后置節(jié)點是null，說明此時是在隊尾添加的，設(shè)置一下隊列尾節(jié)點last，如果不是在隊尾，則更新之前插入位置節(jié)點的前節(jié)點和當前要插入節(jié)點的尾節(jié)點

　　第55-56行：修改當前集合數(shù)量、修改modCount記錄值

　　ok,雖然說是分析的構(gòu)造函數(shù)的源碼，但是把node(int index)、addAll(int index, Collection<? extends E> c)方法也都看了，所以來小結(jié)一下：鏈表批量增加，是靠for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點操作；通過下標index來獲取節(jié)點Node是采用的折半法來提升效率的

2.2 增加元素

常見的方法有以下三種

linkedList.add(E e)
linkedList.add(int index, E element)
linkedList.addAll(Collection<? extends E> c)

來看看具體的源碼

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);
 last = newNode;
 if (l == null)
  first = newNode;
 else
  l.next = newNode;
 size++;
 modCount++;
}
 
public void add(int index, E element) {
 checkPositionIndex(index);
 
 if (index == size)
  linkLast(element);
 else
  linkBefore(element, node(index));
 }
 
 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++;
 }
 
public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }

　　第2、6-16行：創(chuàng)建一個newNode它的prev指向之前隊尾節(jié)點last，并記錄元素值e，之前的隊尾節(jié)點last的next指向當前節(jié)點，size自增，modcount自增

　　第18-20，27-38行：首先去檢查下標是否越界，然后判斷如果加入的位置剛好位于隊尾就和我們add（E element）的邏輯一樣了，如果不是則需要通過 node(index)函數(shù)定位出當前位于index下標的node，再通過linkBefore()函數(shù)創(chuàng)建出newNode將其插入到原先index位置

　　第40-42行：就是我們在構(gòu)造函數(shù)中看過的批量加入元素的方法

　　OK，添加元素也很簡單，如果是在隊尾進行添加的話只需要創(chuàng)建一個新Node將其前置節(jié)點指向之前的last，如果是在隊中添加節(jié)點，首選拆散原先的index-1、index、index+1之間的聯(lián)系，新建節(jié)點插入進去即可。

2.3 刪除元素

常見方法有以下這幾個方法

linkedList.remove(int index)
linkedList.remove(Object o)
linkedList.remove(Collection<?> c)

源碼如下

public E remove(int index) {
 checkElementIndex(index);
 return unlink(node(index));
 }
 
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;
 }
 
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;
 }
 
 public boolean removeAll(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean modified = false;
 Iterator<?> it = iterator();
 while (it.hasNext()) {
  if (c.contains(it.next())) {
  it.remove();
  modified = true;
  }
 }
 return modified;
 }

　　第1-4，6-30行：首先根據(jù)index通過方法值node(index)來確定出集合中的下標是index的node，咋們主要看unlink()方法，代碼感覺很多，其實只是將當前要刪除的節(jié)點node的頭結(jié)點的尾節(jié)點指向node的尾節(jié)點、將node的尾結(jié)點的頭節(jié)點指向node的頭節(jié)點，可能有點繞（哈哈），看一下代碼基本上就可以理解了，然后將下標為index的node置空，供GC回收

　　第32-49行：首先判斷一下當前要刪除的元素o是否為空，然后進行for循環(huán)定位出當前元素值等于o的節(jié)點node，然后再走的邏輯就是上面我們看到過的unlink()方法，也很簡單，比remove(int index) 多了一步

　　第51-62行：這一塊因為涉及到迭代器Iterator，而我們LinkedList使用的是ListItr，這個后面我們將迭代器的時候一起講，不過大致的邏輯是都可以看懂的，和我們的ArrayList的迭代器方法的含義一樣的，可以先那樣理解

　　ok，小結(jié)一下，按下標刪，也是先根據(jù)index找到Node，然后去鏈表上unlink掉這個Node。按元素刪，會先去遍歷鏈表尋找是否有該Node，考慮到允許null值，所以會遍歷兩遍，然后再去unlink它。

2.5 修改元素

public E set(int index, E element) {
 checkElementIndex(index);
 Node<E> x = node(index);
 E oldVal = x.item;
 x.item = element;
 return oldVal;
 }

只有這一種方法，首先檢查下標是否越界，然后根據(jù)下標獲取當前Node，然后修改節(jié)點中元素值item，超級簡單

2.6 查找元素

public E get(int index) {
 checkElementIndex(index);//判斷是否越界 [0,size)
 return node(index).item; //調(diào)用node()方法 取出 Node節(jié)點，
}
 
 
 public int indexOf(Object o) {
 int index = 0;
 if (o == null) {
  for (Node<E> x = first; x != null; x = x.next) {
  if (x.item == null)
   return index;
  index++;
  }
 } else {
  for (Node<E> x = first; x != null; x = x.next) {
  if (o.equals(x.item))
   return index;
  index++;
  }
 }
 return -1;
 }
 
 public int lastIndexOf(Object o) {
 int index = size;
 if (o == null) {
  for (Node<E> x = last; x != null; x = x.prev) {
  index--;
  if (x.item == null)
   return index;
  }
 } else {
  for (Node<E> x = last; x != null; x = x.prev) {
  index--;
  if (o.equals(x.item))
   return index;
  }
 }
 return -1;
 }

獲取元素的源碼也很簡單，主要是通過node(index)方法獲取節(jié)點，然后獲取元素值，indexOf和lastIndexOf方法的區(qū)別在于一個是從頭向尾開始遍歷，一個是從尾向頭開始遍歷

2.7 迭代器

public Iterator<E> iterator() {
  return listIterator();
 }
 
public ListIterator<E> listIterator() {
  return listIterator(0);
 }
 
public ListIterator<E> listIterator(final int index) {
  rangeCheckForAdd(index);
 
  return new ListItr(index);
 }
 
private class ListItr extends Itr implements ListIterator<E> {
  ListItr(int index) {
   cursor = index;
  }
 
  public boolean hasPrevious() {
   return cursor != 0;
  }
 
  public E previous() {
   checkForComodification();
   try {
    int i = cursor - 1;
    E previous = get(i);
    lastRet = cursor = i;
    return previous;
   } catch (IndexOutOfBoundsException e) {
    checkForComodification();
    throw new NoSuchElementException();
   }
  }
 
  public int nextIndex() {
   return cursor;
  }
 
  public int previousIndex() {
   return cursor-1;
  }
 
  public void set(E e) {
   if (lastRet < 0)
    throw new IllegalStateException();
   checkForComodification();
 
   try {
    AbstractList.this.set(lastRet, e);
    expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
   }
  }
 
  public void add(E e) {
   checkForComodification();
 
   try {
    int i = cursor;
    AbstractList.this.add(i, e);
    lastRet = -1;
    cursor = i + 1;
    expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
   }
  }
 }

可以看到，其實最后使用的迭代器是使用的ListIterator類，且集成自Itr，而Itr類就是我們昨天ArrayList內(nèi)部使用的類，hasNext()方法和我們之前的一樣，判斷不等于size大小，然后next()獲取元素主要也是E next = get(i);這行代碼，這樣就又走到我們之前的獲取元素的源碼當中，獲得元素值。

OK，這樣我們上面的基本方法都看完了，再來看看我們上面遺留的問題，首先來看Deque接口有什么作用，我們來一起看看

Deque 是 Double ended queue (雙端隊列) 的縮寫,讀音和 deck 一樣，蛋殼。
Deque 繼承自 Queue,直接實現(xiàn)了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。
Deque 支持容量受限的雙端隊列，也支持大小不固定的。一般雙端隊列大小不確定。
Deque 接口定義了一些從頭部和尾部訪問元素的方法。比如分別在頭部、尾部進行插入、刪除、獲取元素?！　?/p>

public interface Deque<E> extends Queue<E> {
 void addFirst(E e);//插入頭部，異常會報錯
 boolean offerFirst(E e);//插入頭部，異常不報錯
 E getFirst();//獲取頭部，異常會報錯
 E peekFirst();//獲取頭部，異常不報錯
 E removeFirst();//移除頭部，異常會報錯
 E pollFirst();//移除頭部，異常不報錯
 
 void addLast(E e);//插入尾部，異常會報錯
 boolean offerLast(E e);//插入尾部，異常不報錯
 E getLast();//獲取尾部，異常會報錯
 E peekLast();//獲取尾部，異常不報錯
 E removeLast();//移除尾部，異常會報錯
 E pollLast();//移除尾部，異常不報錯
}

Deque也就是一個接口，上面是接口里面的方法，然后了解Deque就必須了解Queue

public interface Queue<E> extends Collection<E> {
 //往隊列插入元素，如果出現(xiàn)異常會拋出異常
 boolean add(E e);
 //往隊列插入元素，如果出現(xiàn)異常則返回false
 boolean offer(E e);
 //移除隊列元素，如果出現(xiàn)異常會拋出異常
 E remove();
 //移除隊列元素，如果出現(xiàn)異常則返回null
 E poll();
 //獲取隊列頭部元素，如果出現(xiàn)異常會拋出異常
 E element();
 //獲取隊列頭部元素，如果出現(xiàn)異常則返回null
 E peek();
}

然后我們知道LinkedList實現(xiàn)了Deque接口，也就是說可以使用LinkedList實現(xiàn)棧和隊列的功能，讓寫寫看

package com.ysten.leakcanarytest;
 
import java.util.Collection;
import java.util.LinkedList;
 
/**
 * desc : 實現(xiàn)棧
 * time : 2018/10/31 0031 19:07
 *
 * @author : wangjitao
 */
public class Stack<T>
{
 private LinkedList<T> stack;
 
 //無參構(gòu)造函數(shù)
 public Stack()
 {
  stack=new LinkedList<T>();
 }
 //構(gòu)造一個包含指定collection中所有元素的棧
 public Stack(Collection<? extends T> c)
 {
  stack=new LinkedList<T>(c);
 }
 //入棧
 public void push(T t)
 {
  stack.addFirst(t);
 }
 //出棧
 public T pull()
 {
  return stack.remove();
 }
 //棧是否為空
 boolean isEmpty()
 {
  return stack.isEmpty();
 }
 
 //打印棧元素
 public void show()
 {
  for(Object o:stack)
   System.out.println(o);
 }
}

測試功能

public static void main(String[] args){
  Stack<String> stringStack = new Stack<>();
  stringStack.push("1");
  stringStack.push("2");
  stringStack.push("3");
  stringStack.push("4");
  stringStack. show();
 }

打印結(jié)果如下：

4
3
2
1

隊列的實現(xiàn)類似的，大家可以下來自己寫一下，然后繼續(xù)我們的問題，實現(xiàn)Deque接口和實現(xiàn)RandomAccess接口有什么區(qū)別，我們上面看了Deque接口，實現(xiàn)Deque接口可以擁有雙向鏈表功能，那我們再來看看RandomAccess接口

 public interface RandomAccess {
 }

發(fā)現(xiàn)什么都沒有，原來RandomAccess接口是一個標志接口（Marker），然而實現(xiàn)這個接口有什么作用呢？

答案是只要List集合實現(xiàn)這個接口，就能支持快速隨機訪問，然而又有人問，快速隨機訪問是什么東西？有什么作用？

google是這樣定義的：給可以提供隨機訪問的List實現(xiàn)去標識一下，這樣使用這個List的程序在遍歷這種類型的List的時候可以有更高效率。僅此而已。

這時候看一下我們Collections類中的binarySearch方法

int binarySearch(List<? extends Comparable<? super T>> list, T key) {
  if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
   return Collections.indexedBinarySearch(list, key);
  else
   return Collections.iteratorBinarySearch(list, key);
 }

可以看到這時候去判斷了如果當前集合實現(xiàn)了RandomAccess接口就會走Collections.indexedBinarySearch方法，那么我們來看一下Collections.indexedBinarySearch()方法和Collections.iteratorBinarySearch()的區(qū)別是什么呢？

int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
  int low = 0;
  int high = list.size()-1;
 
  while (low <= high) {
   int mid = (low + high) >>> 1;
   Comparable<? super T> midVal = list.get(mid);
   int cmp = midVal.compareTo(key);
 
   if (cmp < 0)
    low = mid + 1;
   else if (cmp > 0)
    high = mid - 1;
   else
    return mid; // key found
  }
  return -(low + 1); // key not found
 }
 
 
 
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
 {
  int low = 0;
  int high = list.size()-1;
  ListIterator<? extends Comparable<? super T>> i = list.listIterator();
 
  while (low <= high) {
   int mid = (low + high) >>> 1;
   Comparable<? super T> midVal = get(i, mid);
   int cmp = midVal.compareTo(key);
 
   if (cmp < 0)
    low = mid + 1;
   else if (cmp > 0)
    high = mid - 1;
   else
    return mid; // key found
  }
  return -(low + 1); // key not found
 }

通過查看源代碼，發(fā)現(xiàn)實現(xiàn)RandomAccess接口的List集合采用一般的for循環(huán)遍歷，而未實現(xiàn)這接口則采用迭代器

，那現(xiàn)在讓我們以LinkedList為例子看一下，通過for循環(huán)、迭代器、removeFirst和removeLast來遍歷的效率（之前忘記寫這一塊了，順便一塊先寫了對于LinkedList那種訪問效率要高一些）

迭代器遍歷

LinkedList linkedList = new LinkedList();
for(int i = 0; i < 100000; i++){
   linkedList.add(i);
}
// 迭代器遍歷
 long start = System.currentTimeMillis();
 Iterator iterator = linkedList.iterator();
 while(iterator.hasNext()){
  iterator.next();
 }
 long end = System.currentTimeMillis();
 System.out.println("Iterator："+ (end - start) +"ms");

打印結(jié)果：Iterator：28ms

for循環(huán)get遍歷

// 順序遍歷(隨機遍歷)
 long start = System.currentTimeMillis();
 for(int i = 0; i < linkedList.size(); i++){
   linkedList.get(i);
}
long end = System.currentTimeMillis();
System.out.println("for ："+ (end - start) +"ms");

打印結(jié)果 for ：6295ms

使用增強for循環(huán)

long start = System.currentTimeMillis();
for(Object i : linkedList);
long end = System.currentTimeMillis();
System.out.println("增強for ："+ (end - start) +"ms");

輸出結(jié)果增強for ：6ms

removeFirst來遍歷

long start = System.currentTimeMillis();
while(linkedList.size() != 0){
   linkedList.removeFirst();
}
long end = System.currentTimeMillis();
System.out.println("removeFirst ："+ (end - start) +"ms");

輸出結(jié)果 removeFirst ：3ms

綜上結(jié)果可以看到，遍歷LinkedList時，使用removeFirst()或removeLast()效率最高，而for循環(huán)get()效率最低，應避免使用這種方式進行。應當注意的是，使用removeFirst()或removeLast()遍歷時，會刪除原始數(shù)據(jù)，若只單純的讀取，應當選用迭代器方式或增強for循環(huán)方式。

ok，上述的都是只針對LinkedList而言測試的，然后我們接著上面的RandomAccess接口來講，看看通過對比ArrayList的for循環(huán)和迭代器遍歷看看訪問效率

ArrayList的for循環(huán)

long start = System.currentTimeMillis();
for (int i = 0; i < arrayList.size(); i++) {
   arrayList.get(i);
}
 long end = System.currentTimeMillis();
 System.out.println("for ："+ (end - start) +"ms");

輸出結(jié)果 for ：3ms

ArrayList的迭代遍歷

long start = System.currentTimeMillis();
Iterator iterable = arrayList.iterator() ;
while (iterable.hasNext()){
   iterable.next();
}
 long end = System.currentTimeMillis();
 System.out.println("for ："+ (end - start) +"ms");

輸出結(jié)果 for ：6ms

所以讓我們來綜上對比一下

ArrayList
    普通for循環(huán)：3ms
    迭代器：6ms
LinkedList
    普通for循環(huán)：6295ms
    迭代器：28ms

從上面數(shù)據(jù)可以看出，ArrayList用for循環(huán)遍歷比iterator迭代器遍歷快，LinkedList用iterator迭代器遍歷比for循環(huán)遍歷快,所以對于不同的List實現(xiàn)類，遍歷的方式有所不用，RandomAccess接口這個空架子的存在，是為了能夠更好地判斷集合是否ArrayList或者LinkedList，從而能夠更好選擇更優(yōu)的遍歷方式，提高性能！

（在這里突然想起在去年跳槽的時候，有家公司的面試官問我，list集合的哪一種遍歷方式要快一些，然后我說我沒有每個去試過，結(jié)果那位大佬說的是for循環(huán)遍歷最快，還叫我下去試試，現(xiàn)在想想，只有在集合是ArrayList的時候for循環(huán)才最快，對于LinkedList來說for循環(huán)反而是最慢的，那位大佬，你欠我一聲對不起（手動斜眼微笑））

3，上面把我們該看的點都看了，那么我們再來總結(jié)總結(jié)：

LinkedList 是雙向列表，鏈表批量增加，是靠for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點操作。

ArrayList基于數(shù)組， LinkedList基于雙向鏈表，對于隨機訪問， ArrayList比較占優(yōu)勢，但LinkedList插入、刪除元素比較快，因為只要調(diào)整指針的指向。針對特定位置需要遍歷時，所以LinkedList在隨機訪問元素的話比較慢。

LinkedList沒有實現(xiàn)自己的 Iterator，使用的是 ListIterator。

LinkedList需要更多的內(nèi)存，因為 ArrayList的每個索引的位置是實際的數(shù)據(jù)，而 LinkedList中的每個節(jié)點中存儲的是實際的數(shù)據(jù)和前后節(jié)點的位置。

LinkedList也是非線程安全的，只有在單線程下才可以使用。為了防止非同步訪問，Collections類里面提供了synchronizedList()方法。

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章: