前言
通過之前的《數(shù)據(jù)表-線性結(jié)構(gòu)》。我們已經(jīng)了解了數(shù)據(jù)結(jié)構(gòu)中線性表這種存儲結(jié)構(gòu)的特點，并就其順序存儲和鏈?zhǔn)酱鎯Φ膬?yōu)缺點军掂，及實現(xiàn)方式做了深入的分析轮蜕，并做了簡單的實現(xiàn)；這里我們就從日常開發(fā)中常用的ArrayList和LinkedList出發(fā)蝗锥，鞏固學(xué)習(xí)一下線性表這種數(shù)據(jù)結(jié)構(gòu)跃洛。
下面就從線性表的ADT出發(fā)，結(jié)合其構(gòu)造函數(shù)终议，常用的增刪改查方法的實現(xiàn)税课，比較一下兩種存儲結(jié)構(gòu)的特點。
以下源碼內(nèi)容源自于Android SDK API（api-level 25)痊剖，部分方法的實現(xiàn)和普通的Java JDK中的實現(xiàn)會有一些出入韩玩；日常開發(fā)中，API的實現(xiàn)必然是以Android SDK 為主陆馁，所以還是從Android SDK 內(nèi)自帶的實現(xiàn)出發(fā)分析找颓。
ArrayList
ArrayList本質(zhì)上就是一個動態(tài)數(shù)組。
初始化及構(gòu)造函數(shù)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}
構(gòu)造函數(shù)的實現(xiàn)叮贩，很容易理解击狮；這里需要注意以下，我們可以使用其他的集合初始化ArrayList益老，本質(zhì)上就是把一個集合中的內(nèi)容復(fù)制到一個數(shù)組中彪蓬。c.toArray實現(xiàn)了列表集合到數(shù)組的轉(zhuǎn)換，Arrays.copyOf就是數(shù)組的拷貝捺萌。當(dāng)然档冬，這個過程不一定會成功，當(dāng)失敗的時候桃纯，會由Arrays.copyOf內(nèi)部拋出NullPointerException酷誓。
增、刪态坦、改盐数、查 的實現(xiàn)
增
既然是一個動態(tài)數(shù)組，那么他是怎樣實現(xiàn)動態(tài)增長的呢伞梯？
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看到玫氢，對于數(shù)組的大小何時改變，如何改變谜诫，有著非常嚴(yán)格的規(guī)則漾峡。
- 對于空數(shù)組，第一次添加元素時猜绣，數(shù)組大小將變化為 DEFAULT_CAPACITY灰殴，也就是10的大小，add操作掰邢，總是將元素添加到數(shù)組最后牺陶。
- 當(dāng)我們不斷添加元素，動態(tài)數(shù)組的size大于DEFAULT_CAPACITY時辣之，例如我們添加了第11個元素掰伸，此時在grow方法中，
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
最終怀估，newCapacity 的值為elementData.length的1.5倍狮鸭，也就是15，因此多搀，此時數(shù)組大小將變化為15歧蕉。也就是說，正常情況下康铭，ArrayList每次擴(kuò)容惯退，都將會在原來的基礎(chǔ)上，增加50%的大小从藤。
- 如果數(shù)組不斷的增長催跪，當(dāng)我們按增長50%的規(guī)律擴(kuò)容后，如果newCapacity大于MAX_ARRAY_SIZE時夷野，此時數(shù)組最大的長度為Integer.MAX_VALUE懊蒸。
刪
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
相較于添加一個元素來說，刪除一個特定位置的元素就簡單多悯搔，按照位置關(guān)系把數(shù)組元素整體（復(fù)制）移動一遍骑丸，然后將特定位置的引用指向null即可;當(dāng)然，也可以按照元素的值妒貌，從數(shù)組中移除元素者娱，或者清空數(shù)組，本質(zhì)上都是一樣的工作苏揣，就不贅述了黄鳍。
通過以上內(nèi)容可以看到，為了方便實現(xiàn)數(shù)組的復(fù)制操作平匈，這里Arrays.copy 和System.arraycopy 方法框沟，Arrays.copy 在上一篇Java工具類之Arrays梳理中已經(jīng)介紹過了，System.arraycopy是其內(nèi)部實現(xiàn)增炭。
改 & 查
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
由于實現(xiàn)了RandomAccess接口忍燥，因此隨機(jī)訪問數(shù)組元素是一件特定容易的事情，修改變得so easy隙姿，根據(jù)數(shù)組下標(biāo)賦值操作梅垄，小學(xué)生都看得懂了。因此输玷，可以看到對ArrayList队丝，修改和查找是一件十分容易的事情靡馁。
批量操作
批量添加
對于動態(tài)數(shù)組的批量添加操作，和單個元素的操作是沒有多少區(qū)別的机久，無非就是進(jìn)行擴(kuò)容操作臭墨，復(fù)制和移動數(shù)組元素時，確定好各自的位置就可以了膘盖。
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
在ArrayList的特定位置胧弛，添加一組數(shù)據(jù)，可以看到關(guān)鍵點都是數(shù)組元素的復(fù)制侠畔。這個時候ensureCapacityInternal的參數(shù)结缚，就有可能是一個非常大的值，參考前面add()方法中的擴(kuò)容操作软棺，這種情況下红竭，一次性可能需要將數(shù)組擴(kuò)大很多。
批量移除
對于批量移除,ArrayList提供了兩個使用的方法：
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
從當(dāng)前的ArrayList集合中移除所有包含在集合c中的元素码党。
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true);
}
從當(dāng)前的ArrayList集合中移除所有不在集合c中的元素德崭，換句話說，就是保留兩個集合中共有的元素揖盘。
可以說眉厨，這兩個方法實現(xiàn)的操作是互斥的。而他們內(nèi)部實現(xiàn)都是batchRemove兽狭，我們可以看一下憾股。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
這里使用contains方法，實現(xiàn)了元素的篩選箕慧。根據(jù)if語句服球，只有當(dāng)complement為true時，也就是執(zhí)行retainAll()方法時颠焦，w才會累加斩熊；需要注意的是，如果兩個集合中的元素不兼容伐庭，contains()方法會拋出異常粉渠，因此會導(dǎo)致循環(huán)提前跳出。
最終都會執(zhí)行到finally語句圾另，在這里
- 當(dāng)運(yùn)行retainAll()方法霸株，循環(huán)正常執(zhí)行完畢時，w=r=size;兩個if 判斷都不會執(zhí)行集乔，恰好保存了兩個集合中共有的元素去件；當(dāng)循環(huán)操作異常跳出時，w=r<size;第一個if 判斷執(zhí)行，會把后續(xù)所有的元素按照位置復(fù)制一遍尤溜，w+=size-r 后倔叼，w=size,后一個if 不執(zhí)行。
- 當(dāng)運(yùn)行removeAll()方法靴跛，循環(huán)正常執(zhí)行完畢時缀雳，r=size,w=0;后一個if 判斷中渡嚣，通過循環(huán)所有元素置null梢睛，恰好實現(xiàn)了所有元素清空的操作；當(dāng)循環(huán)異常跳出時识椰，r<size,w=0;最終只有size-r 個元素被置為null,沒有所有元素清空的操作绝葡。
可以看的，這個算法的實現(xiàn)很是巧妙腹鹉。好了藏畅，ArrayList的內(nèi)容，就告一段落功咒，下面看看LinkedList愉阎。
LinkedList
在《數(shù)據(jù)表-線性結(jié)構(gòu)》中我們說過，對于數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)力奋，有單鏈表榜旦，循環(huán)鏈表，雙向鏈表景殷，靜態(tài)鏈表四種實現(xiàn)溅呢，而LinkedList 就是以雙向循環(huán)鏈表雙向鏈表的方式實現(xiàn)。
這里需要注意的是猿挚，這里的LinkedList是雙向鏈表咐旧，但并不是首位相連接的循環(huán)鏈表。
為了方便绩蜻，我們可以看看下面這幅圖铣墨，回想一下一個雙向鏈表有哪些關(guān)鍵點，如何實現(xiàn)它的增刪改查操作办绝。
初始化及構(gòu)造函數(shù)
java 里面沒有指針的概念伊约，對象指向嚴(yán)格來說應(yīng)該是引用。但是感覺指針這個詞八秃，能更加形象的描述其作用碱妆。因此，以下對象的引用統(tǒng)一用指針來代替
鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)昔驱，需要一個結(jié)點對象疹尾，因此首先可以看一下結(jié)點類的定義。
包含前驅(qū)&后繼指針的Node
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;
}
}
可以發(fā)現(xiàn)，通過構(gòu)造函數(shù)纳本，就可以創(chuàng)建一個結(jié)點窍蓝，第一個參數(shù)為指向前驅(qū)的結(jié)點，第二個參數(shù)為當(dāng)前結(jié)點的值繁成，最后一個參數(shù)為指向后繼的結(jié)點吓笙。
下面看看LinkedList是如何初始化的
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;
/**
* Constructs an empty list.
*/
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}
可以看到，LinkedList初始化空鏈表的操作很簡單巾腕。
增面睛、刪、改尊搬、查 的實現(xiàn)
增 & 刪
雙向鏈表叁鉴，由于其結(jié)構(gòu)的特殊性，因此不同于數(shù)組佛寿，只能在最后添加元素的特性幌墓，鏈表可以在其頭部，位置冀泻，中間任何位置添加元素,只要能把雙向鏈表串起來常侣，怎么都行。
在非空結(jié)點succ之前插入元素e
/**
* 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;
else
pred.next = newNode;
size++;
modCount++;
}
對于鏈表的操作弹渔，永遠(yuǎn)都是那個套路胳施，不要搞錯先后順序，其實很簡單捞附。
結(jié)合這幅圖巾乳，鏈表插入應(yīng)該很容易理解了。
對于鏈表中結(jié)點的刪除鸟召，也是同樣的道理胆绊。
/**
* Unlinks non-null node x.
*/
E 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;
}
這里雙向鏈表中的結(jié)點移除后，還需要判斷一下欧募，是否需要初始化為一個空的雙向鏈表压状。
改 & 查
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
鏈表的修改和查找操作，首先進(jìn)行的是位置index的越界檢測跟继，然后通過node 方法獲取index 位置元素進(jìn)行相應(yīng)的操作即可种冬。下面看一下node實現(xiàn)。
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;
}
}
可以看到舔糖，這里首先會判斷一下index位置和整個線性表長度的關(guān)系娱两，然后決定是從頭部開始后繼查找，還是從尾部進(jìn)行前驅(qū)查找金吗。很明顯十兢，鏈?zhǔn)酱鎯Y(jié)構(gòu)中趣竣，對于查找特定位置的元素，是非常麻煩的旱物。無論怎樣遥缕，按位置查找，在最壞的情況下宵呛，要把一段的元素循環(huán)一遍单匣。這在數(shù)量級很大的時候，是不劃算的宝穗。
除了按位置查找之外户秤，還可以按照元素的值進(jì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 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;
}
從源碼可以看到泡徙，使用鏈表結(jié)構(gòu)批量添加元素是很費勁的橱鹏，首先集合元素轉(zhuǎn)成數(shù)組，然后根據(jù)添加位置確定結(jié)點堪藐，最后還要通過循環(huán)逐一將數(shù)組中元素串進(jìn)去莉兰。
對于鏈表的清空操作，clear()方法礁竞，同理也需要循環(huán)各個元素糖荒，釋放結(jié)點的引用，保證鏈表清空后模捂，所有對象都能被回收捶朵。
其他
如果查看LinkedList的源碼，我們還可以發(fā)現(xiàn)有peek,push,pop等一系列的方法狂男，這是因為LinkedList同時也是一種特殊的線性表-隊列综看。這點從其定義也可以看出來 ，他實現(xiàn)了Deque接口岖食，因此是一個雙端隊列红碑。這些方法都是按照隊列FILO的思想，對雙向鏈表泡垃，實現(xiàn)入隊出隊的操作析珊；內(nèi)部的真正實現(xiàn)還是依賴于上面提到幾個方法，就不贅述了蔑穴，有興趣的同學(xué)可以對比一下忠寻。
以上，從數(shù)據(jù)結(jié)構(gòu)的角度存和，敘述了一下ArrayList和LinkedList奕剃。注意不是從集合Collections框架的角度出發(fā)赶舆，所以暫時略過迭代器Iterator的分析。
ArrayList VS LinkedList
關(guān)于二者各自的優(yōu)缺點祭饭，適合在哪些場景使用芜茵，通過通篇的描述，相信大家心里都有數(shù)了倡蝙。這里就不再總結(jié)了九串。下面再看一下兩個常用的點。
判斷空
這兩種不同的存儲結(jié)構(gòu)寺鸥，是如何實現(xiàn)空判斷的呢猪钮？
ArrayList
public boolean isEmpty() {
return size == 0;
}
LinkedList 雖然沒有提供明確方法，但我們也可以根據(jù)其size做判斷的胆建。
toArray
通過Arrays 內(nèi)部的靜態(tài)方法asList 可以很方便的把數(shù)組轉(zhuǎn)換為列表烤低。而List接口也定義的統(tǒng)一的方法toArray實現(xiàn)列表到數(shù)組的轉(zhuǎn)換；需要由每一種特殊的List提供各自的實現(xiàn)笆载。我們可以看一下ArrayList和LinkedList是如何實現(xiàn)toArray方法的扑馁。
ArrayList-toArray()
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
LinkedList-toArray()
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
很清楚的實現(xiàn)，對于ArrayList凉驻，本身即是一個數(shù)組腻要，因此只需要把內(nèi)容復(fù)制一份即可（可以看到，列表其實也是數(shù)組）涝登。而對于LinkedList就稍微有點麻煩了雄家，他需要創(chuàng)建一個對象數(shù)組，把列表里的每一個結(jié)點的值取出來胀滚。
ArrayList VS Vector
說完了ArrayList和LinkedList趟济，這里再簡單的說一下Vector。
- Vector和ArrayList一樣咽笼，也是一個動態(tài)數(shù)組顷编。唯一不同的是Vector是線程安全的，這點從他的源碼可以看到褐荷，所有的數(shù)組操作方法都加了關(guān)鍵字synchronized勾效。因此，當(dāng)多線程同時操作一個List時叛甫，可以考慮使用Vector代替ArrayList层宫。
- 前面說了，ArrayList每次擴(kuò)容其监，會增加原來50%的容量萌腿，Vector則是直接增加一倍。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
好了抖苦，通過以上對ArrayList和LinkedList的分析毁菱，對比兑牡；相信大家對線性表的線性存儲和鏈?zhǔn)酱鎯τ辛烁钊氲恼J(rèn)識酵镜。
不成熟的小實驗
最后树绩，通過一個不成熟的小實驗氏义，ArrayList，Vector窗慎，LinkedList PK 一下Ｎ锱纭！
public class DataStructTest {
private static final int DATA_SIZE = 10 * 10 * 10 * 10 * 10 * 10 * 10;
public static void main(String[] args) {
ArrayListTest();
VectorTest();
LinkedListTest();
}
private static void ArrayListTest() {
long start = System.nanoTime();
List<String> datas = new ArrayList<>();
for (int i = 0; i < DATA_SIZE; i++) {
datas.add("item-" + i);
}
long end = System.nanoTime();
System.err.printf("ArrayList Add %d element in %d nanoseconds\n", DATA_SIZE, (end - start));
start = System.nanoTime();
String data = datas.get(DATA_SIZE / 2);
end = System.nanoTime();
System.err.printf("Get data %s from ArrayList at pos=%d in %d nanoseconds\n", data, DATA_SIZE / 2, end - start);
}
private static void VectorTest() {
long start = System.nanoTime();
List<String> datas = new Vector<>();
for (int i = 0; i < DATA_SIZE; i++) {
datas.add("item-" + i);
}
long end = System.nanoTime();
System.err.printf("Vector Add %d element in %d nanoseconds\n", DATA_SIZE, end - start);
start = System.nanoTime();
String data = datas.get(DATA_SIZE / 2);
end = System.nanoTime();
System.err.printf("Get data %s from Vector at pos=%d in %d nanoseconds\n", data, DATA_SIZE / 2, end - start);
}
private static void LinkedListTest() {
long start = System.nanoTime();
List<String> datas = new LinkedList<>();
for (int i = 0; i < DATA_SIZE; i++) {
datas.add("item-" + i);
}
long end = System.nanoTime();
System.err.printf("LinkedList Add %d element in %d nanoseconds\n", DATA_SIZE, end - start);
start = System.nanoTime();
String data = datas.get(DATA_SIZE / 2);
end = System.nanoTime();
System.err.printf("Get data %s from LinkedList at pos=%d in %d nanoseconds\n", data, DATA_SIZE / 2, end - start);
}
}
上面的代碼遮斥，使用三種結(jié)構(gòu)實現(xiàn)添加DATA_SIZE個數(shù)據(jù)到List中峦失，最后從第DATA_SIZE/2個位置返回元素。當(dāng)然這樣對LinkedList來說是不太公平的术吗∥炯總之，這是一個不成熟的小實驗较屿∷砥牵看一下返回結(jié)果吧！
ArrayList Add 10000000 element in 7491830924 nanoseconds
Get data item-5000000 from ArrayList at pos=5000000 in 7106 nanoseconds
Vector Add 10000000 element in 3810582375 nanoseconds
Get data item-5000000 from Vector at pos=5000000 in 3948 nanoseconds
LinkedList Add 10000000 element in 3475231051 nanoseconds
Get data item-5000000 from LinkedList at pos=5000000 in 73783797 nanoseconds
這是運(yùn)行結(jié)果吝镣，當(dāng)然每次運(yùn)行的結(jié)果都是不一樣的堤器，但是總的趨平均計算的話每次都是相同的。
ArrayList 和 Vector 這樣的線性存儲結(jié)構(gòu)中末贾，查找某個特定位置的元素是，速度比LinkedList快了差不多一萬倍整吆，而添加操作時拱撵，LinkedList總的來說，會快一些表蝙。
好了拴测，從數(shù)據(jù)結(jié)構(gòu)的角度說ArrayList和LinkedList就到這里了。
如果本文中有不正確的結(jié)論府蛇、說法集索，請大家提出和我討論，共同進(jìn)步汇跨，謝謝务荆。
