前言
通過之前的《數(shù)據(jù)表-線性結(jié)構(gòu)》。我們已經(jīng)了解了數(shù)據(jù)結(jié)構(gòu)中線性表這種存儲結(jié)構(gòu)的特點(diǎn)，并就其順序存儲和鏈?zhǔn)酱鎯Φ膬?yōu)缺點(diǎn)，及實(shí)現(xiàn)方式做了深入的分析，并做了簡單的實(shí)現(xiàn)；這里我們就從日常開發(fā)中常用的ArrayList和LinkedList出發(fā)，鞏固學(xué)習(xí)一下線性表這種數(shù)據(jù)結(jié)構(gòu)。
下面就從線性表的ADT出發(fā)，結(jié)合其構(gòu)造函數(shù)，常用的增刪改查方法的實(shí)現(xiàn)，比較一下兩種存儲結(jié)構(gòu)的特點(diǎn)。
以下源碼內(nèi)容源自于Android SDK API（api-level 25)，部分方法的實(shí)現(xiàn)和普通的Java JDK中的實(shí)現(xiàn)會有一些出入；日常開發(fā)中，API的實(shí)現(xiàn)必然是以Android SDK 為主，所以還是從Android SDK 內(nèi)自帶的實(shí)現(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ù)的實(shí)現(xiàn)，很容易理解；這里需要注意以下，我們可以使用其他的集合初始化ArrayList，本質(zhì)上就是把一個集合中的內(nèi)容復(fù)制到一個數(shù)組中。c.toArray實(shí)現(xiàn)了列表集合到數(shù)組的轉(zhuǎn)換，Arrays.copyOf就是數(shù)組的拷貝。當(dāng)然，這個過程不一定會成功，當(dāng)失敗的時候，會由Arrays.copyOf內(nèi)部拋出NullPointerException。
增、刪、改、查 的實(shí)現(xiàn)
增
既然是一個動態(tài)數(shù)組，那么他是怎樣實(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)容可以看到，為了方便實(shí)現(xiàn)數(shù)組的復(fù)制操作，這里Arrays.copy 和System.arraycopy 方法，Arrays.copy 在上一篇Java工具類之Arrays梳理中已經(jīng)介紹過了，System.arraycopy是其內(nèi)部實(shí)現(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];
}
由于實(shí)現(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)鍵點(diǎ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中的元素，換句話說，就是保留兩個集合中共有的元素。
可以說，這兩個方法實(shí)現(xiàn)的操作是互斥的。而他們內(nèi)部實(shí)現(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方法，實(shí)現(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，恰好實(shí)現(xiàn)了所有元素清空的操作；當(dāng)循環(huán)異常跳出時，r<size,w=0;最終只有size-r 個元素被置為null,沒有所有元素清空的操作。
可以看的，這個算法的實(shí)現(xiàn)很是巧妙。好了，ArrayList的內(nèi)容，就告一段落，下面看看LinkedList。
LinkedList
在《數(shù)據(jù)表-線性結(jié)構(gòu)》中我們說過，對于數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)，有單鏈表，循環(huán)鏈表，雙向鏈表，靜態(tài)鏈表四種實(shí)現(xiàn)，而LinkedList 就是以雙向循環(huán)鏈表雙向鏈表的方式實(shí)現(xiàn)。
這里需要注意的是，這里的LinkedList是雙向鏈表，但并不是首位相連接的循環(huán)鏈表。
為了方便，我們可以看看下面這幅圖，回想一下一個雙向鏈表有哪些關(guān)鍵點(diǎn)，如何實(shí)現(xiàn)它的增刪改查操作。
初始化及構(gòu)造函數(shù)
java 里面沒有指針的概念，對象指向嚴(yán)格來說應(yīng)該是引用。但是感覺指針這個詞，能更加形象的描述其作用。因此，以下對象的引用統(tǒng)一用指針來代替
鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)，需要一個結(jié)點(diǎn)對象，因此首先可以看一下結(jié)點(diǎn)類的定義。
包含前驅(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é)點(diǎn)，第一個參數(shù)為指向前驅(qū)的結(jié)點(diǎn)，第二個參數(shù)為當(dāng)前結(jié)點(diǎn)的值，最后一個參數(shù)為指向后繼的結(jié)點(diǎn)。
下面看看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初始化空鏈表的操作很簡單。
增、刪、改、查 的實(shí)現(xiàn)
增 & 刪
雙向鏈表，由于其結(jié)構(gòu)的特殊性，因此不同于數(shù)組，只能在最后添加元素的特性，鏈表可以在其頭部，位置，中間任何位置添加元素,只要能把雙向鏈表串起來，怎么都行。
在非空結(jié)點(diǎn)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)都是那個套路，不要搞錯先后順序，其實(shí)很簡單。
結(jié)合這幅圖，鏈表插入應(yīng)該很容易理解了。
對于鏈表中結(jié)點(diǎn)的刪除，也是同樣的道理。
/**
* 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é)點(diǎn)移除后，還需要判斷一下，是否需要初始化為一個空的雙向鏈表。
改 & 查
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實(shí)現(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)批量添加元素是很費(fèi)勁的，首先集合元素轉(zhuǎn)成數(shù)組，然后根據(jù)添加位置確定結(jié)點(diǎn)，最后還要通過循環(huán)逐一將數(shù)組中元素串進(jìn)去。
對于鏈表的清空操作，clear()方法，同理也需要循環(huán)各個元素，釋放結(jié)點(diǎn)的引用，保證鏈表清空后，所有對象都能被回收。
其他
如果查看LinkedList的源碼，我們還可以發(fā)現(xiàn)有peek,push,pop等一系列的方法，這是因?yàn)?strong>LinkedList同時也是一種特殊的線性表-隊(duì)列。這點(diǎn)從其定義也可以看出來 ，他實(shí)現(xiàn)了Deque接口，因此是一個雙端隊(duì)列。這些方法都是按照隊(duì)列FILO的思想，對雙向鏈表，實(shí)現(xiàn)入隊(duì)出隊(duì)的操作；內(nèi)部的真正實(shí)現(xiàn)還是依賴于上面提到幾個方法，就不贅述了，有興趣的同學(xué)可以對比一下。
以上，從數(shù)據(jù)結(jié)構(gòu)的角度，敘述了一下ArrayList和LinkedList。注意不是從集合Collections框架的角度出發(fā)，所以暫時略過迭代器Iterator的分析。
ArrayList VS LinkedList
關(guān)于二者各自的優(yōu)缺點(diǎn)，適合在哪些場景使用，通過通篇的描述，相信大家心里都有數(shù)了。這里就不再總結(jié)了。下面再看一下兩個常用的點(diǎn)。
判斷空
這兩種不同的存儲結(jié)構(gòu)，是如何實(shí)現(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實(shí)現(xiàn)列表到數(shù)組的轉(zhuǎn)換；需要由每一種特殊的List提供各自的實(shí)現(xiàn)。我們可以看一下ArrayList和LinkedList是如何實(shí)現(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;
}
很清楚的實(shí)現(xiàn)，對于ArrayList，本身即是一個數(shù)組，因此只需要把內(nèi)容復(fù)制一份即可（可以看到，列表其實(shí)也是數(shù)組）。而對于LinkedList就稍微有點(diǎn)麻煩了，他需要創(chuàng)建一個對象數(shù)組，把列表里的每一個結(jié)點(diǎn)的值取出來。
ArrayList VS Vector
說完了ArrayList和LinkedList，這里再簡單的說一下Vector。
- Vector和ArrayList一樣，也是一個動態(tài)數(shù)組。唯一不同的是Vector是線程安全的，這點(diǎn)從他的源碼可以看到，所有的數(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)識。
不成熟的小實(shí)驗(yàn)
最后，通過一個不成熟的小實(shí)驗(yàn)，ArrayList，Vector，LinkedList PK 一下?。?/p>
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)實(shí)現(xiàn)添加DATA_SIZE個數(shù)據(jù)到List中，最后從第DATA_SIZE/2個位置返回元素。當(dāng)然這樣對LinkedList來說是不太公平的?？傊@是一個不成熟的小實(shí)驗(yàn)?？匆幌路祷亟Y(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)步，謝謝。
