• 介紹
• • ArrayList
  • LinkedList
  • 使用場景對比
  • 兩個實例：
  • • 二分查找
    • 插入元素
• 總結

介紹

List 的三個子類的特點：
ArrayList 底層結構是數組,底層查詢快,增刪慢。
LinkedList 底層結構是鏈表型的,增刪快,查詢慢。
vector 底層結構是數組 線程安全的,增刪慢,查詢慢。
鏈表增刪快，查找慢；ArrayList：基于數組實現，非線程安全的，效率高，便于索引，但不便于插入刪除；Vector：基于數組實現，線程安全的，效率低，現在使用較少

ArrayList和LinkedList都實現了List接口，他們有以下的不同點：
ArrayList是基于索引的數據接口，它的底層是數組。它可以以O(1)時間復雜度對元素進行隨機訪問。與此對應，LinkedList是以元素列表的形式存儲它的數據，每一個元素都和它的前一個和后一個元素鏈接在一起，在這種情況下，查找某個元素的時間復雜度是O(n)。
LinkedList比ArrayList更占內存，因為LinkedList為每一個節點存儲了兩個引用，一個指向前一個元素，一個指向下一個元素。

ArrayList

源碼：

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8683452581122892189L;/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/***存儲ArrayList元素的數組緩沖區 *當添加第一個元素時，將擴展到默認容量。*/transient Object[] elementData; // non-private to simplify nested class accesspublic ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA): DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

LinkedList

在LinkedList 中有一個私有的內部類，定義如下：

private static class Entry {Object element;Entry next;Entry previous;}

Linkelist可以進行的遍歷操作：

for(int i = 0;i < list.size(); i++)System.out.println(list.get(i));for(String s:list)System.out.println(s);//迭代器遍歷：Iterator<String>iter = list.iterator(); while(it.hasNext())System.out.println(iter.next());

一些頭插 尾插 獲取頭結點 尾結點等 方法的源碼：

/*** Links e as first element.*/private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}//Links e as last element.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;elsel.next = newNode;size++;modCount++;}/*** Inserts element e before non-null Node succ.*/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;elsepred.next = newNode;size++;modCount++;}/*** Returns the first element in this list.** @return the first element in this list* @throws NoSuchElementException if this list is empty*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** Returns the last element in this list.** @return the last element in this list* @throws NoSuchElementException if this list is empty*/public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}

使用場景對比

要對集合更新操作時，ArrayList 和LinkedList 哪個更適合？
1.ArrayList 是實現了基于動態數組的數據結構，LinkedList 基于鏈表的數據結構。
2.如果集合數據是對于集合隨機訪問get 和set，ArrayList 絕對優于LinkedList，因為LinkedList 要移動指針。
3.如果集合數據是對于集合新增和刪除操作add 和remove，LinedList 比較占優勢，因為ArrayList 要移動數據。
ArrayList 和LinkedList 是兩個集合類，用于存儲一系列的對象引用(references)。例如我們可以用ArrayList 來存儲一系列的String 或者Integer。那 么ArrayList 和LinkedList 在性能上有什么差別呢？什么時候應該用ArrayList 什么時候又該用LinkedList 呢？

ArrayList 的內部實現是基于基礎的對象數組的，因此，它使用get 方法訪問列表中的任意一個元素時(random access)，它的速度要比LinkedList 快。LinkedList 中的get 方法是按照順序從列表的一端開始檢查，直到另外一端。對LinkedList 而言，訪問列表中的某個指定元素沒有更快的方法了。

兩個實例：

二分查找

public class Aboutlist {public static final int N=50000;//總數public static List values;//要查找的集合//放入50000個數字給valuestatic {Integer vals[] = new Integer[N];Random r = new Random();for(int i = 0, currval = 0; i < N; i++){vals[i] = new Integer(currval);currval += r.nextInt(100)+1;}values = Arrays.asList(vals);}//二分查找static long timeList(List list){long start = System.currentTimeMillis();for(int i = 0;i < N;i++){int index = Collections.binarySearch(list, values.get(i));if(index != i)System.out.println("error");}return System.currentTimeMillis() - start;}public static void main(String[] args) {System.out.println("Arrarlist:"+timeList(new ArrayList(values)));System.out.println("Linkedlist:"+timeList(new LinkedList(values)));} }

結果：

但是基本上ArrayList 的時間要明顯小于LinkedList 的時間。因此在這種情況下不宜用LinkedList。二分查找法使用的隨機訪問(random access)策略，而LinkedList 是不支持快速的隨機訪問的。對一個LinkedList 做隨機訪問所消耗的時間與這個list 的大小是成比例的。而相應的，在ArrayList 中進行隨機訪問所消耗的時間是固定的。這是否表明ArrayList 總是比 LinkedList 性能要好呢？這并不一定，在某些情況下LinkedList 的表現要優于ArrayList，有些算法在LinkedList 中實現 時效率更高。比方說，利用Collections.reverse 方法對列表進行反轉時，其性能就要好些。

插入元素

看這樣一個例子，加入我們有一個列表，要對其進行大量的插入和刪除操作，在這種情況下LinkedList就是一個較好的選擇。請看如下一個極端的例子，我們重復的在一個列表的開端插入一個元素：

//執行大量插入操作static long timeList(List list){long start = System.currentTimeMillis();Object o = new Object();for(int i = 0;i < N;i++)list.add(0,o);return System.currentTimeMillis() - start;}public static void main(String[] args) {System.out.println("Arrarlist:"+timeList(new ArrayList(values)));System.out.println("Linkedlist:"+timeList(new LinkedList(values)));}

總結

ArrayList 和LinkedList 在性能上各有優缺點，都有各自所適用的地方，總的說來可以描述如下：
1．對ArrayList 和 LinkedList 而言，在列表末尾增加一個元素所花的開銷都是固定的。對ArrayList 而言，主要是在內部數組中增加一項，指向所添加的元素，偶 爾可能會導致對數組重新進行分配；而對LinkedList 而言，這個開銷是統一的，分配一個內部Entry 對象。
2．在ArrayList 的中間插入或刪除一個元素意味著這個列表中剩余的元素都會被移動；而在LinkedList 的中間插入或刪除一個元素的開銷是固定的。
3．LinkedList 不支持高效的隨機元素訪問。
4．ArrayList 的空間浪費主要體現在在list 列表的結尾預留一定的容量空間，而LinkedList 的空間花費則體現在它的每一個元素都需要消耗相當的空間
可以這樣說：當操作是在一列數據的后面添加數據而不是在前面或中間,并且需要隨機地訪問其中的元素時,使用ArrayList 會提供比較好的性能；當你的操作是在一列數據的前面或中間添加或刪除數據,并且按照順序訪問其中的元素時,就應該使用LinkedList 了。

總結

以上是生活随笔為你收集整理的【java学习】Arraylist和LinkedList使用场景与性能对比的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。