ATOS - Around The Operating System Das ATOS-Magazin 3/96

# Dynamische Datenstrukturen 6-6

Geschwindigkeit

Beim sortierten Einfügen ist unsere verkettete Liste schneller als ein Feld, da kein einziges Feldelement verschoben werden muß.

Ein Feld (Array) ist aber vor allem schneller beim Suchen. Das liegt hauptsächlich daran, daß man ein Feld meist nicht von vorne einzeln nach hinten durchsucht, sondern "Abkürzungen" benutzt (binäres Suchen).

Unsere verkettete Liste müssen wir aber von vorne nach hinten durchsuchen, da wir keine Ahnung haben, wo sich die einzelnen Einträge befinden.

Wie wir dem abhelfen können, erkläre ich in der nächsten ATOS. Sie können sich ja schon mal überlegen, was man mit einem 2. Zeiger in derselben Struktur alles anfangen kann, denn das ist Thema des 2. Teils über dynamische Datenstrukturen.

HW