Overview of Data Structures

This section provides an overview, in the form of a table, of the major data storage structures discussed in this book. This is a bird’s-eye view of a landscape that we’ll be covering later at ground level, so don’t be alarmed if it looks a bit mysterious.

Data Structure Advantages Disadvantages
Array Quick insertion, very fast access if index known. Slow search, slow deletion, fixed size.
Ordered array Quicker search than unsorted array. Slow insertion and deletion, fixed size.
Stack Provides last-in, first-out access. Slow access to other items.
Queue Provides first-in, first-out access. Slow access to other items.
Linked list Quick insertion, quick deletion. Slow search.
Binary tree Quick search, insertion, deletion (if tree remains balanced). Deletion algorithm is complex.
Red-black tree Quick search, insertion, deletion. Tree always balanced. Complex.
2-3-4 tree Quick search, insertion, deletion. Tree always balanced. Similar trees good for disk storage. Complex.
Hash table Very fast access if key known. Fast insertion. Slow deletion, access slow if key not known, inefficient memory usage.
Advertisements