java - LinkedList はどのような意味でランダム アクセスをサポートしていないと言えますか?

Question

This articleは、LinkedListに「ランダムアクセスなし」があると述べています。誰か私にこれを説明できますか？

与えられた

LinkedList<String> l = new LinkedList<>();

それから私は使用することができます、

l.get(n);

これを考えると、なぜ記事は「ランダムアクセスなし」と言っているのですか?

Answer 1

ランダム アクセスとは、一定時間内に i 番目の要素を見つけることができることを意味します。より具体的には、リストのサイズ、または最初の要素、最後の要素、または中間の要素にアクセスしている場合には依存しません。

リンクされたリストを使用

i 番目の要素を見つけるには、最初の要素から i 番目の要素まですべての要素をトラバースする必要があります。したがって、最後の要素を取得するには、最初の要素よりもはるかに時間がかかります。したがって、これはランダム アクセスではありません。

配列あり

配列内の要素はメモリに連続して格納されます。したがって、A最初の要素のアドレスが分かっていて、各要素のサイズSが である場合、i 番目の要素のアドレスが直接わかりますA + i*S。この操作は、配列内のどの要素に対しても同じ時間を要しますが、それを取得するには十分です。したがって、配列はランダムアクセスです。

Answer 2

Java コレクションについて言うとき、それは RandomAccess インターフェイスを実装していないことを意味します

詳細については、ここで RandomAccessを参照してください。

Answer 3

get(n) を使用すると、リストの最初の n-1 要素をスキップします。index = n/2 の場合、検索はリストの最後から開始されます。