10

定義上、リンクリストは、その各要素が次の要素（および二重リンクリストについて話している場合は前の要素）を参照するリストです 。http：//en.wikipedia.org/wiki/Linked_list

ただし、Javaでは、LinkedListはList、Queue、Dequeなどを実装しています。 http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html

LinkedListには、リスト内の次または前のオブジェクトを提供するメソッドが見つかりません。できる最善の方法は、イテレーターを取得してオブジェクトを取得することです。私の質問は、Javaがこのデータ構造をLinkedListと呼んでいるのに、実際にはリンクリストではないのはなぜですか？リンクリストは、次のようにJavaで実装できます。

Public class MyLinkedList{
 public int value;
 public MyLinkedList next;
}
4

7 に答える 7

9

リスト内の次または前のオブジェクトを提供するメソッドがLinkedListに見つかりません

いいえ、それは完全に適切です。「リストの次のアイテム」という考えは、リストでは意味がありません。リスト内のノードには完全に理にかなっていますが、それはJavaAPIによって公開されるものではありません。もちろん、それは内部に存在します-ただ公開されていません。リストを反復処理する場合は、イテレータを使用します。開始または終了時に追加したり、開始または終了から削除したり、イテレータから追加/削除したりすることもできます。

提案されたサンプルコードのように「ノード」と「リスト」の概念を混同することは確かにできますが、一般的には良い考えではないと思います。

別の言い方をすれば、問題を引き起こしていることを達成しようとしていますか？パブリックAPIを使用して、やりたいことができるはずだと思います。すべてに気付いていないかもしれません。

于 2013-02-11T16:59:24.437 に答える
6

私の質問は、Javaがこのデータ構造をLinkedListと呼んでいるのに、実際にはリンクリストではないのはなぜですか？

それの実装はリンクリストだからです。ドキュメントから：

ListおよびDequeインターフェイスの二重リンクリストの実装。すべてのオプションのリスト操作を実装し、すべての要素（を含むnull）を許可します。

LinkedListはListリンクリストを介して実装され、ArrayListはList配列などを使用して実装されます。どちらを選択するかは、実行時の特性の観点から重要です。たとえば、LinkedListドキュメントから：

すべての操作は、二重リンクリストで期待できるとおりに実行されます。リストにインデックスを付ける操作は、リストの最初または最後のどちらか、指定されたインデックスに近い方からトラバースします。

たとえば、あなたはあなたがそこから得るか、非常に効率的であることを知ってnextいIteratorますiteratorがlistIterator、getインデックスによるそれはトラバーサルを含みます。

于 2013-02-11T16:58:09.783 に答える
4

コレクションがリンクリストであるか配列リストであるかは、そのコントラクトではなく、その実装に関するものです。LinkedList確かに、実装別およびjava.util.List契約別のリンクリストです。

それが示すのはAPIではなく、リンクリストに精通している人なら誰でも簡単に予測できる空間/時間の複雑さの特性です。

参考までに、これはLinkedListノードの実際の実装であり、期待に非常によく一致します。

957  プライベート 静的 クラスNode<E>{ 
958E      アイテム; 
959      ノード<E>次; 
960      ノード<E>prev; 
962       Node（Node <E> prev、E element、Node <E> next）{ 
963           this .item = element; 
964           this .next = next; 
965           this .prev = prev; 
966       } 
967   }

于 2013-02-11T16:58:27.817 に答える
2

あなたの質問を読んでいると、リンクリストの概念とリンクリストの実装をうまく区別していないように感じました。

サンプルコードはリンクリストの概念を非常によく示していますが、それがリンクリストを実装する唯一の方法または最良の方法であるという意味ではありません。LinkedListデータ構造クラスや教科書に見られるような見慣れないAPIのセットが表示される場合がありますが、組み込みクラスを使用して、標準のリンクリストに伴うすべての操作を実行できると思います。

したがって、基本的には、配列などの他のデータ構造の時間計算量とは対照的に、時間内に挿入操作、O(1)時間内に削除操作、O(1)時間内に検索操作などを実行できる限り、リンクリストです。O(n)

ビルトインは、操作を直接LinkedList提供するのではなくnext、イテレーターを介して提供しました。Iteratorパターンの恩恵を受ける可能性があるため、これはJava言語の設計上の決定にすぎませんでした。

そして、Javaは典型的なオブジェクト指向言語であり、その主な特徴の1つは抽象化です。

于 2013-02-11T17:48:00.307 に答える
1

他の人による正解に加えて、インターフェースの基礎となる実装がリンクリストである場合、実装オブジェクトには、リスト内の次の項目を取得するためのメソッドがあります。その方法は、契約の一部として公開されていないだけです。

実装がリンクリストであるという事実は、リストコントラクトのさまざまなメソッドのBig-Oパフォーマンスに影響を与えます。

于 2013-02-11T17:00:22.660 に答える
0

ただし、Javaでは、LinkedListはList、Queue、Dequeなどを実装しています。

APIによると、LinkedListはこれらのインターフェースを実装しているため、これらの構造のいずれでも使用できます。

于 2013-02-11T17:04:15.590 に答える
0

したがって、@ Markoがその実装をどこから読み取ったのかはわかりませんが、1.8jdkの実装は大きく異なります。

まず、宣言された最初の変数は次のとおりです。

 transient int size = 0;

その値は、ノードがリストに追加されるたびに増分されます。これは、リスト内のInteger.MAX_VALUE（2147483647）ノードに固有の制限があることを意味します。現代の世界では、その数は見た目ほど大きくはありません。問題は、実際のリンクリストがないことではありません（作成するのは簡単です）が、すべてのサードパーティライブラリでは、これを考慮していない可能性が高く、ライブラリ全体が混乱します。

于 2019-04-12T15:08:26.353 に答える