LinkedList vs. ArrayList

[CodeIt]

Hallo,
ich lese immer wieder, dass ArrayList schneller beim indexbasierten Zugriff ist.
Beim Durchlaufen einer LinkedList wie im folgenden Beispiel mit einer
For-Schleife frage ich jedoch schon, ob dies auch hier so ist, dass der Zugriff auf
die LinkedList langsamer ist als auf eine ArrayList:

LinkedList<int> linkList = new LinkedList<int>();
linkList.add(1);
linkList.add(11);
linkList.add(111);
for(int i: linkList){
      System.out.println(i);
}

Hier wird doch lediglich durch die LinkedList iteriert, oder....warum sollte
der Zugriff hier langsamer sein als bei einer ArrayList welche anhand
einer for-Schliefe durchlaufen wird?


Vielen Dank

 

[Javinner]

Beide Namen sind Programm. W¨ahrend die Klasse ArrayList intern mit einem
Feld arbeitet, werden die Elemente von Objekten der Klasse LinkedList ¨uber
Referenzen miteinander
”
verlinkt“. Durch diese unterschiedlichen Speicherfor-
men, die Abbildung 12.3 verdeutlicht, ergeben sich f¨ur die beiden Klassen unter-
schiedliche Laufzeiten bei den Standardoperationen auf ihren Objekten. W¨ahrend
der Zugriff auf Elemente in ArrayList-Objekten in der Regel f¨ur alle Elemente
gleich schnell erfolgen kann, ist das Einf¨ugen und L¨oschen von Elementen (auf-
grund der notwendigen Verschiebungen der Feldelemente) wesentlich aufw¨andi-
ger als in LinkedList-Objekten, wo es gen¨ugt, die Referenzen auf die jeweiligen
Vorg¨anger- und Nachfolger-Objekte des neuen bzw. gel¨oschten Objekts richtig zu
setzen.

 

[Blender3D]

Der Zugriff in einem Array passiert mittels Index. Das bedeutet direkt. Wenn ich aber in einer Liste auf das 10te Element zugreifen will, muss ich die Liste vom Anfang bis zum 10ten Element durchlaufen bis ich darauf zugreifen kann. Das bedeutet: Deine Schleife muss bei jedem Zugriff bis zum jeweiligen Element laufen. Die ArrayList verwendet intern ein Array das bei Bedarf dynamisch vergrößert wird. ( Was dann ebenfalls etwas Zeit in Anspruch nimmt ). Sie kompensiert den Nachteil des Arrays, das wenn es einmal angelegt wurde eine maximale Größe hat und den oben erwähnten Zugriffsnachteil der Liste.

for(int i: linkList){
System.out.println(i);
}

So nicht, besser mittels Iterator dann ist sie gleichschnell wie ein Array, weil die Liste nur einmal durchlaufen wird.

    int[] array = { 1, 2, 3, 4, 5, 7, 8, 9, 10 };
        LinkedList<Integer> list = new LinkedList<Integer>();     
        for( int i = 0; i < array.length; i++ )
            list.add( array[i]);
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next().toString() +" ");

        }

 

[Xyz1]

So nicht, besser mittels Iterator dann ist sie gleichschnell wie ein Array,

Doch - es war schon richtig, int i : list ist einfach nur eine Umschreibung für einen Iterator.

Mit dem Rest hast du recht.

 

[mrBrown]

Wenn ich aber in einer Liste auf das 10te Element zugreifen will, muss ich die Liste vom Anfang bis zum 10ten Element durchlaufen bis ich darauf zugreifen kann. Das bedeutet: Deine Schleife muss bei jedem Zugriff bis zum jeweiligen Element laufen.

zusätzliche kleine Verbesserung: LinkedList läuft je nach Index vor- oder rückwärts, muss also maximal die halbe Liste und somit beim letzten Element also nur eins durchlaufen.

 

[Javinner]

So nicht, besser mittels Iterator dann ist sie gleichschnell wie ein Array, weil die Liste nur einmal durchlaufen wird

Iterator und erweitertes »for«
Stößt der Compiler auf ein erweitertes for, und erkennt er rechts vom Doppelpunkt den Typ Iterable, so erzeugt er Bytecode für eine Schleife, die den Iterator und seine bekannten Methoden hasNext() und next() nutzt

 

[CodeIt]

Vielen Dank an alle.
Da ich die Liste ja nur durchlaufen möchte, wäre in diesem Fall also die LinkedList genauso schnell wie die ArrayList.
Da ich aber weder in die Liste etwas löschen oder einfügen möchte, wäre hier dann evtl. doch ArrayList die bessere Wahl, da sie weniger Speicher benötigt als eine LinkedList.

 

[mrBrown]

ArrayList ist auch beim Durchlaufen schneller, wenn du sie überhaupt nicht veränderst ist sie sie bessere Wahl

 

[CodeIt]

Danke,
Vielleicht noch ein zusätzliche Frage: wenn ich jetzt z.B. durch die Liste iterieren möchte und bei jeder Iteration jeweils das erste Element entfernen möchte, was wäre dann besser?

 

[mrBrown]

Wenn du das erste Element entfernen willst wahrscheinlich eine LinkedList

 

[truesoul]

Danke,
Vielleicht noch ein zusätzliche Frage: wenn ich jetzt z.B. durch die Liste iterieren möchte und bei jeder Iteration jeweils das erste Element entfernen möchte, was wäre dann besser?

Hallo,

darauf hat der @mrBrown schon geantwortet.

EDIT: Oops. Zu langsam

Grüße

 

[Javinner]

LinkedList und ArrayList implementieren das Interface Iterable<E>, welches wiederum Iterator<T> iterator() Methode anbietet. Interface Iterator<E> bietet eine Methode remove() an, welches das Löschen eines Elementes aus der Liste erlaubt, jedoch kannst du das zu löschende Element nicht wählen:

public class Test
{

    public static void main(String[] args) throws IOException
    {

        LinkedList<Integer> lList = new LinkedList<>();
        lList.add(1);
        lList.add(2);
        lList.add(3);
        lList.add(4);
        lList.add(5);

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());
        lList.remove();

        Iterator it = lList.iterator();
        while (it.hasNext()) {
            System.out.println(it.hasNext());
            System.out.println(Arrays.asList(lList));
            lList.remove();
          
        }

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());

        lList.add(1);
        lList.add(2);
        lList.add(3);
        lList.add(4);
        lList.add(5);

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());
        lList.remove();
        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());

    }

}
/** Konsolenausgabe */
[[1, 2, 3, 4, 5]]
5
true
[[2, 3, 4, 5]]
true
[[3, 4, 5]]
true
[[4, 5]]
true
[[5]]
[[]]
0
[[1, 2, 3, 4, 5]]
5
[[2, 3, 4, 5]]
4

ArrayList hat jedoch listIterator() und listIterator(int index) Methoden von Interface ListIterator<E> geerbt, welches wiederum vom Interface Iterator<E> erbt.

 

[Javinner]

@CodeIt
Habe gerade nachgesehen: LinkedList bietet ebenso eine Methode remove(int index) an.

 

[CodeIt]

LinkedList und ArrayList implementieren das Interface Iterable<E>, welches wiederum Iterator<T> iterator() Methode anbietet. Interface Iterator<E> bietet eine Methode remove() an, welches das Löschen eines Elementes aus der Liste erlaubt, jedoch kannst du das zu löschende Element nicht wählen:

public class Test
{

    public static void main(String[] args) throws IOException
    {

        LinkedList<Integer> lList = new LinkedList<>();
        lList.add(1);
        lList.add(2);
        lList.add(3);
        lList.add(4);
        lList.add(5);

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());
        lList.remove();

        Iterator it = lList.iterator();
        while (it.hasNext()) {
            System.out.println(it.hasNext());
            System.out.println(Arrays.asList(lList));
            lList.remove();
        
        }

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());

        lList.add(1);
        lList.add(2);
        lList.add(3);
        lList.add(4);
        lList.add(5);

        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());
        lList.remove();
        System.out.println(Arrays.asList(lList));
        System.out.println(lList.size());

    }

}
/** Konsolenausgabe */
[[1, 2, 3, 4, 5]]
5
true
[[2, 3, 4, 5]]
true
[[3, 4, 5]]
true
[[4, 5]]
true
[[5]]
[[]]
0
[[1, 2, 3, 4, 5]]
5
[[2, 3, 4, 5]]
4

ArrayList hat jedoch listIterator() und listIterator(int index) Methoden von Interface ListIterator<E> geerbt, welches wiederum vom Interface Iterator<E> erbt.

Danke,
wäre dann folgender Code langsamer?:

Integer zahl;
while(lList.size() >0){
       zahl = lList.removeFirst();
}

 

[sascha-sphw]

wäre dann folgender Code langsamer?:

Warum testest Du es nicht einfach? Spiel doch einfach mal etwas damit herum.

 

[mrBrown]

Danke,
wäre dann folgender Code langsamer?:

Integer zahl;
while(lList.size() >0){
       zahl = lList.removeFirst();
}

Der Code entspricht einem zahl = lList.getLast(); lList.clear(), was auf jeden Fall schneller wäre...