verkettete Listen

[Namenloser]

Zitat von Stevie:

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Die gehen aber offensichtlich davon aus, dass man das Element erst noch suchen muss. Das ist ein bisschen unfair der verketteten Liste gegenüber. Denn an sich geht das Einfügen oder Löschen eines Elements in einer verketteten Liste – wenn man den Pointer schon hat – in konstanter Zeit, weil man ja nur zwei Pointer umbiegen muss. Beim Array dagegen muss man immer alle Elemente nach dem gelöschten bzw. eingefügten Element umkopieren, was mit der Anzahl der Elemente linear ansteigt. Gerade da spielt die verkettete Liste ja ihre Stärke aus. Das ist normalerweise genau der Grund, warum man sich für eine verkettete Liste entscheidet.

Bei sehr kleinen Listen (so in der Größenordnung <100 Elemente) ist allerdings das Array oft trotzdem schneller. Es kommt natürlich auch immer darauf an, ob man mehr liest oder mehr schreibt. Wenn man fast nur liest, dann kann das Array auch bei größeren Listen Sinn machen.