Close
Register
Close Window

Basic Data Structures

Chapter 4 Linear Structures

Show Source |    | About   «  4.1. Chapter Introduction: Lists   ::   Contents   ::   5.1. Stacks  »

4.2. The List ADT

4.2.1. The List ADT

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. In the simple list implementations discussed in this chapter, all elements of the list are usually assumed to have the same data type, although there is no conceptual objection to lists whose elements have differing data types if the application requires it. The operations defined as part of the list ADT do not depend on the elemental data type. For example, the list ADT 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 length of the list. The beginning of the list is called the head, the end of the list is called the tail.

We need some notation to show the contents of a list, so we will use the same angle bracket notation that is normally used to represent sequences. To be consistent with standard array indexing, the first position on the list is denoted as 0. Thus, if there are \(n\) elements in the list, they are given positions 0 through \(n-1\) as \(\langle\ a_0,\ a_1,\ ...,\ a_{n-1}\ \rangle\). The subscript indicates an element’s position within the list. Using this notation, the empty list would appear as \(\langle\ \rangle\).

4.2.1.1. Defining the ADT

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. We must be able to create and clear (or reinitialize) lists. It is also convenient to access the next or previous element from the “current” one.

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

True to the notion of an ADT, an interface does not specify how operations are implemented. Two complete implementations are presented later in later modules, both of which use the same list ADT to define their operations. But they are considerably different in approaches and in their space/time tradeoffs.

The code below presents our list ADT. Any implementation for a container class such as a list should be able to support different data types for the elements. One way to do this in Java is to store data values of type Object. Languages that support generics (Java) or templates (C++) give more control over the element types.

The comments given with each member function describe what it is intended to do. However, an explanation of the basic design should help make this clearer. Given that we wish to support the concept of a sequence, with access to any position in the list, the need for many of the member functions such as insert and moveToPos is clear. The key design decision embodied in this ADT is support for the concept of a current position. For example, member moveToStart sets the current position to be the first element on the list, while methods next and prev move the current position to the next and previous elements, respectively. The intention is that any implementation for this ADT support the concept of a current position. The current position is where any action such as insertion or deletion will take place. An alternative design is to factor out position as a separate position object, sometimes referred to as an iterator.

// List class ADT. Generalize the element type using Java Generics.
public interface List<E> { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(E it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(E it);

  // Remove and return the current element
  public E remove() throws NoSuchElementException;

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at beginning
  public void prev();

  // Move the current position one step right, no change if already at end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if current position is at end of the list
  public boolean isAtEnd();

  // Return the current element
  public E getValue() throws NoSuchElementException;
  
  // Tell if the list is empty or not
  public boolean isEmpty();
}

// List class ADT. Generalize by using "Object" for the element type.
public interface List { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(Object it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(Object it);

  // Remove and return the current element
  public Object remove() throws NoSuchElementException;

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at beginning
  public void prev();

  // Move the current position one step right, no change if already at end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if current position is at end of the list
  public boolean isAtEnd();

  // Return the current element
  public Object getValue() throws NoSuchElementException;
  
  public boolean isEmpty();
}

// List class ADT.
class List { // List class ADT
public:
  // Destructor
  virtual ~ List () =default;

  // Remove all contents from the list, so it is once again empty
  virtual void clear() =0;

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  virtual bool insert(const ListItemType& it) =0;

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  virtual bool append(const ListItemType& it) =0;

  // Remove and return the current element
  virtual ListItemType remove() =0;

  // Set the current position to the start of the list
  virtual void moveToStart() =0;

  // Set the current position to the end of the list
  virtual void moveToEnd() =0;

  // Move the current position one step left, no change if already at beginning
  virtual void prev() =0;

  // Move the current position one step right, no change if already at end
  virtual void next() =0;

  // Return the number of elements in the list
  virtual int length() =0;

  // Return the position of the current element
  virtual int currPos() =0;

  // Set the current position to "pos"
  virtual bool moveToPos(int pos) =0;

  // Return true if current position is at end of the list
  virtual bool isAtEnd() =0;

  // Return the current element
  virtual ListItemType getValue() =0;
  
  virtual bool isEmpty() =0;
};

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

The List member functions allow you to build a list with elements in any desired order, and to access any desired position in the list. You might notice that the clear method is a “convenience” method, since it could be implemented by means of the other member functions in the same asymptotic time.

A list can be iterated through as follows:

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

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

The list class declaration presented here is just one of many possible interpretations for lists. Our list interface provides most of the operations that one naturally expects to perform on lists and serves to illustrate the issues relevant to implementing the list data structure. As an example of using the list ADT, here is a function to return true if there is an occurrence of a given integer in the list, and false otherwise. The find method needs no knowledge about the specific list implementation, just the list ADT.

// Return true if k is in list L, false otherwise
static boolean find(List<Integer> L, int k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                         // k not found
}

// Return true if k is in list L, false otherwise
static boolean find(List L, Object k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                         // k not found
}

// Return true if k is in list L, false otherwise
static bool find(List &L, ListItemType k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                       // k not found
}

In languages that support it, this implementation for find could be rewritten as a generic or template with respect to the element type. While making it more flexible, even generic types still are limited in their ability to handle different data types stored on the list. In particular, for the find function generic types would only work when the description for the object being searched for (k in the function) is of the same type as the objects themselves. They also have to be comparable when using the == operator. A more realistic situation is that we are searching for a record that contains a key field whose value matches k. Similar functions to find and return a composite type based on a key value can be created using the list implementation, but to do so requires some agreement between the list ADT and the find function on the concept of a key, and on how keys may be compared.

There are two standard approaches to implementing lists, the array-based list, and the linked list.

4.2.2. List ADT Programming Exercise

   «  4.1. Chapter Introduction: Lists   ::   Contents   ::   5.1. Stacks  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Jan 23, 2021. Created using Sphinx 2.4.4.
Close Window