溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
ArrayList 和 LinkedList 的區(qū)別有哪些？相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。
ArrayList 和 LinkedList 有什么區(qū)別，是面試官非常喜歡問的一個問題?？赡艽蟛糠中』锇楹臀乙粯?，能回答出“ArrayList 是基于數(shù)組實現(xiàn)的，LinkedList 是基于雙向鏈表實現(xiàn)的?！?/p>
關于這一點，我之前的文章里也提到過了。但說實話，這樣蒼白的回答并不能令面試官感到滿意，他還想知道的更多。
那假如小伙伴們繼續(xù)做出下面這樣的回答：
“ArrayList 在新增和刪除元素時，因為涉及到數(shù)組復制，所以效率比 LinkedList 低，而在遍歷的時候，ArrayList 的效率要高于 LinkedList?！?/p>
面試官會感到滿意嗎？我只能說，如果面試官比較仁慈的話，他可能會讓我們回答下一個問題；否則的話，他會讓我們回家等通知，這一等，可能意味著杳無音訊了。
為什么會這樣呢？為什么為什么？回答的不對嗎？
暴躁的小伙伴請喝口奶茶冷靜一下。冷靜下來后，請隨我來，讓我們一起肩并肩、手拉手地深入地研究一下 ArrayList 和 LinkedList 的數(shù)據(jù)結(jié)構(gòu)、實現(xiàn)原理以及源碼，可能神秘的面紗就揭開了。
ArrayList 實現(xiàn)了 List 接口，繼承了 AbstractList 抽象類，底層是基于數(shù)組實現(xiàn)的，并且實現(xiàn)了動態(tài)擴容。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;
}ArrayList 還實現(xiàn)了 RandomAccess 接口，這是一個標記接口：
public interface RandomAccess {
}內(nèi)部是空的，標記“實現(xiàn)了這個接口的類支持快速（通常是固定時間）隨機訪問”?？焖匐S機訪問是什么意思呢？就是說不需要遍歷，就可以通過下標（索引）直接訪問到內(nèi)存地址。
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}ArrayList 還實現(xiàn)了 Cloneable 接口，這表明 ArrayList 是支持拷貝的。ArrayList 內(nèi)部的確也重寫了 Object 類的 clone() 方法。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}ArrayList 還實現(xiàn)了 Serializable 接口，同樣是一個標記接口：
public interface Serializable {
}內(nèi)部也是空的，標記“實現(xiàn)了這個接口的類支持序列化”。序列化是什么意思呢？Java 的序列化是指，將對象轉(zhuǎn)換成以字節(jié)序列的形式來表示，這些字節(jié)序中包含了對象的字段和方法。序列化后的對象可以被寫到數(shù)據(jù)庫、寫到文件，也可用于網(wǎng)絡傳輸。
眼睛雪亮的小伙伴可能會注意到，ArrayList 中的關鍵字段 elementData 使用了 transient 關鍵字修飾，這個關鍵字的作用是，讓它修飾的字段不被序列化。
這不前后矛盾嗎？一個類既然實現(xiàn)了 Serilizable 接口，肯定是想要被序列化的，對吧？那為什么保存關鍵數(shù)據(jù)的 elementData 又不想被序列化呢?
這還得從 “ArrayList 是基于數(shù)組實現(xiàn)的”開始說起。大家都知道，數(shù)組是定長的，就是說，數(shù)組一旦聲明了，長度（容量）就是固定的，不能像某些東西一樣伸縮自如。這就很麻煩，數(shù)組一旦裝滿了，就不能添加新的元素進來了。
ArrayList 不想像數(shù)組這樣活著，它想能屈能伸，所以它實現(xiàn)了動態(tài)擴容。一旦在添加元素的時候，發(fā)現(xiàn)容量用滿了 s == elementData.length，就按照原來數(shù)組的 1.5 倍（oldCapacity >> 1）進行擴容。擴容之后，再將原有的數(shù)組復制到新分配的內(nèi)存地址上 Arrays.copyOf(elementData, newCapacity)。
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}動態(tài)擴容意味著什么？大家伙想一下。嗯，還是我來告訴大家答案吧，有點迫不及待。
意味著數(shù)組的實際大小可能永遠無法被填滿的，總有多余出來空置的內(nèi)存空間。
比如說，默認的數(shù)組大小是 10，當添加第 11 個元素的時候，數(shù)組的長度擴容了 1.5 倍，也就是 15，意味著還有 4 個內(nèi)存空間是閑置的，對吧？
序列化的時候，如果把整個數(shù)組都序列化的話，是不是就多序列化了 4 個內(nèi)存空間。當存儲的元素數(shù)量非常非常多的時候，閑置的空間就非常非常大，序列化耗費的時間就會非常非常多。
于是，ArrayList 做了一個愉快而又聰明的決定，內(nèi)部提供了兩個私有方法 writeObject 和 readObject 來完成序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}從 writeObject 方法的源碼中可以看得出，它使用了 ArrayList 的實際大小 size 而不是數(shù)組的長度（elementData.length）來作為元素的上限進行序列化。
此處應該有掌聲??！不是為我，為 Java 源碼的作者們，他們真的是太厲害了，可以用兩個詞來形容他們——殫精竭慮、精益求精。
LinkedList 是一個繼承自 AbstractSequentialList 的雙向鏈表，因此它也可以被當作堆棧、隊列或雙端隊列進行操作。
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;
}LinkedList 內(nèi)部定義了一個 Node 節(jié)點，它包含 3 個部分：元素內(nèi)容 item，前引用 prev 和后引用 next。代碼如下所示：
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}LinkedList 還實現(xiàn)了 Cloneable 接口，這表明 LinkedList 是支持拷貝的。
LinkedList 還實現(xiàn)了 Serializable 接口，這表明 LinkedList 是支持序列化的。眼睛雪亮的小伙伴可能又注意到了，LinkedList 中的關鍵字段 size、first、last 都使用了 transient 關鍵字修飾，這不又矛盾了嗎？到底是想序列化還是不想序列化？
答案是 LinkedList 想按照自己的方式序列化，來看它自己實現(xiàn)的 writeObject() 方法：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (LinkedList.Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}發(fā)現(xiàn)沒？LinkedList 在序列化的時候只保留了元素的內(nèi)容 item，并沒有保留元素的前后引用。這樣就節(jié)省了不少內(nèi)存空間，對吧？
那有些小伙伴可能就疑惑了，只保留元素內(nèi)容，不保留前后引用，那反序列化的時候怎么辦？
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}注意 for 循環(huán)中的 linkLast() 方法，它可以把鏈表重新鏈接起來，這樣就恢復了鏈表序列化之前的順序。很妙，對吧？
和 ArrayList 相比，LinkedList 沒有實現(xiàn) RandomAccess 接口，這是因為 LinkedList 存儲數(shù)據(jù)的內(nèi)存地址是不連續(xù)的，所以不支持隨機訪問。
前面我們已經(jīng)從多個維度了解了 ArrayList 和 LinkedList 的實現(xiàn)原理和各自的特點。那接下來，我們就來聊聊 ArrayList 和 LinkedList 在新增元素時究竟誰快？
1）ArrayList
ArrayList 新增元素有兩種情況，一種是直接將元素添加到數(shù)組末尾，一種是將元素插入到指定位置。
添加到數(shù)組末尾的源碼：
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}很簡單，先判斷是否需要擴容，然后直接通過索引將元素添加到末尾。
插入到指定位置的源碼：
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}先檢查插入的位置是否在合理的范圍之內(nèi)，然后判斷是否需要擴容，再把該位置以后的元素復制到新添加元素的位置之后，最后通過索引將元素添加到指定的位置。這種情況是非常傷的，性能會比較差。
2）LinkedList
LinkedList 新增元素也有兩種情況，一種是直接將元素添加到隊尾，一種是將元素插入到指定位置。
添加到隊尾的源碼：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}先將隊尾的節(jié)點 last 存放到臨時變量 l 中（不是說不建議使用 I 作為變量名嗎？Java 的作者們明知故犯?。?，然后生成新的 Node 節(jié)點，并賦給 last，如果 l 為 null，說明是第一次添加，所以 first 為新的節(jié)點；否則將新的節(jié)點賦給之前 last 的 next。
插入到指定位置的源碼：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, LinkedList.Node<E> succ) {
// assert succ != null;
final LinkedList.Node<E> pred = succ.prev;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}先檢查插入的位置是否在合理的范圍之內(nèi)，然后判斷插入的位置是否是隊尾，如果是，添加到隊尾；否則執(zhí)行 linkBefore() 方法。
在執(zhí)行 linkBefore() 方法之前，會調(diào)用 node() 方法查找指定位置上的元素，這一步是需要遍歷 LinkedList 的。如果插入的位置靠前前半段，就從隊頭開始往后找；否則從隊尾往前找。也就是說，如果插入的位置越靠近 LinkedList 的中間位置，遍歷所花費的時間就越多。
找到指定位置上的元素（succ）之后，就開始執(zhí)行 linkBefore() 方法了，先將 succ 的前一個節(jié)點（prev）存放到臨時變量 pred 中，然后生成新的 Node 節(jié)點（newNode），并將 succ 的前一個節(jié)點變更為 newNode，如果 pred 為 null，說明插入的是隊頭，所以 first 為新節(jié)點；否則將 pred 的后一個節(jié)點變更為 newNode。
經(jīng)過源碼分析以后，小伙伴們是不是在想：“好像 ArrayList 在新增元素的時候效率并不一定比 LinkedList 低??！”
當兩者的起始長度是一樣的情況下：
如果是從集合的頭部新增元素，ArrayList 花費的時間應該比 LinkedList 多，因為需要對頭部以后的元素進行復制。
public class ArrayListTest {
public static void addFromHeaderTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(0, i + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("ArrayList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));
}
}
/**
* @author 微信搜「沉默王二」，回復關鍵字 PDF
*/
public class LinkedListTest {
public static void addFromHeaderTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.addFirst(i + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("LinkedList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));
}
}num 為 10000，代碼實測后的時間如下所示：
ArrayList從集合頭部位置新增元素花費的時間595
LinkedList從集合頭部位置新增元素花費的時間15
ArrayList 花費的時間比 LinkedList 要多很多。
如果是從集合的中間位置新增元素，ArrayList 花費的時間搞不好要比 LinkedList 少，因為 LinkedList 需要遍歷。
public class ArrayListTest {
public static void addFromMidTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
int temp = list.size();
list.add(temp / 2 + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("ArrayList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));
}
}
public class LinkedListTest {
public static void addFromMidTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
int temp = list.size();
list.add(temp / 2, i + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("LinkedList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));
}
}num 為 10000，代碼實測后的時間如下所示：
ArrayList從集合中間位置新增元素花費的時間1
LinkedList從集合中間位置新增元素花費的時間101
ArrayList 花費的時間比 LinkedList 要少很多很多。
如果是從集合的尾部新增元素，ArrayList 花費的時間應該比 LinkedList 少，因為數(shù)組是一段連續(xù)的內(nèi)存空間，也不需要復制數(shù)組；而鏈表需要創(chuàng)建新的對象，前后引用也要重新排列。
public class ArrayListTest {
public static void addFromTailTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(i + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("ArrayList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));
}
}
public class LinkedListTest {
public static void addFromTailTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(i + "沉默王二");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("LinkedList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));
}
}num 為 10000，代碼實測后的時間如下所示：
ArrayList從集合尾部位置新增元素花費的時間69
LinkedList從集合尾部位置新增元素花費的時間193
ArrayList 花費的時間比 LinkedList 要少一些。
這樣的結(jié)論和預期的是不是不太相符？ArrayList 在添加元素的時候如果不涉及到擴容，性能在兩種情況下（中間位置新增元素、尾部新增元素）比 LinkedList 好很多，只有頭部新增元素的時候比 LinkedList 差，因為數(shù)組復制的原因。
當然了，如果涉及到數(shù)組擴容的話，ArrayList 的性能就沒那么可觀了，因為擴容的時候也要復制數(shù)組。
1）ArrayList
ArrayList 刪除元素的時候，有兩種方式，一種是直接刪除元素（remove(Object)），需要直先遍歷數(shù)組，找到元素對應的索引；一種是按照索引刪除元素（remove(int)）。
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}但從本質(zhì)上講，都是一樣的，因為它們最后調(diào)用的都是 fastRemove(Object, int) 方法。
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}從源碼可以看得出，只要刪除的不是最后一個元素，都需要數(shù)組重組。刪除的元素位置越靠前，代價就越大。
2）LinkedList
LinkedList 刪除元素的時候，有四種常用的方式：
remove(int)，刪除指定位置上的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}先檢查索引，再調(diào)用 node(int) 方法（ 前后半段遍歷，和新增元素操作一樣）找到節(jié)點 Node，然后調(diào)用 unlink(Node) 解除節(jié)點的前后引用，同時更新前節(jié)點的后引用和后節(jié)點的前引用：
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;
}remove(Object)，直接刪除元素
public boolean remove(Object o) {
if (o == null) {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}也是先前后半段遍歷，找到要刪除的元素后調(diào)用 unlink(Node)。
removeFirst()，刪除第一個節(jié)點
public E removeFirst() {
final LinkedList.Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(LinkedList.Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final LinkedList.Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}刪除第一個節(jié)點就不需要遍歷了，只需要把第二個節(jié)點更新為第一個節(jié)點即可。
removeLast()，刪除最后一個節(jié)點
刪除最后一個節(jié)點和刪除第一個節(jié)點類似，只需要把倒數(shù)第二個節(jié)點更新為最后一個節(jié)點即可。
可以看得出，LinkedList 在刪除比較靠前和比較靠后的元素時，非常高效，但如果刪除的是中間位置的元素，效率就比較低了。
這里就不再做代碼測試了，感興趣的小伙伴可以自己試試，結(jié)果和新增元素保持一致：
我本地的統(tǒng)計結(jié)果如下所示，小伙伴們可以作為參考：
ArrayList從集合頭部位置刪除元素花費的時間380
LinkedList從集合頭部位置刪除元素花費的時間4
ArrayList從集合中間位置刪除元素花費的時間381
LinkedList從集合中間位置刪除元素花費的時間5922
ArrayList從集合尾部位置刪除元素花費的時間8
LinkedList從集合尾部位置刪除元素花費的時間12
1）ArrayList
遍歷 ArrayList 找到某個元素的話，通常有兩種形式：
get(int)，根據(jù)索引找元素
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}由于 ArrayList 是由數(shù)組實現(xiàn)的，所以根據(jù)索引找元素非常的快，一步到位。
indexOf(Object)，根據(jù)元素找索引
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}根據(jù)元素找索引的話，就需要遍歷整個數(shù)組了，從頭到尾依次找。
2）LinkedList
遍歷 LinkedList 找到某個元素的話，通常也有兩種形式：
get(int)，找指定位置上的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}既然需要調(diào)用 node(int) 方法，就意味著需要前后半段遍歷了。
indexOf(Object)，找元素所在的位置
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}需要遍歷整個鏈表，和 ArrayList 的 indexOf() 類似。
那在我們對集合遍歷的時候，通常有兩種做法，一種是使用 for 循環(huán)，一種是使用迭代器（Iterator）。
如果使用的是 for 循環(huán)，可想而知 LinkedList 在 get 的時候性能會非常差，因為每一次外層的 for 循環(huán)，都要執(zhí)行一次 node(int) 方法進行前后半段的遍歷。
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}那如果使用的是迭代器呢？
LinkedList<String> list = new LinkedList<String>();
for (Iterator<String> it = list.iterator(); it.hasNext();) {
it.next();
}迭代器只會調(diào)用一次 node(int) 方法，在執(zhí)行 list.iterator() 的時候：先調(diào)用 AbstractSequentialList 類的 iterator() 方法，再調(diào)用 AbstractList 類的 listIterator() 方法，再調(diào)用 LinkedList 類的 listIterator(int) 方法，如下圖所示。
最后返回的是 LinkedList 類的內(nèi)部私有類 ListItr 對象：
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new LinkedList.ListItr(index);
}
private class ListItr implements ListIterator<E> {
private LinkedList.Node<E> lastReturned;
private LinkedList.Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
}執(zhí)行 ListItr 的構(gòu)造方法時調(diào)用了一次 node(int) 方法，返回第一個節(jié)點。在此之后，迭代器就執(zhí)行 hasNext() 判斷有沒有下一個，執(zhí)行 next() 方法下一個節(jié)點。
由此，可以得出這樣的結(jié)論：遍歷 LinkedList 的時候，千萬不要使用 for 循環(huán)，要使用迭代器。
也就是說，for 循環(huán)遍歷的時候，ArrayList 花費的時間遠小于 LinkedList；迭代器遍歷的時候，兩者性能差不多。
看完上述內(nèi)容，你們掌握ArrayList 和 LinkedList 的區(qū)別有哪些的方法了嗎？如果還想學到更多技能或想了解更多相關內(nèi)容，歡迎關注億速云行業(yè)資訊頻道，感謝各位的閱讀！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
