Wir verwenden Arrays als Datenstruktur, um eine Liste von Elementen desselben Datentyps zu speichern. Diese Elemente werden nebeneinander oder zusammen in Folge an zusammenhängenden Speicherorten gespeichert. Das bedeutet, dass wir sehr gut über den Index des Arrays auf das Element zugreifen können. Ein Array mit Integers würde bspw. 4Bytes im Memory benötigen.
Arrays sind wahrscheinlich die Datenstruktur, mit der wir am
häufigsten arbeiten. Im Code sind Arrays eine Sammlung von Werten, die
zwischen eckigen Klammern gespeichert werden. Diese Werte werden im
Speicher zugewiesen. Jeder Wert in einem Array enthält einen
numerischen Index in aufsteigender Reihenfolge vom ersten zum letzten.
Das heißt der Speicher für Arrays wird zugewiesen bzw. vorab
festgelegt. Ihre Größe kann ohne entsprechende Algorithmen nicht
verändert werden (dazu gleich mehr). Außerdem sind Arrays
null-indiziert, was bedeutet, dass der erste Index in einem Array
nicht 1 ist, sondern 0. Arrays sind statisch, ihre Größe kann nicht
flexibel verändert werden. Deshalb müssen wir schätzen, wieviel Platz
wir brauchen. Wenn es zu wenig Platz ist, müssen wir den Array
nachträglich verändern - nicht gut. Deshalb kann man sich an die
einfache Faustregel richten: Wenn man die Zahl der Elemente vorab
weiß, sollte man Arrays nutzen. Andernfalls greift man besser auf
andere Datenstrukturen zurück.
Search
by Index: O(1)
by Value: O(n)
Insert
Beginning/End: O(n)
Middle: O(n)
Delete
Beginning: O(n)
Middle: O(n)
End: O(n)