Big Java, 4th Edition

Chapter 15. An Introduction to Data Structures

CHAPTER GOALS

• To learn how to use the linked lists provided in the standard library

• To be able to use iterators to traverse linked lists

• To understand the implementation of linked lists

• To distinguish between abstract and concrete data types

• To know the efficiency of fundamental operations of lists and arrays

• To become familiar with the stack and queue data types

Up to this point, we have used arrays as a one-size-fits-all mechanism for collecting objects. However, computer scientists have developed many different data structures that have varying performance tradeoffs. In this chapter, you will learn about the linked list, a data structure that allows you to add and remove elements efficiently, without moving any existing elements. You will also learn about the distinction between concrete and abstract data types. An abstract type spells out the fundamental operations that should be supported efficiently, but it leaves the implementation unspecified. The stack and queue types, introduced at the end of this chapter, are examples of abstract types.

Using Linked Lists

A linked list is a data structure used for collecting a sequence of objects that allows efficient addition and removal of elements in the middle of the sequence.

To understand the need for such a data structure, imagine a program that maintains a sequence of employee objects, sorted by the last names of the employees. When a new employee is hired, an object needs to be inserted into ...