Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Foundational Data Structures

In this book we consider a variety of abstract data types (ADTs) , including stacks, queues, deques, ordered lists, sorted lists, hash and scatter tables, trees, priority queues, sets and graphs. In just about every case, we have the option of implementing the ADT using an array or using a some kind of linked data structure.

Because they are the base upon which almost all of the ADTs are built, we call the array and the linked list the foundational data structures . It is important to understand that we do not view the array or the linked list as ADTs, but rather as alternatives for the implementation of ADTs.

In this chapter we discuss in detail the implementation of two classes, Array<T> and LinkedList<T>, that embody the foundational data structures. It is important to become familiar with these classes, as they are used extensively throughout the remainder of the book.