Java基于JDK 1.8的LinkedList源碼詳析
前言
上周末我們一起分析了ArrayList的源碼并進(jìn)行了一些總結(jié),因?yàn)樽罱诳碈ollection這一塊的東西,下面的圖也是大致的總結(jié)了Collection里面重要的接口和類,如果沒(méi)有意外的話后面基本上每一個(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; } } }
首先我們知道常見(jiàn)的構(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 增加元素
常見(jiàn)的方法有以下三種
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 刪除元素
常見(jiàn)方法有以下這幾個(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()方法,代碼感覺(jué)很多,其實(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è)是從頭向尾開(kāi)始遍歷,一個(gè)是從尾向頭開(kāi)始遍歷
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)行插入、刪除、獲取元素。
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)什么都沒(méi)有,原來(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ō)我沒(méi)有每個(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沒(méi)有實(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)文章
Junit單元測(cè)試關(guān)于@Transactional注解引起的事務(wù)回滾問(wèn)題
這篇文章主要介紹了Junit單元測(cè)試關(guān)于@Transactional注解引起的事務(wù)回滾問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-08-08SpringBoot中屬性賦值操作的實(shí)現(xiàn)
這篇文章主要介紹了SpringBoot中屬性賦值操作的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10SSH框架網(wǎng)上商城項(xiàng)目第9戰(zhàn)之添加和更新商品類別功能實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了SSH框架網(wǎng)上商城項(xiàng)目第9戰(zhàn)之添加和更新商品類別功能實(shí)現(xiàn),感興趣的小伙伴們可以參考一下2016-06-06java開(kāi)發(fā)中嵌套類的詳解及實(shí)例
這篇文章主要介紹了 java開(kāi)發(fā)中嵌套類的詳解及實(shí)例的相關(guān)資料,一般把定義內(nèi)部類的外圍類成為包裝類(enclosing class)或者外部類,需要的朋友可以參考下2017-07-07Springboot + Mysql8實(shí)現(xiàn)讀寫分離功能
這篇文章主要介紹了Springboot + Mysql8實(shí)現(xiàn)讀寫分離功能,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-10-10mybatis-plus?Wrapper條件構(gòu)造器updateForSet更新方式
這篇文章主要介紹了mybatis-plus?Wrapper條件構(gòu)造器updateForSet更新方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03Mybatis傳單個(gè)參數(shù)和<if>標(biāo)簽同時(shí)使用的問(wèn)題及解決方法
這篇文章主要介紹了Mybatis傳單個(gè)參數(shù)和<if>標(biāo)簽同時(shí)使用的問(wèn)題及解決方法,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-05-05Spring?Security?自定義授權(quán)服務(wù)器實(shí)踐記錄
授權(quán)服務(wù)器(Authorization Server)目前并沒(méi)有集成在Spring Security項(xiàng)目中,而是作為獨(dú)立項(xiàng)目存在于Spring生態(tài)中,這篇文章主要介紹了Spring?Security?自定義授權(quán)服務(wù)器實(shí)踐,需要的朋友可以參考下2022-08-08SpringBoot使用JavaMailSender實(shí)現(xiàn)發(fā)送郵件
JavaMailSender是Spring Framework中的一個(gè)接口,用于發(fā)送電子郵件,本文主要為大家詳細(xì)介紹了SpringBoot如何使用JavaMailSender實(shí)現(xiàn)發(fā)送郵件,需要的可以參考下2023-12-12