1.7: List of Data Structures — Read

From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

Tables \(\PageIndex{1}\) and \(\PageIndex{2}\) summarize the performance of data structures in this book that implement each of the interfaces, List, USet, and SSet, described in Section 1.2. Figure \(\PageIndex{1}\) shows the dependencies between various chapters in this book. A dashed arrow indicates only a weak dependency, in which only a small part of the chapter depends on a previous chapter or only the main results of the previous chapter.

Table \(\PageIndex{1}\): Summary of List and USet implementations.

\(\texttt{List}\) implementations

	\(\mathtt{get(i)}/\mathtt{set(i,x)}\)	\(\mathtt{add(i,x)}/\mathtt{remove(i)}\)
\(\texttt{ArrayStack}\)	\(O(1)\)	\(O(1+\mathtt{n}-\mathtt{i})\)^A	§ 2.1
\(\texttt{ArrayDeque}\)	\(O(1)\)	\(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\)^A	§ 2.4
\(\texttt{DualArrayDeque}\)	\(O(1)\)	\(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\)^A	§ 2.5
\(\texttt{RootishArrayStack}\)	\(O(1)\)	\(O(1+\mathtt{n}-\mathtt{i})\)^A	§ 2.6
\(\texttt{DLList}\)	\(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\)	\(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\)	§ 3.2
\(\texttt{SEList}\)	\(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\}/\mathtt{b})\)	\(O(\mathtt{b}+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\}/\mathtt{b})\)^A	§ 3.3
\(\texttt{SkiplistList}\)	\(O(\log \mathtt{n})\)^E	\(O(\log \mathtt{n})\)^E	§ 4.3

\(\texttt{USet}\) implementations

	\(\mathtt{find(x)}\)	\(\mathtt{add(x)}/\mathtt{remove(x)}\)
^ADenotes an amortized running time. ^EDenotes an expected running time.
\(\texttt{ChainedHashTable}\)	\(O(1)\)^E	\(O(1)\)^A,E	§ 5.1
\(\texttt{LinearHashTable}\)	\(O(1)\)^E	\(O(1)\)^A,E	§ 5.2

Table \(\PageIndex{2}\): Summary of SSet and priority Queue implementations.

\(\texttt{SSet}\) implementations

	\(\mathtt{find(x)}\)	\(\mathtt{add(x)}/\mathtt{remove(x)}\)
\(\texttt{SkiplistSSet}\)	\(O(\log \mathtt{n})\)^E	\(O(\log \mathtt{n})\)^E	§ 4.2
\(\texttt{Treap}\)	\(O(\log \mathtt{n})\)^E	\(O(\log \mathtt{n})\)^E	§ 7.2
\(\texttt{ScapegoatTree}\)	\(O(\log \mathtt{n})\)	\(O(\log \mathtt{n})\)^A	§ 8.1
\(\texttt{RedBlackTree}\)	\(O(\log \mathtt{n})\)	\(O(\log \mathtt{n})\)	§ 9.2
\(\texttt{BinaryTrie}\)^I	\(O(\mathtt{w})\)	\(O(\mathtt{w})\)	§ 13.1
\(\texttt{XFastTrie}\)^I	\(O(\log \mathtt{w})\)^A,E	\(O(\mathtt{w})\)^A,E	§ 13.2
\(\texttt{YFastTrie}\)^I	\(O(\log \mathtt{w})\)^A,E	\(O(\log \mathtt{w})\)^A,E	§ 13.3
\(\texttt{BTree}\)	\(O(\log \mathtt{n})\)	\(O(B+\log \mathtt{n})\)^A	§ 14.2
\(\texttt{BTree}\)^X	\(O(\log_B \mathtt{n})\)	\(O(\log_B \mathtt{n})\)	§ 14.2

(Priority) \(\texttt{Queue}\) implementations

	\(\mathtt{findMin()}\)	\(\mathtt{add(x)}/\mathtt{remove()}\)
^IThis structure can only store \(\texttt{w}\)-bit integer data. ^XThis denotes the running time in the external-memory model; see Chapter 14.
\(\texttt{BinaryHeap}\)	\(O(1)\)	\(O(\log \mathtt{n})\)^A	§ 10.1
\(\texttt{MeldableHeap}\)	\(O(1)\)	\(O(\log \mathtt{n})\)^E	§ 10.2

Figure \(\PageIndex{1}\): The dependencies between chapters in this book.

This page titled 1.7: List of Data Structures was last modified on Sat, 01 May 2021 15:12:21 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .

Contents

Text