Data Structures and Algorithms with Object-Oriented Design Patterns in Java

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 consider arrays first. We review the support for arrays in Java and then show how to provide arrays with arbitrary subscript ranges, resizeable arrays, multi-dimensional arrays, and matrices. Next, we consider a number of linked list implementation alternatives and we discuss in detail the implementation of a singly-linked list class, LinkedList. It is important to become familiar with this class, as it is used extensively throughout the remainder of the book.