The book explores the development of a series of key data structures using C and C++. The reader is taken on a graduated journey with each chapter leading to the development of a new C++ template class.
The data structures are:
A Linked List, including a double linked list that allows a look at list reversal and sorting.
A FiFo Queue class based upon a linked list looking at the benefits and subtle challenges of sub-classing.
A LiFo Stack class.
An introduction to binary trees that includes tree balancing techniques including the DSW algorithm which is a nice introduction to rotations.
An AVL self-balancing binary tree that maintains a near optimal balance through insertions and deletions.
A Red-Black tree that is optimised for frequent insertions and deletions.
A Splay tree optimised for repeated and frequent interaction with a sub-set of the tree data items.
A Map class based upon a Red-Black binary tree.
Hash tables – developing both the linear probing and separate chaining types.
A Vector class representing an efficient resizable array.
An introduction to binary heaps and the development of a priority queue based upon a heap.
A set class based upon a modified AVL tree.
The reader is presented with a range of iterator types and is introduced to template specialization.
The book includes C++ demonstration code for each data structure. Additional code samples are supplied for programmers targeting the Arduino IDE which has some variations.