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.

Let us name the interface MyList and the convenience abstract class MyAbstractList. Figure below shows the relationship of MyList, MyAbstractList, MyArrayList, and MyLinkedList.

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

package demo;

public interface MyList<E> extends java.lang.Iterable<E> {
    /** Add a new element at the end of this list */
    public void add(E e);

    /** Add a new element at the specified index in this list */
    public void add(int index, E e);

    /** Clear the list */
    public void clear();

    /**Return true if this list contains the element */
    public boolean contains(E e);

    /** Return the element from this list at the specified index */
    public E get(int index);

    /** Return the index of the first matching element in this list.
     * Return -1 if no match. */
    public int indexOf(E e);

    /** Return true if this list doesn't contain any elements */
    public boolean isEmpty();

    /** Return the index of the last matching element in this list
     * Return -1 if no match. */
    public int lastIndexOf(E e);

    /** Remove the first occurrence of the element e from this list.
     * Shift any subsequent elements to the left.
     * Return true if the element is removed. */
    public boolean remove(E e);

    /** Remove the element at the specified position in this list.
     * Shift any subsequent elements to the left.
     * Return the element that was removed from the list. */
    public E remove(int index);

    /** Replace the element at the specified position in this list
     * with the specified element and return the old element. */
    public Object set(int index, E e);

    /** Return the number of elements in this list */
    public int size();
}

MyAbstractList declares variable size to indicate the number of elements in the list. The methods isEmpty(), size(), add(E), and remove(E) can be implemented in the class, as shown in the code below.

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.