7.2.1. Introduction¶

If your program needs to store a few things—numbers, payroll records, or job descriptions for example—the simplest and most effective approach might be to put them in a list. Only when you have to organize and search through a large number of things do more sophisticated data structures like search trees become necessary. Many applications don’t require any form of search, and they do not require that an ordering be placed on the objects being stored. Some applications require that actions be performed in a strict chronological order, processing objects in the order that they arrived, or perhaps processing objects in the reverse of the order that they arrived. For all these situations, a simple list structure is appropriate.

Along with presenting the list as a fundamental data structure, the other goals of this section are to:

1. Give examples that show the separation of a logical representation in the form of an interface from a realized implementation as a data structure.

2. Illustrate the use of asymptotic analysis in the context of simple operations that you might already be familiar with. In this way you can begin to see how asymptotic analysis works, without the complications that arise when analyzing more sophisticated algorithms and data structures.

We begin by defining an interface for lists, and then discuss an array-based implementation of the list.

We all have an intuitive understanding of what we mean by a “list”. We want to turn this intuitive understanding into a concrete data structure with implementations for its operations. The most important concept related to lists is that of position. In other words, we perceive that there is a first element in the list, a second element, and so on. So, define a list to be a finite, ordered sequence of data items known as elements. This is close to the mathematical concept of a sequence.

“Ordered” in this definition means that each element has a position in the list. So the term “ordered” in this context does not mean that the list elements are sorted by value. (Of course, we can always choose to sort the elements on the list if we want; it’s just that keeping the elements sorted is not an inherent property of being a list.)

Each list element must have some data type.

The operations defined as part of the list interface do not depend on the elemental data type. For example, the list interface can be used for lists of integers, lists of characters, lists of payroll records, even lists of lists.

A list is said to be empty when it contains no elements. The number of elements currently stored is called the size of the list.

7.2.2. Defining the Interface¶

What basic operations do we want our lists to support? Our common intuition about lists tells us that a list should be able to grow and shrink in size as we insert and remove elements. We should be able to insert and remove elements from anywhere in the list. We should be able to gain access to any element’s value, either to read it or to change it.

Now we can define the interface for a list object in terms of a set of operations on that object. MHCList defines the member functions that any list implementation inheriting from it must support, along with their parameters and return types.

As we have previously discussed, an interface does not specify how operations are implemented. We will discuss two complete implementations, the array list and the linked list, both of which use the same list interface to define their operations. However they are considerably different in approaches and in their space/time tradeoffs.

The code below presents our list interface, which should be able to support different data types for the elements. Languages that support generics, like Java, give us more control over the element types:

public interface MHCList<E> {

    // Replaces the element at the specified position in this list with the specified element.
    public void set (int index, E o);
    
    // Returns the element at the specified position in this list.
    public E get (int index);
    
    // Returns the number of elements in this list.
    public int size();
    
    // Appends the specified element to the end of this list.
    public boolean add (E o);
    
    // Inserts the specified element at the specified position in this list.
    public void add (int index, E o);
    
    // Removes the element at the specified position in this list, and returns it.
    public E remove (int index);

    // Returns true if this list contains no elements.
    public boolean isEmpty();

    // Returns a string representation of the list elements.
    public String toString();

}

The MHCList member methods allow you to build a list with elements in any desired order, and to access any desired position in the list.

7.2.3. Using a List¶

We can modify a List using the methods defined in the MHCList interface:

MHCList<String> theList = new MHCArrayList<>(); // Create a new empty ArrayList
System.out.println(theList.size()); // Output: 0
System.out.println(theList.isEmpty()); // Output: true

theList.add("Hello"); // add "Hello" to the beginning of the list
theList.add("World"); // add "World" to the end of the list
theList.add(1, "There"); // add "There" to the second position in the list, which shifts "World" to the third position
System.out.println(theList); // Output: [Hello, There, World]

String removedElement = theList.remove(theList.size() - 1); // remove the last element from the list, and return it
System.out.println(removedElement); // Output: World
System.out.println(theList); // Output: [Hello, There]

theList.set(0, "Hi"); // replace the first element with "Hi"
System.out.println(theList); // Output: [Hi, There]

A List can be iterated through as follows:

MHCList<String> theList; // assume theList is initialized previously
String curElement;

// size() returns the number of elements in the list
for (int i = 0; i < theList.size(); i++) {

    // get() returns the element at the specified position in the list
    curElement = theList.get(i);

    // take some action with the current element
    doSomething(curElement);
}

In this example, each element of the list in turn is stored in curElement, and passed to the doSomething function. The loop terminates when the index i reaches the end of the list.

Next class, we will look at a standard approach of implementing lists, the array-based list or ArrayList.