IMPLEMENTING LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 896

24.1 Introduction
This chapter focuses on implementing data structures.

Key
Point

Lists, stacks, queues, and priority queues are classic data structures typically covered in a
data structures course. They are supported in the Java API, and their uses were presented in
Chapter 20, Lists, Stacks, Queues, and Priority Queues. This chapter will examine how these
data structures are implemented under the hood. Implementation of sets and maps is covered
in Chapter 27. Through these examples, you will learn how to design and implement custom
data structures.

24.2 Common Features for Lists
Common features of lists are defined in the List interface.

Key
Point

A list is a popular data structure for storing data in sequential order—for example, a list of
students, a list of available rooms, a list of cities, a list of topics. You can perform the follow-
ing operations on a list:

Retrieve an element from the list.

■

Insert a new element into the list.

■

Delete an element from the list.

■

Find out how many elements are in the list.

■

Determine whether an element is in the list.

■

Check whether the list is empty.

■

There are two ways to implement a list. One is to use an array to store the elements.
Array size is fixed. If the capacity of the array is exceeded, you need to create a new,
larger array and copy all the elements from the current array to the new array. The other
approach is to use a linked structure . A linked structure consists of nodes. Each node is
dynamically created to hold an element. All the nodes are linked together to form a list.
Thus you can define two classes for lists. For convenience, let's name these two classes
MyArrayList and MyLinkedList . These two classes have common operations but dif-
ferent implementations.

Design Guide
The common operations can be generalized in an interface or an abstract class. A good
strategy is to combine the virtues of interfaces and abstract classes by providing both an
interface and a convenience abstract class in the design so that the user can use either
of them, whichever is convenient. The abstract class provides a skeletal implementation
of the interface, which minimizes the effort required to implement the interface.

convenience abstract class for
interface

Pedagogical Note
For an interactive demo on how array lists and linked lists work, go to www.cs.armstrong
.edu/liang/animation/web/ArrayList.html and www.cs.armstrong.edu/liang/animation/web/Linked
List.html , as shown in Figure 24.1. list animation on Companion

Website

Let us name the interface MyList and the convenience abstract class MyAbstractList .
Figure 24.2 shows the relationship of MyList , MyAbstractList , MyArrayList , and
MyLinkedList . The methods in MyList and the methods implemented in MyAbstractList
are shown in Figure 24.3. Listing 24.1 gives the source code for MyList .