-
實(shí)現(xiàn)接口
LinkedList繼承關(guān)系
看上圖获茬，LinkedList和ArrayList稍微有不一樣的東西一汽，那就是RandomAccess和Deque蒲赂，實(shí)現(xiàn)了雙端隊(duì)列给梅，ArrayList實(shí)現(xiàn)RandomAccess遍歷，快速訪問显蝌，接口中說(shuō)理論for優(yōu)于Iterator迭代预伺。所以快速訪問，查找ArrayList優(yōu)于LinkedList曼尊，but增刪反之酬诀。查找迭代，說(shuō)實(shí)際的還不好確定骆撇，按文檔來(lái)說(shuō)是優(yōu)于LinkedList的瞒御。
Deque繼承Queue，api如下神郊，主要針對(duì)如隊(duì)列出隊(duì)列操作肴裙。
api
不同顏色操作不一樣，詳情后面文章會(huì)進(jìn)行介紹涌乳。
- 內(nèi)部實(shí)現(xiàn)原理
內(nèi)部使用Node<E>對(duì)象實(shí)現(xiàn)蜻懦，數(shù)據(jù)保存first和last對(duì)象：
實(shí)現(xiàn)
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;
}
}
就是使用prev和next保存數(shù)據(jù)的之間的關(guān)系，內(nèi)存不需要連續(xù)夕晓。學(xué)過數(shù)據(jù)結(jié)構(gòu)的應(yīng)該會(huì)熟悉宛乃。
-
Iterator實(shí)現(xiàn)
Iterator()方法返回listIterator實(shí)現(xiàn)。取得具體的遍歷對(duì)象使用下列方法：
Paste_Image.png
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index); // 這兒是調(diào)用上圖中遍歷取得的對(duì)象。使用next征炼，prev迭代析既。
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;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
好了，基本完成了谆奥。
