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 Section 1.1.

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	2.1
ArrayDeque	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A	2.4
DualArrayDeque	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A	2.5
RootishArrayStack	$O(1)$	$O(1+\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$A	2.6
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}}\})$	3.2
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	3.3
SkiplistList	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E	4.3
USet implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
ChainedHashTable	$O(1)$E	$O(1)$AE	5.1
LinearHashTable	$O(1)$E	$O(1)$AE	5.2
SSet implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
SkiplistSSet	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E	4.2
Treap	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E	7.2
ScapegoatTree	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$A	8.1
RedBlackTree	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$	9.2
BinaryTrieI	$O(\ensuremath{\mathtt{w}})$	$O(\ensuremath{\mathtt{w}})$	13.1
XFastTrieI	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\ensuremath{\mathtt{w}})$AE	13.2
YFastTrieI	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\log \ensuremath{\mathtt{w}})$AE	13.3
(Priority) Queue implementations
	$\mathtt{findMin()}$	$\mathtt{add(x)}$/ $\mathtt{remove()}$
BinaryHeap	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$A	10.1
MeldableHeap	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$E	10.2

Footnotes

...#tex2html_wrap_inline38884#
^E

Denotes an expected running time. See Section 1.2.4.

...BinaryTrie^I

...

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