2.1. Lists¶

2.1.1. Lists¶

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)¶

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

2.1.1.4. List ADT (2)¶

  // 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();

2.1.1.5. List ADT (3)¶

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

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 L, Object 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 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

  // Constructors
  // Create a new list object with maximum size "size"
  AList(int size) {
    maxSize = size;
    listSize = curr = 0;
    listArray = new Object[size];         // Create listArray
  }
  // Create a list with the default capacity
  AList() { this(DEFAULT_SIZE); }          // Just call the other constructor

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.

130
121
202
83
34
5
6
7
// Insert "it" at current position
public boolean insert(Object 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
8
maxSize
5
listSize
0
curr

Saving...
Server Error
Resubmit

2.1.1.10. Link Class¶

Dynamic allocation of new list elements.

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
}

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)¶

null
null
head
curr
tail

null
20
23
10
12
15
null
head
curr
tail

2.1.1.14. Linked List Class (1)¶

1 / 7 Settings
<<<>>>

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

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

Saving...
Server Error
Resubmit

2.1.1.15. Linked List Class (2)¶

1 / 5 Settings
<<<>>>

Now we look at the constructors for class LList.

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

Saving...
Server Error
Resubmit

2.1.1.16. Insertion¶

1 / 9 Settings
<<<>>>

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

// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(new Link(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
15
0

Saving...
Server Error
Resubmit

2.1.1.17. Removal¶

1 / 7 Settings
<<<>>>

Now we look at the remove method.

// Remove and return current element
public Object 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");
Object 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
10
it

Saving...
Server Error
Resubmit

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

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

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

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

2.1.1.23. 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.24. Doubly Linked Lists¶

null
20
23
12
15
null
head
curr
tail

2.1.1.25. Doubly Linked Node (1)¶

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
}

2.1.1.26. Doubly Linked Insert¶

1 / 10 Settings
<<<>>>

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

public boolean insert(Object it) {
curr = new Link(it, curr.prev(), curr);
curr.prev().setNext(curr);
curr.next().setPrev(curr);
listSize++;
return true;
}
it
15
null
23
8
35
10
null
head
curr
tail

Saving...
Server Error
Resubmit

2.1.1.27. 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 Object remove() {
if (curr == tail) return null; // Nothing to remove
Object 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

CS3 Coursenotes

Chapter 2 Week 3

2.1. Lists¶

2.1.1. Lists¶

2.1.1.1. Lists¶

2.1.1.2. List Implementation Concepts¶

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¶

2.1.1.7. List Find Function¶

2.1.1.8. Array-Based List Class (1)¶

2.1.1.9. Array-Based List Insert¶

2.1.1.10. Link Class¶

2.1.1.11. Linked List Position (1)¶

2.1.1.12. Linked List Position (2)¶

2.1.1.13. Linked List Position (3)¶

2.1.1.14. Linked List Class (1)¶

2.1.1.15. Linked List Class (2)¶

2.1.1.16. Insertion¶

2.1.1.17. Removal¶

2.1.1.18. Prev¶

2.1.1.19. Overhead¶

2.1.1.20. Comparison of Implementations¶

2.1.1.21. Space Comparison¶

2.1.1.22. Space Example¶

2.1.1.23. Freelist¶

2.1.1.24. Doubly Linked Lists¶

2.1.1.25. Doubly Linked Node (1)¶

2.1.1.26. Doubly Linked Insert¶

2.1.1.27. Doubly Linked Remove¶