Dynamic Data Structures

Linked lists, recursive type definitions, hash tables, arrays and pointers.

It is time to introduce a few fundamental data structures that will serve as building blocks for the creation of more complex objects. We will start with a dynamic array (actually a stack), a linked list and a string buffer. Then we will introduce hash tables, and finally we will put all these components together to form a string table--a data structure for efficient storage and retrieval of strings.

It's good to know that almost all of these data structures are available through the C++ standard library. A dynamic array is called a vector; there is also a list, a string and much more. There are, however, several reasons why I'd like you to first learn to implement these data structures without the use of the standard library. First, it will be a good exercise and a good way to learn the language step-by-step. Second, I want you to get an idea how these data structures might be implemented in the standard library. Third, the standard library uses very advanced features of the language (e.g., templates, operator overloading, etc.) which we haven't talked about yet. We'll get there in time, though.