V листа

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

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