List (ADT)

A list, although not indexed, introduces the concept of abstract pointers called Positions. Lists are special in that they are not contiguous in memory, so fixed size limitations are not a problem.

Position

A position is an abstraction of a pointer in that it either contains an element or is "null". Think of it like a node with no access to the next or previous elements in the list.

These are the only public members of a Position:

• Position(Node n) — conversion from a node to a position
• Object& element() — access to the element stored at this position
• bool isNull() — whether this is a "null" position

Functions

• int size() — Returns how many items are in the list.
• bool isEmpty() — Returns whether the list is empty (i.e. size is 0).
• bool isFirst(Position p) — Returns whether the specified position $p$ is the first item in the list.
• bool isLast(Position p) — Returns whether the specified position $p$ is the last item in the list.
• Position first() — Returns the position of the first item in the list.
• Position last() — Returns the position of the last item in the list.
• Position before(Position p) — Returns the position of the element prior to Position $p$.
• Position after(Position p) — Returns the position of the element after Position $p$.
• void replaceElement(Position p, Object o) — Replaces the element at position $p$ with an object $o$.
• void swapElements(Position p, Position q) — Switches the element stored at position $p$ with the one from position $q$ and vice versa.
• Position insertBefore(Position p, Object o) — Inserts a new element $o$ before position $p$ and returns the position of the newly inserted element.
• Position insertAfter(Position p, Object o) — Inserts a new element $o$ after position $p$ and returns the position of the newly inserted element.
• Position insertFirst(Object o) — Inserts a new element $o$ at the beginning of the list and returns the position of the newly inserted element.
• Position insertLast(Object o) — Inserts a new element $o$ at the end of the list and returns the position of the newly inserted element.
• void remove(Position p) — Removes an object from Position $p$.

Implementations

Note: Positions can be converted to nodes and vice versa in their constructors.

Singly-Linked-List

This is a sample implementation: not all functions have been implemented.

class SingleList {
private:
  Node* first;
  Node* last;

public:
  Position first() { return Position(*first); }
  Position last() { return Position(*last); }

  Position before(Position p) {
    Node* n = first;
    while (n->next()) {
      if (n->next()->element() == p.element()) {
        return Position(n);
      }
    }
    return Position(NULL);
  }
  
  Position after(Position p) {
    Node pNode(p);
    return Position(pNode.next());
  }
};

Doubly-Linked-List

The before() method becomes much easier to implement if we have access to the previous element in the list.

class DoubleList {
  /* ... */

public:
  Position before(Position p) {
    Node pNode(p);
    return Position(pNode.previous());
  }

  /* ... */
};