Java集合中のLinkdList
1842 ワード
Linked Listとは何ですか
1 Linked Listは、双方向テーブルの一般的な動作を定義する
2 Linked Listも
3 Linked Listも
順序アクセス:データは秩序化されており、アクセスも秩序化されており、要素を取得するためには、最初から相互参照を開始する必要があります。直接に配列で指定されたインデックスビットの値を取得することはできません。
ランダムアクセス:ランダムアクセスは、
双方向連結表データ構造及び関連操作
1.基本構造
双方向連結表に含まれる基本要素は、
2.基本操作(add、removeプロセスとは反対)
双方向テーブルにノードを挿入するときは、挿入位置の前後の2つのノードの直接前駆と直接後継の方向を変更する必要があります。
Linked Listの実現
Linked Listは内部ではプライベートな静的内部クラスを通して連結表を実現しています。内部コードは以下の通りです。
Linked Listのその他の関連内容
1.0とArayListの比較
両方のデータ構造はListとして使用できるが、性能とオーバーヘッドは異なる。ArayListはArayの実現として、強みは
2.0スレッド安全問題
Linked Listはスレッドが安全ではないことを実現します。スレッドを使用する場合は、安全なLinked Listを通過してください。
3.0同時修正異常
原理はArayList参照に類似している:ArayList
1 Linked Listは、双方向テーブルの一般的な動作を定義する
Doubly-linked list
双方向テーブルであり、Deque
インターフェースを実現する。2 Linked Listも
List
インターフェースを実現したので、List
に含まれる基本的な方法(新規、削除、挿入など)Linked Listが実現されました。3 Linked Listも
AbstractSequentialList
クラスにおいて
を定義するために必要な実装方法を継承している。順序アクセス:データは秩序化されており、アクセスも秩序化されており、要素を取得するためには、最初から相互参照を開始する必要があります。直接に配列で指定されたインデックスビットの値を取得することはできません。
ランダムアクセス:ランダムアクセスは、
ArrayList
のget(int index), set(int index, E element), add(int index, E element) and remove(int index)
など、指定されたインデックスビットの値をランダムアクセス方式で直接取得することができる。双方向連結表データ構造及び関連操作
1.基本構造
双方向連結表に含まれる基本要素は、
、 、
を含み、直接前駆者が前のノードアドレスを指し、直接に後のノードアドレスを指し、直接前駆者が空の場合は
で、直接に後継者が空の場合は
である。2.基本操作(add、removeプロセスとは反対)
双方向テーブルにノードを挿入するときは、挿入位置の前後の2つのノードの直接前駆と直接後継の方向を変更する必要があります。
Linked Listの実現
Linked Listは内部ではプライベートな静的内部クラスを通して連結表を実現しています。内部コードは以下の通りです。
transient Node first; //
transient Node last; //
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;
}
}
Linked Listの動作は、first last
の2つのオブジェクトをめぐって行われる。Linked Listのその他の関連内容
1.0とArayListの比較
両方のデータ構造はListとして使用できるが、性能とオーバーヘッドは異なる。ArayListはArayの実現として、強みは
上で、LinkdListは連表によって実現されると、その利点はここに現れます。
で動作します。2.0スレッド安全問題
Linked Listはスレッドが安全ではないことを実現します。スレッドを使用する場合は、安全なLinked Listを通過してください。
List list = Collections.synchronizedList(new LinkedList(...))
が取得する。3.0同時修正異常
原理はArayList参照に類似している:ArayList