1.7 List of Data Structures

Tables 1.1 and 1.2 summarize 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.2. 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 1.1: Summary of $ \mathtt{List}$ and $ \mathtt{USet}$ implementations.
% latex2html id marker 3692
\resizebox{.98\textwidth}{!}{
\begin{threeparttable...
...{Denotes an \emph{expected} running time.}
\end{tablenotes}\end{threeparttable}}



Table 1.2: Summary of $ \mathtt{SSet}$ and priority $ \mathtt{Queue}$ implementations.

\begin{threeparttable}
% latex2html id marker 2588\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=\textwidth ]{figs/dependencies}



opendatastructures.org