Java Reference
In-Depth Information
665
Chapter 15 An Introduction to Data Structures
C
HAPTER
G
OALS
ȗ 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 types
Up to this point, we 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 what
fundamental operations 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.
665
666
15.1 Using Linked Lists
A linked list is a data structure used for collecting a sequence of objects, which 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 the sequence. Unless the
company happened to hire employees in dictionary order, the new object probably
needs to be inserted somewhere near the middle of the sequence. If we use an array to
