V листа

Из Википедије, слободне енциклопедије
V листа

V листа је структура података коју је осмислио Фил Багвел 2002. године. То је врста листе која комбинује брз приступ случајно изабраном елеменату и брзу експанзију листе. V листа захтева само log n меморије за складиштење показивача, где је n - број ставки у листи. Представља уобичајену листу низова чији је облик величине геометријске прогресије. Да би се пронашао елемент у V листи, неопходно је да се зна само адреса низа у ком је жељени елемент, као и индекс у низу. Просечна претрага налази случајни елемент након О(1) операција и O(log n) - у најгорем случају.