JavaでLinkedListの更新パフォーマンス

Question

このコードの部分では、最初のリストノードを常に削除し、リストをそのままにしてすべてのノードを反復するよりも、最初のノードを印刷するほうが効率的です（実行時間に関して）。これは、最初のノードを削除するときに、開始ノードを次のノードに更新して、最初のノードをフェッチして値を出力するだけで済むからです。 list intanctを保持することによってリスト全体を反復処理する場合、get操作は毎回指定されたインデックスにリストをトラバースして値を取得します。 私の質問は以下の通りです： 1）私の理解は正しいですか？ 2）両方の方法で同時に実行する必要があります 3）他に推論がありますか？

public class Ddbrw { 
public List<Integer> ListValidation() 
    { 
     List<Integer> lst = new LinkedList<>(); 
     for(int i = 0; i < 20; i++){ 
     lst.add(new Integer(1)); lst.add(new Integer(5)); 
     lst.add(new Integer(9)); lst.add(new Integer(7)); 
     lst.add(new Integer(5)); lst.add(new Integer(61)); 
     lst.add(new Integer(8)); lst.add(new Integer(12)); 
     } 
     return lst; 
    } 

public static void main(String[] args) 
    { 
    Ddbrw obj = new Ddbrw(); 
    Ddbrw obj2 = new Ddbrw(); 

    List<Integer> lst = obj2.ListValidation(); 
    int size = lst.size(); 
    long startTime = System.currentTimeMillis(); 
    for(int i = 0; i < size; i++) { 
     System.out.print(lst.get(i)); 
    } 
    long endTime = System.currentTimeMillis(); 
    System.out.println("*************"); 
    System.out.println(endTime-startTime); 
    System.out.println("*************"); 

    List<Integer> lst2 = obj.ListValidation(); 
    long startTime1 = System.currentTimeMillis(); 
    for(int k = 0; k < lst2.size();) { 
     System.out.print(lst2.get(k)); 
     lst2.remove(k); 
    } 
    long endTime1 = System.currentTimeMillis(); 
    System.out.println("*************"); 
    System.out.println(endTime1-startTime1); 
    System.out.println("*************"); 
    } 
} 

Answer 1

あなたの最初の推論はポイントがLinkedListがランダムアクセスと効率的であることを意味していないことで、正しいです。したがって、インデックス（たとえばlst.get(k)）で要素にアクセスするたびに、その要素の先頭から要素に到達する必要があります。

しかし、これはLinkedListがあなたの状況で効率的に使用できないことを意味するものではなく、単にArrayListとして使用しようとしていることを意味します。 List<T>にはIterator<T>があり、これはリストを反復処理するとより効率的です。例えば

は：

Iterator<Integer> it = lst.iterator(); 

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

for (int i : lst) 
    System.out.println(i); 

これは、イテレータ内のすべてのトラックを保持するので、各反復でk番目の要素に到達することなく、リストを反復処理します。

実際には、要素を削除するたびに連続する要素を削除したり移動したりする必要がないため、状況によってはArrayListより効率的です。

Answer 2

あなたの所見は、リンクされたリストに関しては、特にあなたが索引ごとにトラバースしているためにのみ正しいです。 Javaは、の実装を特定するためのRandomAccessインターフェイスを持っています。この実装は、たとえばArrayListで実装されていますが、LinkedListでは実装されていません。

あなたの代わりに、リストを横断するイテレータを使用した場合、あなたはほぼ同じ性能を得るでしょう：

for (Integer i : lst) { 
    System.out.println(i); 
}