1.6 List of Data Structures

Tables 1.1 and 1.2 summarizes the performance of data structures in this book that implement each of the interfaces, $\mathtt{List}$ , $\mathtt{USet}$ , and $\mathtt{SSet}$ , described in Section 1.1. Figure 1.6 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:** Summary of $\mathtt{List}$ and $\mathtt{USet}$ implementations.
$\begin{threeparttable} % latex2html id marker 2292\begin{tabular}{\vert l\vert... ...]{Denotes an \emph{expected} running time.} \end{tablenotes}\end{threeparttable}$

**Table:** Summary of $\mathtt{SSet}$ and priority $\mathtt{Queue}$ implementations.
$\begin{threeparttable} % latex2html id marker 2380\begin{tabular}{\vert l\vert... ...\ensuremath{\mathtt{w}}-bit integer data.}\end{tablenotes}\end{threeparttable}$

**Figure 1.6:** The dependencies between chapters in this book.
$\includegraphics[width=.95\textwidth]{figs/dependencies}$

opendatastructures.org