Implementierung (doppelt verkettet):
Suchaufwand bei ungeordneter Liste
- erfolgreiche Suche cavg=(n+1)/2
(Standardannahme: zufällige Schlüsselauswahl, stochastische Unabhängigkeit der g. Schlüsselmenge)
Einfügen oder Löschen eines Elementes
- konstante Kosten für Einfügen am Listenanfang
- Löschen verlangt meist vorherige Suche
- konstante Löschkosten bei positionsbezogenem Löschen und Doppelverkettung
Sortierung bringt kaum Vorteile
- erfolglose Suche cavg=(n+1)/2
- lineare Kosten für Einfügen in Sortierreihenfolge