淺談ArrayList和LinkedList到底誰更快
一、ArrayList和LinkedList究竟誰快
在Java中應該都知道ArrayList和LinkedList,
一直以來的概念呢是
ArrayList在get(index)這個應該比LinkedList快;
LinkedList比ArrayList在add(index,element)快;
兩者共同遍歷呢,應該是一樣快的,畢竟都要循環(huán)遍歷一遍。
直到我寫了一個測試類
package com.lw; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import org.junit.Test; public class TestJDKList { List<Integer> linkedList = new LinkedList<>(); List<Integer> arrayList = new ArrayList<>(); int length = 1000000; @Test public void testLinkedInsert(){ for (int i = 0; i < length; i++) { linkedList.add(i); } long currentMi2 = System.currentTimeMillis(); linkedList.add(length/2,3); long endTime2 = System.currentTimeMillis(); System.out.println("testLinkedInsert:" + (endTime2 - currentMi2)); // 9 } @Test public void testArrayInsert(){ for (int i = 0; i < length; i++) { arrayList.add(i); } long currentMi2 = System.currentTimeMillis(); arrayList.add(length/2,3); long endTime2 = System.currentTimeMillis(); System.out.println("testArrayInsert:" + (endTime2 - currentMi2)); // 1 } @Test public void testLinkedGet(){ for (int i = 0; i < length; i++) { linkedList.add(i); } long currentMi2 = System.currentTimeMillis(); linkedList.get(length/2); long endTime2 = System.currentTimeMillis(); System.out.println("testLinkedGet:" + (endTime2 - currentMi2)); // 5 } @Test public void testArrayGet(){ for (int i = 0; i < length; i++) { arrayList.add(i); } long currentMi2 = System.currentTimeMillis(); arrayList.get(length/2); long endTime2 = System.currentTimeMillis(); System.out.println("testArrayGet:" + (endTime2 - currentMi2)); // 0 } @Test public void testLinkedIter(){ for (int i = 0; i < length; i++) { linkedList.add(i); } long currentMi2 = System.currentTimeMillis(); for (Integer i : linkedList) { }; long endTime2 = System.currentTimeMillis(); System.out.println("testLinkedIter:" + (endTime2 - currentMi2)); // 26 } @Test public void testArrayIter(){ for (int i = 0; i < length; i++) { arrayList.add(i); } long currentMi2 = System.currentTimeMillis(); for (Integer i : arrayList) { }; long endTime2 = System.currentTimeMillis(); System.out.println("testArrayIter:" + (endTime2 - currentMi2)); // 11 } @Test public void testLinkedAdd() { long currentMi2 = System.currentTimeMillis(); for (int i = 0; i < length; i++) { linkedList.add(i); } long endTime2 = System.currentTimeMillis(); System.out.println("testLinkedAdd:" + (endTime2 - currentMi2)); // 53 } @Test public void testArrayAdd(){ long currentMi1 = System.currentTimeMillis(); for (int i = 0; i < length; i++) { arrayList.add(i); } long endTime1 = System.currentTimeMillis(); System.out.println("testArrayAdd:" + (endTime1 - currentMi1)); // 35 } }
二、結(jié)果
運行了兩遍結(jié)果如下:
testLinkedInsert:7
testArrayInsert:0
testLinkedAdd:218
testArrayAdd:23
testLinkedGet:4
testArrayGet:0
testLinkedIter:14
testArrayIter:11
----------------第二遍分割線---------------------------------
testLinkedInsert:12
testArrayInsert:0
testLinkedIter:13
testArrayIter:12
testLinkedGet:3
testArrayGet:0
testLinkedAdd:119
testArrayAdd:23
顛覆三觀,ArrayList竟然無論怎樣都比LinkedList快??
三、循環(huán)Add
ArrayList的add源碼,它是把數(shù)據(jù)放在一個數(shù)組中
transient Object[] elementData;
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
而LinkedList源碼,是把數(shù)據(jù)放在Node對象中,有個前后指針。
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++; }
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; } }
難道是前后指針這里花時間了么?
四、指定位置Get
再看get方法,
ArrayList的get,因為是連續(xù)的內(nèi)存,所以取數(shù)據(jù)很快。
public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }
再看LinkedList的get,是通過指針遍歷的,直到是這個index為止。
這里還有判斷size,如果是size的前一半,則通過first節(jié)點往后去找,如果在后一半則通過last節(jié)點往前找,這樣會更快,所以LinkedList的查找其實也不慢。
public E get(int index) { checkElementIndex(index); return node(index).item; } 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; } }
五、指定位置Add
ArrayList的add(index,element)
這里是可以擴容的,將index后半段拷貝到index+1,然后在index插入一個新的,但沒想到這么快。
其實也能想到System.arraycopy是native,所以快也能理解
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
然后是LinkedList的add(index,element)
無非是指針的指向變化而已,但沒想到比上面的System.arraycopy還要慢,果然不愧為native方法。
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++; } 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++; }
所以項目中大部分用ArrayList也就是可以理解。
不過ArrayList是連續(xù)的內(nèi)存空間,在內(nèi)存空間很緊張情況下,LinkedList內(nèi)存利用率更高。
到此這篇關于淺談ArrayList和LinkedList到底誰更快的文章就介紹到這了,更多相關ArrayList和LinkedList內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
- java中ArrayList和LinkedList的區(qū)別詳解
- 區(qū)分Java中的ArrayList和LinkedList
- java 集合之實現(xiàn)類ArrayList和LinkedList的方法
- Java中ArrayList和LinkedList之間的區(qū)別_動力節(jié)點Java學院整理
- java中ArrayList與LinkedList對比詳情
- java 中ArrayList與LinkedList性能比較
- Java中ArrayList和LinkedList的遍歷與性能分析
- 分析Java中ArrayList與LinkedList列表結(jié)構(gòu)的源碼
- 淺談 java中ArrayList、Vector、LinkedList的區(qū)別聯(lián)系
- JAVA LinkedList和ArrayList的使用及性能分析
相關文章
java實現(xiàn)統(tǒng)計字符串中字符及子字符串個數(shù)的方法示例
這篇文章主要介紹了java實現(xiàn)統(tǒng)計字符串中字符及子字符串個數(shù)的方法,涉及java針對字符串的遍歷、判斷及運算相關操作技巧,需要的朋友可以參考下2017-01-01Spring Cloud超詳細i講解Feign自定義配置與使用
這篇文章主要介紹了SpringCloud Feign自定義配置與使用,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-06-06springboot的maven多模塊混淆jar包的實現(xiàn)方法
springboot可以使用proguard-maven-plugin 這個插件 在 pom.xml 中自定義proguard 的指令,本文基于 springboot + maven + proguard 的maven多模塊架構(gòu)進行代碼混淆,需要的朋友可以參考下2024-03-03