V-listă

V-list este o structură de date dezvoltată de Phil Bagwell în 2002 . V-list combină accesul rapid la elemente aleatorii și extinderea rapidă a listei. Lista V necesită doar log n memorie suplimentară pentru a stoca pointerii, unde n este numărul de elemente din listă. O listă V constă dintr-o listă obișnuită de tablouri ale căror dimensiuni formează o progresie geometrică . Pentru a găsi un element în lista V, trebuie doar să știți adresa matricei în care se află elementul dorit și indexul acestuia în acest tablou. În medie, găsirea unui element aleatoriu necesită operații O(1), iar O(log n) este cel mai rău caz.

Literatură

Link -uri