zum Inhalt springen

Vor- und Nachteile von Arrays und Vektoren

Wenn Elemente im Array bewegt werden müssen (weil z. B. ein Element gelöscht wird und die anderen "aufrücken" müssen), oder wenn die Größe eines Arrays nicht mehr ausreicht, wird es i.d.R. in ein neues Array umkopiert. Dies kostet Zeit, die abhängig von der Anzahl der Elemente im Array ist. Verkettete Listen bieten hier eine Alternative, die die Operationen "Einfügen" und "Entfernen" in konstanter Zeit ermöglicht.

Verkettete Listen bestehen - in einer objektorientierten Sprache - aus einzelnen "Knoten", die jeweils zwei Objekte speichern: Zum einen die eigentlichen "Nutzdaten", zum anderen enthält jeder Knoten eine Referenz auf seinen Nachfolger, wie folgende Grafik veranschaulichen soll:

 

Ist eine Referenz auf den ersten Knoten bekannt, so kann die Liste durchlaufen werden - das letzte Element ist dadurch zu erkennen, dass sein "next"-Zeiger auf "null" zeigt.

Im Gegensatz zu Arrays muss in dieser Form der Collection nicht viel gemacht werden, um ein Element an beliebiger Stelle einzufügen oder zu löschen - es müssen lediglich einige Zeiger in der Liste "umgebogen" werden:


Wird zusätzlich neben dem "Sonderknoten" first noch ein Knoten "last" genutzt, der das Ende der Liste repräsentiert, so ist das Einfügen am Ende der Liste in konstanter Zeit möglich, unabhängig davon, wie viele Elemente die Liste bereits enthält:

Das Suchen nach einem Element ist jedoch nach wie vor schwierig - im schlimmsten Fall ist das gesuchte Element nicht in der Liste, was jedoch erst dann feststeht, wenn jedes Element betrachtet wurde.