2.1.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?

2.1.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>$

2.1.1.3. List ADT (1)¶

2.1.1.4. List ADT (2)¶

2.1.1.5. List ADT (3)¶

2.1.1.6. List ADT Examples¶

List: $<12\ |\ 32, 15>$

L.insert(99);

Result: $<12\ |\ 99, 32, 15>$

Iterate through the whole list:

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

2.1.1.7. List Find Function¶

// 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
}

2.1.1.8. Array-Based List Class (1)¶

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

2.1.1.9. Array-Based List Insert¶

1 / 6 Settings

<<<>>>

Inserting an element at the head of an array-based list requires shifting all existing elements in the array by one position toward the tail.

1. 130
2. 121
3. 202
4. 83
5. 34
6. 5
7. 6
8. 7

• // Insert "it" at current position
• public boolean insert(E it) {
• if (listSize >= maxSize) {
• return false;
• }
• for (int i=listSize; i>curr; i--) { // Shift elements up
• listArray[i] = listArray[i-1]; // to make room
• }
• listArray[curr] = it;
• listSize++; // Increment list size
• return true;
• }

Insert 23

1. 8

maxSize

1. 5

listSize

1. 0

curr

Saving...
Server Error
Resubmit

2.1.1.10. Link Class¶

Dynamic allocation of new list elements.

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
}

2.1.1.11. Linked List Position (1)¶

1 / 3 Settings

<<<>>>

Here is a graphical depiction for a linked list storing five integers. The value stored in a pointer variable is indicated by an arrow "pointing" to something. A NULL pointer is indicated graphically by a diagonal slash through a pointer variable's box. The vertical line between the nodes labeled 23 and 10 indicates the current position (immediately to the right of this line).

20

23

10

12

15

head

curr

tail

Saving...
Server Error
Resubmit

2.1.1.12. Linked List Position (2)¶

1 / 7 Settings

<<<>>>

Another problem is that we have no link to get us to the preceding node (shown in yellow). So we have no easy way to update the yellow node's next pointer.

20

23

10

12

15

head

curr

tail

curr

tail

Saving...
Server Error
Resubmit

2.1.1.13. Linked List Position (3)¶

We will add list header and list trailer nodes. This eliminates all the special cases.

null

null

head

curr

tail

null

20

23

10

12

15

null

head

curr

tail

2.1.1.14. Design Principle: Design to Avoid Special Cases¶

Adding list header/trailer nodes add a little space and (simple) code to the list class constructor.

However, adding them avoids dealing with special cases that potentially involve bug-prone code

Avoids writing code for most special cases when inserting into empty list, at head of list, or at end of list.

Avoids writing code for most special cases when deleting first, last, or only element in list.

2.1.1.15. Linked List Class (1)¶

1 / 7 Settings

<<<>>>

Let's look at the data members for class LList.

• class LList<E> implements List<E> {
• private Link<E> head; // Pointer to list header
• private Link<E> tail; // Pointer to last element
• private Link<E> curr; // Access to current element
• private int listSize; // Size of list

Saving...
Server Error
Resubmit

2.1.1.16. Linked List Class (2)¶

1 / 5 Settings

<<<>>>

Now we look at the constructors for class LList.

• // Constructors
• LList(int size) { // Constructor -- Ignore size
• this();
• }
• LList() {
• clear();
• }
• // Remove all elements
• public void clear() {
• curr = tail = new Link<E>(null); // Create trailer
• head = new Link<E>(tail); // Create header
• listSize = 0;
• }

Saving...
Server Error
Resubmit

2.1.1.17. Insertion¶

1 / 9 Settings

<<<>>>

The linked list before insertion. 15 is the value to be inserted.

• // Insert "it" at current position
• public boolean insert(E it) {
• curr.setNext(new Link<E>(curr.element(), curr.next()));
• curr.setElement(it);
• if (tail == curr) {
• tail = curr.next(); // New tail
• }
• listSize++;
• return true;
• }

null

35

23

12

null

head

curr

tail

it

1. 15

1. 0

Saving...
Server Error
Resubmit

2.1.1.18. Removal¶

1 / 7 Settings

<<<>>>

Now we look at the remove method.

• // Remove and return current element
• public E remove () throws NoSuchElementException {
• if (curr == tail) {// Nothing to remove
• throw new NoSuchElementException("remove() in LList has current of " + curr + " and size of "
• + listSize + " that is not a a valid element");
• }
• E it = curr.element(); // Remember value
• curr.setElement(curr.next().element()); // Pull forward the next element
• if (curr.next() == tail) {
• tail = curr; // Removed last, move tail
• }
• curr.setNext(curr.next().next()); // Point around unneeded link
• listSize--; // Decrement element count
• return it; // Return value
• }

null

23

8

35

10

null

head

curr

tail

1. 10

it

Saving...
Server Error
Resubmit

2.1.1.19. Prev¶

1 / 10 Settings

<<<>>>

Finally, we will look at how a few other methods work.

null

23

8

35

10

null

head

curr

tail

temp

curr

• // Move curr one step right; no change if now at end
• public void next() { if (curr != tail) { curr = curr.next(); } }

• // Move curr one step left; no change if now at front
• public void prev() {
• if (head.next() == curr) {
• return; // No previous element
• }
• Link<E> temp = head;
• // March down list until we find the previous element
• while (temp.next() != curr) {
• temp = temp.next();
• }
• curr = temp;
• }

• // Move down list to "pos" position
• public boolean moveToPos(int pos) {
• if ((pos < 0) || (pos > listSize)) {
• return false;
• }
• curr = head.next();
• for(int i=0; i<pos; i++) { curr = curr.next(); }
• return true;
• }

Saving...
Server Error
Resubmit

2.1.1.20. 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

2.1.1.21. 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.

2.1.1.22. 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.

2.1.1.23. 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

2.1.1.24. Freelist¶

System new and garbage collection are slow.

• Add freelist support to the Link class.

1 / 7 Settings

<<<>>>

We will illustrate using a freelist by performing a series of list operations. Let's start from an empty singly linked list and a freelist variable pointing to null.

null

null

8

12

6

20

6

null

null

null

head

curr

tail

freelist

Saving...
Server Error
Resubmit

2.1.1.25. Doubly Linked Lists¶

null

20

23

12

15

null

head

curr

tail

2.1.1.26. Doubly Linked Node (1)¶

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
}

2.1.1.27. Doubly Linked Insert¶

1 / 10 Settings

<<<>>>

The linked list before insertion. 15 is the value to be inserted.

• public boolean insert(E it) {
• curr = new Link<E>(it, curr.prev(), curr);
• curr.prev().setNext(curr);
• curr.next().setPrev(curr);
• listSize++;
• return true;
• }

it

1. 15

null

23

8

35

10

null

head

curr

tail

Saving...
Server Error
Resubmit

2.1.1.28. Doubly Linked Remove¶

1 / 9 Settings

<<<>>>

Now we will look at the remove method. Here is the linked list before we remove the node with value 8.

• public E remove() {
• if (curr == tail) { return null; } // Nothing to remove
• E it = curr.element(); // Remember value
• curr.prev().setNext(curr.next()); // Remove from list
• curr.next().setPrev(curr.prev());
• curr = curr.next();
• listSize--; // Decrement node count
• return it; // Return value removed
• }

it

null

23

8

35

null

head

curr

tail

Saving...
Server Error
Resubmit