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

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

Footnotes

...#tex2html_wrap_inline41201#
^A

Denotes an amortized running time. See Chapter 2.

...#tex2html_wrap_inline41235#
^E

Denotes an expected running time. See Section 1.2.4.

...#tex2html_wrap_inline41291#
^I

...

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