Java 7の集合タイプ第3編-LinkedList
11319 ワード
チェーンテーブルに基づいて実装される集合は、要素を検索する速度で配列に基づいて実装される集合に及ばないに違いないが、チェーンテーブル実装の最大の利点は、頻繁にノードを操作する場合、例えばノードを削除し、配列のように配列中の要素をコピーする必要がないことである.
まずAbstractSequencialList抽象クラスを見てみましょう.
上記のクラスでは、インデックスを含むパラメータが実装されています.(index)のいくつかの方法で、これらの方法はすべてリストにランダムにアクセスするものである.LinkedListの下位層の実装は双方向チェーンテーブルであるため、両端順でチェーンテーブルノードに素早く位置決めすることができる.ああ、自分でチェーンテーブルの集合を実現するには、この抽象クラスを継承したほうがいい.そうすれば、自分でこんなに多くの方法を実現するのに手間がかからない.
LinkedListはサブ構造Listの現実である.次のようになります.
Deque双方向キュー、Cloneable、javaなどの他のインタフェースを実現しています.io.Serializableは、構造をクローニングおよび直列化することができ、リストの下のサブインタフェースAbstractSequentialListは、構造を順次取得することができる.
次にLinkedListクラスを検討します.このクラスは双方向チェーンテーブルに基づいて実現されるので、両端で操作することができます.これには、先頭ノードを指す2つのポインタが必要です.
チェーンテーブルのNodeノードを内部のプライベートクラスで表すと、このノードの2つのポインタは、チェーンテーブルのindex番目の位置で処理されるノードを検索するなど、検索などの操作に便利になります.ソースコードは次のとおりです.
1、LinkedListの作成
コンストラクション関数を見てみましょう.
実際には、Collectionインタフェースを直接または間接的に実装するコレクションクラスには、2つのコンストラクション関数があります.1つはデフォルトの非パラメトリックコンストラクション関数です.もう1つはCollectionパラメータを集合とするコンストラクション関数である.2番目のコンストラクション関数では、他のセットの要素をチェーンテーブルのセットの要素に変換できます.
2、反復要素
双方向チェーンテーブルの構造が特殊であるため、反復的に要素を検索する場合、ArrayListなどの配列構造に基づく実装よりも時間がかかり、以下のようになる.
チェーンテーブルの操作に詳しい場合は、上記のコードが非常に簡単で、ここではあまり紹介しません.このようにhasNext()およびnext()メソッドを使用してノードを順次巡回することができ、この2つのメソッドを使用して逆巡回する場合は、コードの場合を使用して実現することができます.
次に例を挙げます.
a b c c b a
3、スタック操作
以下はもちろん双方向チェーンテーブルに対してノード操作を行い、チェーンテーブルの首尾ノードの削除、特定のノードの検索などの操作を含め、方法は簡単で、興味のある読者は自分で研究することができます.ちなみに、配列はスタック操作を実現するために使用することができ、チェーンテーブルも同様にでき、このクラスではpop()、push()などの方法が提供され、スタック操作を行う場合は、同様にこれらの方法を呼び出すことができます.ダブルチェーンテーブルの端で操作すればいいです.
4、クローンオブジェクト
このクラスはConableインタフェースも実装しているのでclone()メソッドを実装したが,このメソッドは浅いクローンのみを実装し,ソースコードは以下の通りである.
したがって、操作するノードのitemが基本タイプであれば、変更時に両者は影響しません.itemで参照タイプであれば,両者の値は相互に影響し合い,その場合は自己クローン法を用いなければならない.例を挙げます.
このときに印刷された値がttt、つまりクローンを修正した後の参照値は、元の値も修正され、深さでクローンされます.ソースコードを注意深く読んだ人は、チェーンテーブル要素をクローンする方法がclone方法と同じであることを発見します.以下のようにします.
だから使うときは特に注意しなければなりません.
5、ArrayListとLinkedListの比較
ArrayListは動的配列に相当する配列で実現される.配列はインデックスによって迅速に位置決めできるため、ランダムアクセス効率が高い.挿入と削除では配列全体が移動する場合があるため,ランダム挿入,ランダム削除の効率は低い.LinkedListは双方向チェーンテーブルです.スタック、キュー、または両端キューとして動作することもできます.LinkedListはランダムアクセス効率は低いが,ランダム挿入,ランダム削除の効率は高い.
異なる適用シーンに基づいて異なるセットを選択すると、プログラムの効率が向上します.
まずAbstractSequencialList抽象クラスを見てみましょう.
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() { }
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Bulk Operations
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.iterator();
while (e2.hasNext()) {
e1.add(e2.next());
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Iterators
public Iterator<E> iterator() {
return listIterator();
}
public abstract ListIterator<E> listIterator(int index);
}
上記のクラスでは、インデックスを含むパラメータが実装されています.(index)のいくつかの方法で、これらの方法はすべてリストにランダムにアクセスするものである.LinkedListの下位層の実装は双方向チェーンテーブルであるため、両端順でチェーンテーブルノードに素早く位置決めすることができる.ああ、自分でチェーンテーブルの集合を実現するには、この抽象クラスを継承したほうがいい.そうすれば、自分でこんなに多くの方法を実現するのに手間がかからない.
LinkedListはサブ構造Listの現実である.次のようになります.
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.SerializableDeque
次にLinkedListクラスを検討します.このクラスは双方向チェーンテーブルに基づいて実現されるので、両端で操作することができます.これには、先頭ノードを指す2つのポインタが必要です.
transient int size = 0; //
transient Node<E> first; //
transient Node<E> last; //
//
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;
}
}
チェーンテーブルのNodeノードを内部のプライベートクラスで表すと、このノードの2つのポインタは、チェーンテーブルのindex番目の位置で処理されるノードを検索するなど、検索などの操作に便利になります.ソースコードは次のとおりです.
//Returns the (non-null) Node at the specified element index.
// ， ，
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;
}
}1、LinkedListの作成
コンストラクション関数を見てみましょう.
public LinkedList() { } //
public LinkedList(Collection<? extends E> c) {//
this();
addAll(c);
}実際には、Collectionインタフェースを直接または間接的に実装するコレクションクラスには、2つのコンストラクション関数があります.1つはデフォルトの非パラメトリックコンストラクション関数です.もう1つはCollectionパラメータを集合とするコンストラクション関数である.2番目のコンストラクション関数では、他のセットの要素をチェーンテーブルのセットの要素に変換できます.
2、反復要素
双方向チェーンテーブルの構造が特殊であるため、反復的に要素を検索する場合、ArrayListなどの配列構造に基づく実装よりも時間がかかり、以下のようになる.
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();
}
}// end ListItr
チェーンテーブルの操作に詳しい場合は、上記のコードが非常に簡単で、ここではあまり紹介しません.このようにhasNext()およびnext()メソッドを使用してノードを順次巡回することができ、この2つのメソッドを使用して逆巡回する場合は、コードの場合を使用して実現することができます.
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}次に例を挙げます.
LinkedList<String> list=new LinkedList<>();
list.add("a");
list.add("b");
list.add("c");
Iterator sx=list.listIterator();
while(sx.hasNext()){
System.out.print(sx.next()+" ");
}
System.out.println();
Iterator nx=list.descendingIterator();
while(nx.hasNext()){
System.out.print(nx.next()+" ");
}a b c c b a
3、スタック操作
以下はもちろん双方向チェーンテーブルに対してノード操作を行い、チェーンテーブルの首尾ノードの削除、特定のノードの検索などの操作を含め、方法は簡単で、興味のある読者は自分で研究することができます.ちなみに、配列はスタック操作を実現するために使用することができ、チェーンテーブルも同様にでき、このクラスではpop()、push()などの方法が提供され、スタック操作を行う場合は、同様にこれらの方法を呼び出すことができます.ダブルチェーンテーブルの端で操作すればいいです.
4、クローンオブジェクト
このクラスはConableインタフェースも実装しているのでclone()メソッドを実装したが,このメソッドは浅いクローンのみを実装し,ソースコードは以下の通りである.
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
public Object clone() { //
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}したがって、操作するノードのitemが基本タイプであれば、変更時に両者は影響しません.itemで参照タイプであれば,両者の値は相互に影響し合い,その場合は自己クローン法を用いなければならない.例を挙げます.
LinkedList<Number> list=new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
for(Number i:list){
System.out.println(i);// 1 2 3 4
}
LinkedList<Number> l=(LinkedList<Number>) list.clone();
l.add(5);
l.set(2, 33);
for(Number i:l){
System.out.println(i);// 1 2 33 4 5
}String[] x={"a","c"};
String[] y={"m","n"};
LinkedList<String[]> list=new LinkedList<>();
list.add(x);
list.add(y);
LinkedList<String[]> l=(LinkedList<String[]>) list.clone();
l.get(1)[1]="ttttt";
System.out.println(list.get(1)[1]);このときに印刷された値がttt、つまりクローンを修正した後の参照値は、元の値も修正され、深さでクローンされます.ソースコードを注意深く読んだ人は、チェーンテーブル要素をクローンする方法がclone方法と同じであることを発見します.以下のようにします.
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;
} public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}だから使うときは特に注意しなければなりません.
5、ArrayListとLinkedListの比較
ArrayListは動的配列に相当する配列で実現される.配列はインデックスによって迅速に位置決めできるため、ランダムアクセス効率が高い.挿入と削除では配列全体が移動する場合があるため,ランダム挿入,ランダム削除の効率は低い.LinkedListは双方向チェーンテーブルです.スタック、キュー、または両端キューとして動作することもできます.LinkedListはランダムアクセス効率は低いが,ランダム挿入,ランダム削除の効率は高い.
異なる適用シーンに基づいて異なるセットを選択すると、プログラムの効率が向上します.