LinkedList Update-Leistung in Java

Question

In diesem unteren Teil des Codes finde ich Entfernen der erste listnode immer und Drucken der ersten Knoten ist effizienter (in Bezug auf die Ausführungszeit) als die Liste intakt und Iterieren über alle Knoten. Ich habe mich gefragt, ob das der Fall ist, weil wenn ich immer den ersten Knoten entferne, ich nur den Startknoten zum nächsten Knoten aktualisieren muss und nur den ersten Knoten holen muss, um den Wert zu drucken. Im Falle der Iteration über die gesamte Liste, indem die Liste intact beibehalten wird, durchläuft die get-Operation die Liste jedesmal mit dem angegebenen Index und ruft den Wert ab. Nun sind meine Fragen: 1) Ist mein Verständnis richtig? 2) Müssen beide Möglichkeiten gleichzeitig ausgeführt werden? 3) Gibt es andere Gründe?

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

Ihre erste Überlegung ist richtig, der Punkt ist, dass ein LinkedList nicht mit wahlfreiem Zugriff effizient sein bedeutet. Jedes Mal, wenn Sie auf ein Element per Index zugreifen (zB lst.get(k)), müssen Sie dieses Element vom Anfang der Liste erreichen.

Aber das bedeutet nicht, dass ein LinkedList kann nicht effizient in Ihrer Situation verwendet werden, es ist nur, dass Sie versuchen, es als ArrayList zu verwenden. List<T> bietet Iterator<T>, die beim Iterieren über die Liste effizienter ist.

Zum Beispiel:

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

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

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

Dies wird die Liste iterieren, ohne das k -te Element bei jeder Iteration zu erreichen, da es den Überblick über alles, was im Innern des Iterator hält.

Tatsächlich könnte dies unter manchen Umständen sogar noch effizienter als ein ArrayList sein, da es die aufeinanderfolgenden Elemente nicht jedes Mal memove/shift muss, wenn Sie ein Element entfernen.

Answer 2

Ihre Beobachtung ist speziell in Bezug auf eine verknüpfte Liste korrekt und nur, weil Sie nach Index suchen. Java hat eine RandomAccess Schnittstelle, um List Implementierungen zu identifizieren, die in konstanter Zeit indiziert werden können, was zum Beispiel durch ArrayList implementiert wird, aber nicht durch LinkedList.

Wenn Sie einen Iterator verwendet, um die Liste stattdessen zu durchlaufen, würden Sie etwa die gleiche Leistung erhalten:

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