Implementing Lists, Stacks, Queues, and Priority Queues - Common Features for Lists

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 books. You can perform the following 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 different implementations.

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.

The methods in MyList and the methods implemented in MyAbstractList are shown in Figure below. The code below gives the source code for MyList.

The following sections give the implementation for MyArrayList and MyLinkedList, respectively.

Protected data fields are rarely used. However, making size a protected data field in the MyAbstractList class is a good choice. The subclass of MyAbstractList can access size, but nonsubclasses of MyAbstractList in different packages cannot access it. As a general rule, you can declare protected data fields in abstract classes.