欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java基于JDK 1.8的LinkedList源碼詳析

 更新時(shí)間：2018年11月01日 15:46:07   作者：阿呆哥哥  
這篇文章主要給大家介紹了關(guān)于Java基于JDK 1.8的LinkedList源碼的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

前言

上周末我們一起分析了ArrayList的源碼并進(jìn)行了一些總結(jié)，因?yàn)樽罱诳碈ollection這一塊的東西，下面的圖也是大致的總結(jié)了Collection里面重要的接口和類，如果沒有意外的話后面基本上每一個(gè)都會(huì)和大家一起學(xué)習(xí)學(xué)習(xí)，所以今天也就和大家一起來(lái)看看LinkedList吧！

 

2，記得首次接觸LinkedList還是在大學(xué)Java的時(shí)候，當(dāng)時(shí)說(shuō)起LinkedList的特性和應(yīng)用場(chǎng)景：LinkedList基于雙向鏈表適用于增刪頻繁且查詢不頻繁的場(chǎng)景，線程不安全的且適用于單線程（這點(diǎn)和ArrayList很像）。然后還記得一個(gè)很深刻的是可以用LinkedList來(lái)實(shí)現(xiàn)棧和隊(duì)列，那讓我們一起看一看源碼到底是怎么來(lái)實(shí)現(xiàn)這些特點(diǎ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)兩種，然后再來(lái)看看我們繼承的類和實(shí)現(xiàn)的接口

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

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

　　第5-7行：定義記錄元素?cái)?shù)量size，因?yàn)槲覀冎罢f(shuō)過(guò)LinkedList是個(gè)雙向鏈表，所以這里定義了鏈表鏈表頭節(jié)點(diǎn)first和鏈表尾節(jié)點(diǎn)last

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

　　第22行：檢查當(dāng)前的下標(biāo)是否越界，因?yàn)槭窃跇?gòu)造函數(shù)中所以我們這邊的index為0，且size也為0

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

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

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

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

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

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

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

2.2 增加元素

常見的方法有以下三種

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

來(lái)看看具體的源碼

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)建一個(gè)newNode它的prev指向之前隊(duì)尾節(jié)點(diǎn)last，并記錄元素值e，之前的隊(duì)尾節(jié)點(diǎn)last的next指向當(dāng)前節(jié)點(diǎn)，size自增，modcount自增

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

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

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

2.3 刪除元素

常見方法有以下這幾個(gè)方法

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通過(guò)方法值node(index)來(lái)確定出集合中的下標(biāo)是index的node，咋們主要看unlink()方法，代碼感覺很多，其實(shí)只是將當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)node的頭結(jié)點(diǎn)的尾節(jié)點(diǎn)指向node的尾節(jié)點(diǎn)、將node的尾結(jié)點(diǎn)的頭節(jié)點(diǎn)指向node的頭節(jié)點(diǎn)，可能有點(diǎn)繞（哈哈），看一下代碼基本上就可以理解了，然后將下標(biāo)為index的node置空，供GC回收

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

　　第51-62行：這一塊因?yàn)樯婕暗降鱅terator，而我們LinkedList使用的是ListItr，這個(gè)后面我們將迭代器的時(shí)候一起講，不過(guò)大致的邏輯是都可以看懂的，和我們的ArrayList的迭代器方法的含義一樣的，可以先那樣理解

　　ok，小結(jié)一下， 按下標(biāo)刪，也是先根據(jù)index找到Node，然后去鏈表上unlink掉這個(gè)Node。 按元素刪，會(huì)先去遍歷鏈表尋找是否有該Node，考慮到允許null值，所以會(huì)遍歷兩遍，然后再去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;
 }

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

2.6 查找元素

public E get(int index) {
 checkElementIndex(index);//判斷是否越界 [0,size)
 return node(index).item; //調(diào)用node()方法 取出 Node節(jié)點(diǎn)，
}
 
 
 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;
 }

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

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();
   }
  }
 }

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

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

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

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

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

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

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

package com.ysten.leakcanarytest;
 
import java.util.Collection;
import java.util.LinkedList;
 
/**
 * desc : 實(shí)現(xiàn)棧
 * time : 2018/10/31 0031 19:07
 *
 * @author : wangjitao
 */
public class Stack<T>
{
 private LinkedList<T> stack;
 
 //無(wú)參構(gòu)造函數(shù)
 public Stack()
 {
  stack=new LinkedList<T>();
 }
 //構(gòu)造一個(gè)包含指定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);
 }
}

測(cè)試功能

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

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

 public interface RandomAccess {
 }

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

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

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

這時(shí)候看一下我們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);
 }

可以看到這時(shí)候去判斷了如果當(dāng)前集合實(shí)現(xiàn)了RandomAccess接口就會(huì)走Collections.indexedBinarySearch方法，那么我們來(lái)看一下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
 }

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

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

迭代器遍歷

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遍歷

// 順序遍歷(隨機(jī)遍歷)
 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

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

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

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

removeFirst來(lái)遍歷

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時(shí)，使用removeFirst()或removeLast()效率最高，而for循環(huán)get()效率最低，應(yīng)避免使用這種方式進(jìn)行。應(yīng)當(dāng)注意的是，使用removeFirst()或removeLast()遍歷時(shí)，會(huì)刪除原始數(shù)據(jù)，若只單純的讀取，應(yīng)當(dāng)選用迭代器方式或增強(qiáng)for循環(huán)方式。

ok，上述的都是只針對(duì)LinkedList而言測(cè)試的，然后我們接著上面的RandomAccess接口來(lái)講，看看通過(guò)對(duì)比ArrayList的for循環(huán)和迭代器遍歷看看訪問(wè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

所以讓我們來(lái)綜上對(duì)比一下

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

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

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

3，上面把我們?cè)摽吹狞c(diǎn)都看了，那么我們?cè)賮?lái)總結(jié)總結(jié)：

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

ArrayList基于數(shù)組， LinkedList基于雙向鏈表，對(duì)于隨機(jī)訪問(wèn)， ArrayList比較占優(yōu)勢(shì)，但LinkedList插入、刪除元素比較快，因?yàn)橹灰{(diào)整指針的指向。針對(duì)特定位置需要遍歷時(shí)，所以LinkedList在隨機(jī)訪問(wèn)元素的話比較慢。

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

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

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

總結(jié)

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

相關(guān)文章

最新評(píng)論