2日目LinkedListソース分析
1860 ワード
LinkedListはチェーンテーブルの集合です.
LinkedListはRandomAccessインタフェースを実装していないことがわかり、for(int i=0;i
ノードのデータ構造から,
指定indexのelementを取得し,アルゴリズムは二分法を採用した.時間の複雑さではo(n)であるが,実際の計算では確かに1/2の時間を節約した.
peek()直接ヘッダノードに戻る
Poll()はヘッダノードに戻り、チェーンテーブルから削除します.
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
LinkedListはRandomAccessインタフェースを実装していないことがわかり、for(int i=0;i
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
ノードのデータ構造から,
LinkedListは双方向チェーンテーブルであることがわかる.チェーンテーブルの特性は、インタフェースの挿入と削除を容易にすることです./**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
isElementIndex、isPositionIndexは、インデックスがsizeである位置が挿入可能なビットであるが、既存のElementビットではないため、境界検査のための2つの方法を提供し、コードによって発見される./**
* Returns the (non-null) Node at the specified element index.
*/
Node node(int index) {
// assert isElementIndex(index);
//
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
指定indexのelementを取得し,アルゴリズムは二分法を採用した.時間の複雑さではo(n)であるが,実際の計算では確かに1/2の時間を節約した.
peek()直接ヘッダノードに戻る
Poll()はヘッダノードに戻り、チェーンテーブルから削除します.