1.5 List of Data Structures

The following table summarize the performance of data structures described in this book that implement each of the interfaces, List, USet, and SSet, described in .

List implementations
	$\mathtt{get(i)}$/ $\mathtt{set(i,x)}$	$\mathtt{add(i,x)}$/ $\mathtt{remove(i)}$
ArrayStack	$O(1)$	$O(1+\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$A
ArrayDeque	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A
DualArrayDeque	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A
RootishArrayStack	$O(1)$	$O(1+\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$A
DLList	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$
SEList	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\}/\ensuremath{\mathtt{b}})$	$O(\ensuremath{\mathtt{b}}+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\}/\ensuremath{\mathtt{b}})$A
SkiplistList	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
USet implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
ChainedHashTable	$O(1)$E	$O(1)$AE
LinearHashTable	$O(1)$E	$O(1)$AE
SSet implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
SkiplistSSet	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
Treap	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
ScapegoatTree	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$A
RedBlackTree	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$
BinaryTrieI	$O(\ensuremath{\mathtt{w}})$	$O(\ensuremath{\mathtt{w}})$
XFastTrieI	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\ensuremath{\mathtt{w}})$AE
YFastTrieI	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\log \ensuremath{\mathtt{w}})$AE
(Priority) Queue implementations
	$\mathtt{findMin()}$	$\mathtt{add(x)}$/ $\mathtt{remove()}$
BinaryHeap	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$A
MeldableHeap	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$E

Footnotes

...#tex2html_wrap_inline38840#
^E

Denotes an expected running time. See .

...BinaryTrie^I

...

This structure can only store $\mathtt{w}$-bit integer data.