Abstract List / List ADT

Relation: explicitly defined linear ordering

The Abstract List

The Abstract List is defined for objects which are explicitly ordered by the programmer. The first object in the list is defined to be at the front of the list and the last is at the back of the list.

Critical Operations for Abstract Lists

  • Access the kth object in the list, and
  • Given a reference to a specific object in the list:
    • Access the previous or the next object in the list,
    • Modify the current object,
    • Remove the current object from the list,
    • Insert a new object either immediately before or immediately after the currently reference object.

Example Data Structures

Both a linked list and an array may be used to implement the Abstract List and each of these has positive and negative features with respect to the run time of various operations. An alternate possibility may be to use a linked list of fixed-size arrays. This hybrid approach is used in the STL for the deque data structure.

Abstract Lists and the Abstract Sorted Lists

The next abstract data structure discussed is the Abstract Sorted List where objects are stored in such a way that it is possible to step through the entries in order. One may claim that the Abstract Sorted List is simply a specialization of the Abstract List; however, this is not entirely true: it makes no sense to replace one object in a sorted list unless there is some guarantee that it correctly fits into that position. Defining a Abstract List which then has two specializations of Abstract Unsorted List and Abstract Sorted List may be elegant; however, such a generalization would be essentially worthless: the number of operations relevant to each is very restricted.

Knuth and Lists

In The Art of Computer Programming, Volume 1: Fundamental Algorithms, Donald Knuth begins Section 2.2 with a list of nine operations which "we might want to perform on linear lists":

  1. Gain access to the kth node of the list to examine and/or to change the contents of its fields.
  2. Insert a new node just before or after the kth node.
  3. Delete the kth node.
  4. Combine two or more linear lists into a single list.
  5. Split a linear list into two or more lists.
  6. Make a copy of a linear list.
  7. Determine the number of nodes in a list.
  8. Sort the nodes of the list into ascending order based on certain fields of the nodes.
  9. Search the list for the occurrence of a node with a particular value in some field.

In this discussion, note that operations 4, 5, 6, 7, and 9 are classified as operations which may be performed on general containers. The last operation, searching a list, can be optimized to O(1) if a hash table is used (with no relation) or O(ln(n)) if a balanced binary search tree is used (with a linear ordering).