Java LinkedList
3714 ワード
Listインタフェースには2つの実装があり,1つはArrayList,もう1つはLinkedListである.文字通りArrayは配列を表し,Linkはチェーンテーブルを表し,区別が一目瞭然であることが分かるが,今日はLinkedListの反復器の実現を見る.
ノード定義:
典型的なチェーンテーブルノード構造ですね.
ArrayListではiteratorで反復器を取得できますが、残念ながらLinkedListにはありません.その基礎はlistIteratorです.
案の定、また一つの内部類です.
コードも実は簡単です.ポインタですね.
ノード定義:
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;
}
}
典型的なチェーンテーブルノード構造ですね.
ArrayListではiteratorで反復器を取得できますが、残念ながらLinkedListにはありません.その基礎はlistIteratorです.
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
案の定、また一つの内部類です.
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);
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();
}
}
コードも実は簡単です.ポインタですね.