30.10.1.1. Lists¶

A list is a finite, ordered sequence of data items.

Important concept: List elements have a position.

Notation: \(<a_0, a_1, …, a_{n-1}>\)

What operations should we implement?

30.10.1.2. List Implementation Concepts¶

Our list implementation will support the concept of a current position.

Operations will act relative to the current position.

\(<20, 23\ |\ 12, 15>\)

30.10.1.3. List ADT (1)¶

30.10.1.4. List ADT (2)¶

30.10.1.5. List ADT (3)¶

30.10.1.6. List ADT Examples¶

List: \(<12\ |\ 32, 15>\)

L.insert(99);

Result: \(<12\ |\ 99, 32, 15>\)

Iterate through the whole list:

• Java
• Processing
• Java (Generic)
• C++

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);
}

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

30.10.1.7. List Find Function¶

• Java
• Processing
• Java (Generic)
• C++

// 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
boolean find(List L, int k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == (Integer)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<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
bool find(List& L, int k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                         // k not found
}

30.10.1.8. Array-Based List Class (1)¶

• Java
• Processing
• Java (Generic)
• C++

class AList implements List {
  private Object listArray[];             // Array holding list elements
  private static final int DEFAULT_SIZE = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private int curr;                       // Position of current element

class AList implements List {
  private Object listArray[];             // Array holding list elements
  private static final int DEFAULT_SIZE = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private int curr;                       // Position of current element

class AList<E> implements List<E> {
  private E listArray[];                  // Array holding list elements
  private static final int DEFAULT_SIZE = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private int curr;                       // Position of current element

class AList : public List {
  ListItemType listArray[MAX_SIZE];  //Array holding list elements
  int listSize;   //Current number of list items
  int curr;   //Position of current element

30.10.1.9. Array-Based List Insert¶

Settings

Saving...
Server Error
Resubmit

30.10.1.10. Link Class¶

Dynamic allocation of new list elements.

• Java
• Processing
• Java (Generic)

class Link {         // Singly linked list node class
  private Object e;  // Value for this node
  private Link n;    // Point to next node in list

  // Constructors
  Link(Object it, Link inn) { e = it; n = inn; }
  Link(Link inn) { e = null; n = inn; }

  Object element() { return e; }                  // Return the value
  Object setElement(Object it) { return e = it; } // Set element value
  Link next() { return n; }                       // Return next link
  Link setNext(Link inn) { return n = inn; }      // Set next link
}

class Link {         // Singly linked list node class
  private Object e;  // Value for this node
  private Link n;    // Point to next node in list

  // Constructors
  Link(Object it, Link inn) { e = it; n = inn; }
  Link(Link inn) { e = null; n = inn; }

  Object element() { return e; }                  // Return the value
  Object setElement(Object it) { return e = it; } // Set element value
  Link next() { return n; }                       // Return next link
  Link setNext(Link inn) { return n = inn; }      // Set next link
}

class Link<E> {         // Singly linked list node class
  private E e;          // Value for this node
  private Link<E> n;    // Point to next node in list

  // Constructors
  Link(E it, Link<E> inn) { e = it; n = inn; }
  Link(Link<E> inn) { e = null; n = inn; }

  E element() { return e; }                        // Return the value
  E setElement(E it) { return e = it; }            // Set element value
  Link<E> next() { return n; }                     // Return next link
  Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
}

30.10.1.11. Linked List Position (1)¶

Settings

Saving...
Server Error
Resubmit

30.10.1.12. Linked List Position (2)¶

Settings

Saving...
Server Error
Resubmit

30.10.1.13. Linked List Position (3)¶

30.10.1.14. Linked List Class (1)¶

Settings

Saving...
Server Error
Resubmit

30.10.1.15. Linked List Class (2)¶

Settings

Saving...
Server Error
Resubmit

30.10.1.16. Insertion¶

Settings

Saving...
Server Error
Resubmit

30.10.1.17. Removal¶

Settings

Saving...
Server Error
Resubmit

30.10.1.18. Prev¶

Settings

Saving...
Server Error
Resubmit

30.10.1.19. Overhead¶

• Container classes store elements. Those take space.

• Container classes also store additional space to organize the elements.

  • This is called overhead

• The overhead fraction is: overhead/total space

30.10.1.20. Comparison of Implementations¶

• Array-Based Lists:

  • Insertion and deletion are \(\Theta(n)\).
  • Prev and direct access are \(\Theta(1)\).
  • Array must be allocated in advance.
  • No overhead if all array positions are full.

• Linked Lists:

  • Insertion and deletion are \(\Theta(1)\).
  • Prev and direct access are \(\Theta(n)\).
  • Space grows with number of elements.
  • Every element requires overhead.

30.10.1.21. Space Comparison¶

"Break-even" point:

\(DE = n(P + E)\)

\(n = \frac{DE}{P + E}\)

E: Space for data value.

P: Space for pointer.

D: Number of elements in array.

30.10.1.22. Space Example¶

• Array-based list: Overhead is one pointer (8 bytes) per position in array – whether used or not.
• Linked list: Overhead is two pointers per link node one to the element, one to the next link
• Data is the same for both.
• When is the space the same?
  • When the array is half full

30.10.1.23. Freelist¶

System new and garbage collection are slow.

• Add freelist support to the Link class.

Settings

Saving...
Server Error
Resubmit

30.10.1.24. Doubly Linked Lists¶

30.10.1.25. Doubly Linked Node (1)¶

• Java
• Processing
• Java (Generic)

class Link {            // Doubly linked list node
  private Object e;     // Value for this node
  private Link n;       // Pointer to next node in list
  private Link p;       // Pointer to previous node

  // Constructors
  Link(Object it, Link inp, Link inn) { e = it;  p = inp; n = inn; }
  Link(Link inp, Link inn) { p = inp; n = inn; }

  // Get and set methods for the data members
  public Object element() { return e; }                     // Return the value
  public Object setElement(Object it) { return e = it; }    // Set element value
  public Link next() { return n; }                          // Return next link
  public Link setNext(Link nextval) { return n = nextval; } // Set next link
  public Link prev() { return p; }                          // Return prev link
  public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}

class Link {            // Doubly linked list node
  private Object e;     // Value for this node
  private Link n;       // Pointer to next node in list
  private Link p;       // Pointer to previous node

  // Constructors
  Link(Object it, Link inp, Link inn) { e = it;  p = inp; n = inn; }
  Link(Link inp, Link inn) { p = inp; n = inn; }

  // Get and set methods for the data members
  Object element() { return e; }                     // Return the value
  Object setElement(Object it) { return e = it; }    // Set element value
  Link next() { return n; }                          // Return next link
  Link setNext(Link nextval) { return n = nextval; } // Set next link
  Link prev() { return p; }                          // Return prev link
  Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}

class Link<E> {         // Doubly linked list node
  private E e;          // Value for this node
  private Link<E> n;    // Pointer to next node in list
  private Link<E> p;    // Pointer to previous node

  // Constructors
  Link(E it, Link<E> inp, Link<E> inn) { e = it;  p = inp; n = inn; }
  Link(Link<E> inp, Link<E> inn) { p = inp; n = inn; }

  // Get and set methods for the data members
  public E element() { return e; }                                // Return the value
  public E setElement(E it) { return e = it; }                    // Set element value
  public Link<E> next() { return n; }                             // Return next link
  public Link<E> setNext(Link<E> nextval) { return n = nextval; } // Set next link
  public Link<E> prev() { return p; }                             // Return prev link
  public Link<E> setPrev(Link<E> prevval) { return p = prevval; } // Set prev link
}

30.10.1.26. Doubly Linked Insert¶

Settings

Saving...
Server Error
Resubmit

30.10.1.27. Doubly Linked Remove¶

Settings

Saving...
Server Error
Resubmit