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, $\mathtt{List}$, $\mathtt{USet}$, and $\mathtt{SSet}$, described in .

$\mathtt{List}$ implementations
	$\mathtt{get(i)}$/ $\mathtt{set(i,x)}$	$\mathtt{add(i,x)}$/ $\mathtt{remove(i)}$
$\mathtt{ArrayStack}$	$O(1)$	$O(1+\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$A
$\mathtt{ArrayDeque}$	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A
$\mathtt{DualArrayDeque}$	$O(1)$	$O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$A
$\mathtt{RootishArrayStack}$	$O(1)$	$O(1+\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$A
$\mathtt{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}}\})$
$\mathtt{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
$\mathtt{SkiplistList}$	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
$\mathtt{USet}$ implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
$\mathtt{ChainedHashTable}$	$O(1)$E	$O(1)$AE
$\mathtt{LinearHashTable}$	$O(1)$E	$O(1)$AE
$\mathtt{SSet}$ implementations
	$\mathtt{find(x)}$	$\mathtt{add(x)}$/ $\mathtt{remove(x)}$
$\mathtt{SkiplistSSet}$	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
$\mathtt{Treap}$	$O(\log \ensuremath{\mathtt{n}})$E	$O(\log \ensuremath{\mathtt{n}})$E
$\mathtt{ScapegoatTree}$	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$A
$\mathtt{RedBlackTree}$	$O(\log \ensuremath{\mathtt{n}})$	$O(\log \ensuremath{\mathtt{n}})$
$\mathtt{BinaryTrie}$I	$O(\ensuremath{\mathtt{w}})$	$O(\ensuremath{\mathtt{w}})$
$\mathtt{XFastTrie}$I	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\ensuremath{\mathtt{w}})$AE
$\mathtt{YFastTrie}$I	$O(\log \ensuremath{\mathtt{w}})$AE	$O(\log \ensuremath{\mathtt{w}})$AE
(Priority) $\mathtt{Queue}$ implementations
	$\mathtt{findMin()}$	$\mathtt{add(x)}$/ $\mathtt{remove()}$
$\mathtt{BinaryHeap}$	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$A
$\mathtt{MeldableHeap}$	$O(1)$	$O(\log \ensuremath{\mathtt{n}})$E

Footnotes

...#tex2html_wrap_inline41284#
^A

Denotes an amortized running time. See .

...#tex2html_wrap_inline41318#
^E

Denotes an expected running time. See .

...#tex2html_wrap_inline41374#
^I

...

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