写真のデータ構造。 LinkedList

こんにちは、ハラジテリ！

私が始めたもの、つまり、いくつかのデータ構造がJavaでどのように実装されているかを（視覚的なイメージを使用して）伝えようとしています。



前回ArrayListについて話しましたが、今日はLinkedListを調べています。

LinkedList-Listインターフェースを実装します。 これは、構造の各要素が前の要素と次の要素へのポインタを含む双方向リストの代表です。 反復子は往復をサポートします。 リストの最初、中央、および最後に取得、削除、貼り付けのメソッドを実装します。 nullを含む任意の要素を追加できます。

オブジェクト作成

List<String> list = new LinkedList<String>(); 

Footprint{Objects=2, References=4, Primitives=[int x 2]}
Object size: 48 bytes

新しく作成されたリストオブジェクトには、 ヘッダーとサイズのプロパティが含まれています。

header-リストの擬似要素。 その値は常にnullであり、プロパティnextおよびprevは、常にリストの最初と最後の要素をそれぞれ指します。 リストはまだ空であるため、 nextプロパティとprevプロパティは自分自身（つまり、 ヘッダー要素）を指します。 サイズリストのサイズは0です。

 header.next = header.prev = header; 

アイテムを追加する

 list.add("0"); 

Footprint{Objects=5, References=8, Primitives=[int x 5, char]}
Object size: 112 bytes

add（value） 、 addLast（value）メソッドを使用してリストの最後にアイテムを追加します
また、 addFirst（値）を使用してリストの先頭に追加することは、O（1）時間で行われます。

LinkedListクラスの内部には、新しい要素が作成される静的な内部Entryクラスがあります。

 private static class Entry<E> { E element; Entry<E> next; Entry<E> prev; Entry(E element, Entry<E> next, Entry<E> prev) { this.element = element; this.next = next; this.prev = prev; } } 

新しい要素を追加するたびに、実際には2つの手順が実行されます。

1） エントリクラスの新しい新しいインスタンスが作成されます

 Entry newEntry = new Entry("0", header, header.prev); 

2）前と次の要素へのポインタが再定義されます

 newEntry.prev.next = newEntry; newEntry.next.prev = newEntry; size++; 

別のアイテムを追加

 list.add("1"); 

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

1）

 // header.prev      0 Entry newEntry = new Entry("1", header, header.prev); 

2）

リストの中央にアイテムを追加する

リスト内の特定の位置に要素を追加するには、 add（index、value）メソッドを呼び出す必要があります。 add（value）との違いは、挿入が実行される前の要素の定義です

 (index == size ? header : entry(index)) 

エントリ（インデックス）メソッドは、指定されたインデックスを持つ要素を探してリストを検索します。 トラバースの方向は、条件（インデックス<（サイズ>> 1））によって決まります。 実際、目的の要素を見つけるためにリストの半分以下が検索されますが、漸近解析の観点からは、検索時間は線形に増加します-O（n）。

 private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.prev; } return e; } 

ご覧のとおり、指定されたインデックスが負であるか、現在のサイズより大きい場合、開発者はIndexOutOfBoundsExceptionをキャッチできます 。 これは、パラメータにインデックスが表示されるすべてのメソッドに当てはまります。

 list.add(1, "100"); 

Footprint{Objects=11, References=16, Primitives=[int x 11, char x 5]}
Object size: 248 bytes

1）

 // entry      1, entry.prev     0 Entry newEntry = new Entry("100", entry, entry.prev); 

2）

アイテムを削除する

リストからアイテムを削除するには、いくつかの方法があります。
-リストの先頭または末尾から、O（1）の間にremoveFirst（） 、 removeLast（）を使用します 。
- 削除（インデックス）インデックスおよびO（n）時間中の削除（値）値による。

値による削除を検討する

 list.remove("100"); 

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

remove（値）メソッド内で、リストのすべての要素がスキャンされ、正しい要素が検索されます。 最初に見つかったアイテムのみが削除されます。

一般に、リストからの削除は条件付きで3つのステップに分けることができます。

1）対応する値を持つ最初の要素を検索する



2）前と次の要素へのポインタが再定義されます

 //     //         E result = e.element; e.prev.next = e.next; e.next.prev = e.prev; 

3）他の要素へのポインタの削除および要素自体の忘却

 e.next = e.prev = null; e.element = null; size--; 

イテレータ

独自の要素の列挙には、「組み込み」イテレーターを使用できます。 私は深く行きません。内部で行われるプロセスは上記のプロセスと非常に似ています。

 ListIterator<String> itr = list.listIterator(); 

上記のコードは、ポインターをリストの一番上に置きます。 特定の場所から要素の繰り返しを開始することもできます。そのためには、インデックスをlistIterator（インデックス）メソッドに渡す必要があります。 リストの最後からクロールを開始する必要がある場合は、 descendingIterator（）メソッドを使用できます。

イテレータを作成した後、リストが独自のイテレータメソッドで変更されなかった場合、 ListIteratorは ConcurrentModificationExceptionで落ちることに注意してください 。

念のため、要素を列挙する基本的な例：

 while (itr.hasNext()) System.out.println(itr.next()); 

まとめ

-LinkedListから、アクセス時間O（1）でスタック、キュー、またはダブルキューを整理できます。
-インデックスまたは値でアイテムを取得するには、リストの中央から挿入および削除するのに線形時間O（n）がかかります。 ただし、ListIterator.add（）およびListIterator.remove（）を使用してリストの中央から追加および削除するには、O（1）が必要です。
-nullを含む任意の値を追加できます。 プリミティブ型のストレージには、対応するラッパークラスを使用します。
-同期されていません。

参照資料

LinkedListソース
JDK7のLinkedList
JDKがOpenJDKとTrade 6のソースリリースをソース-ビルドb23

占有メモリの量は、 メモリ測定ツールを使用して測定されました。 また、 Guava （Google Core Libraries）を使用する必要があります。