Linked Lists

Linked Lists
> Click or hit Control-Enter to run Example.main above

What you have been building on the last few homework problems is a more general data structure called a list.

Lists are an ordered 1 data structure that allow us to:

Get and set values at any index (like an array)
Add or remove values at any index (this is new)
Lists are one of the two data structures you meet in heaven—maps are the other and we’ll get to them in a few weeks

Depending on how we structure data different implementations of the same interface can have different performance characteristics.

We’ll start by looking at this with lists
Lists that store items using arrays have fast (O(1)) lookups but slow (O(n)) modifications
Lists that store items using linked lists have slow lookups (O(n)) but some insertions are fast (O(1))
Both also present different memory usage tradeoffs

interface SimpleList {
  /** Get the object at this index. */
  public Object get(int index);
  /** Set the object at this index to the passed element. */
  public void set(int index, Object element);
  /** Add the object at the specified location in the list. */
  public void add(int index, Object element);
  /** Remove and return the object at the specified location in the list. */
  public Object remove(int index);
  /** Return the number of elements in the list. */
  public int size();
}

(The official Java one contains a bunch of convenience methods that we don’t want.)

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);
items = new Item((Integer) 5, items);

interface SimpleList {
  public Object get(int index);
  public void set(int index, Object element);
  public void add(int index, Object element);
  public Object remove(int index);
  public int size();
}
public class SimpleLinkedList implements SimpleList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
}

public class SimpleLinkedList {
  private Item start;
  public void addToFront(Object value) {
    start = new Item(value, start);
  }
}

What is n—or what feature drives performance? The length of the list.
What is the performance of addToFront? O(1): constant time!

(There’s always a catch.)

public class SimpleLinkedList {
  private Item start;
  public void addToFront(Object value) {
    start = new Item(value, start);
  }
  public Object get(int index) {
    // This should be easy...
  }
}

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);

public class SimpleLinkedList {
  public Object get(int index) {
    // until I get to the index
    // follow each Item to the next
  }
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);

public class SimpleLinkedList {
  private Item start;
}
public class Item {
  public int value;
  public Item next;
}

We can iterate through our LinkedList using a for loop.

> Click or hit Control-Enter to run Example.main above

Find the right spot.
Set the reference on the preceding item to point to the new item.
Set the reference on the new item to point to the former next item.

Let’s insert value 7 at index 1.

But wait, now we can’t change the preceding reference.

Let’s insert value 7 at index 1.

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
}

What we’ve been discussing is known as a singly linked list.

public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private Item end;
}

You can also have both forward and backward links. This is known an a doubly linked list.

public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private Item end;
}

public class SimpleArrayList {
  private Object[] array;
}
public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
  }
  private Item start;
  private Item end;
}

ArrayList v. LinkedList also represents a time v. space tradeoff.

LinkedList is faster for certain operations…
but consumes more space to store the same amount of information.

public class SimpleArrayList {
  private Object[] array;
}
public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
  }
  private Item start;
  private Item end;
}

To store n ints:

ArrayList: n values
LinkedList: 3n (1 value, 1 next, 1 previous)

Both provide the same functionality, but with different performance characteristics.

Operation ArrayList LinkedList

Operation	`ArrayList`	`LinkedList`
`add` (at front)	O(n)	O(1)
`get` and `set`	O(1)	O(n)
`insert` (anywhere)	O(n)	O(n)

add (at front)

O(n)

O(1)

get and set

O(1)

O(n)

insert (anywhere)

O(n)

public interface SimpleList {
  public Object get(int index);
  public void set(int index, Object element);
  public void add(int index, Object element);
  public Object remove(int index);
  public int size();
}
public class SimpleLinkedList implements SimpleList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;

public SimpleLinkedList(Object[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }

public void add(int index, Object toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
    }
  }

public int size() {
    int currentSize = 0;
    for (Item current = start; current != null; current = current.next) {
      currentSize++;
    }
    return currentSize;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleList simpleList = new SimpleLinkedList(new Integer[] { 1, 2, 5 });
    System.out.println(simpleList.size());
  }
}

> Click or hit Control-Enter to run Example.main above

Midterm format:

40 points: 10 4-point multiple-choice questions drawn from previous quizzes
60 points: 3 20-point programming questions, all including partial credit

Everything up through the quiz before spring break.

Lectures starting 2/11/2019 through 3/8/2019.
No coverage of algorithms, algorithm runtime, or lists.

You’re all doing great!
The point of the exams (and quizzes) is to get you to do the homework problems.

Midterm 1 starts tomorrow in the CBTF. It’s worth the same amount as a quiz but cannot be dropped.
No labs this week. Instead we’ll have drop-in midterm review office hours Tuesday and Wednesday. Residential office hours are also canceled.
I’m canceling my Monday office hours for the remainder of the semester. I’m still available Wednesday and Friday from 1–3PM in Siebel 2227.
MP4 will be released later this week. It’s incredibly fun… but also a big challenge.

Review: Lists

Review: Data Structure Tradeoffs

Our List Interface

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Review: `LinkedList` `addToFront`

Wow! What’s the catch?

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

Linked Lists: Iteration

But How Do We Insert?

`LinkedList` Insertion Algorithm

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Singly Linked Lists

Doubly Linked Lists

Doubly Linked Lists

Time v. Space

Time v. Space

`ArrayList` v. `LinkedList`

Questions About Lists?

Midterm Overview and Review

Midterm Topic Coverage

Midterm Questions?

Reminders

Announcements

Review: Lists

Review: Data Structure Tradeoffs

Our List Interface

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Review: LinkedList addToFront

Wow! What’s the catch?

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

LinkedList: get

Linked Lists: Iteration

But How Do We Insert?

LinkedList Insertion Algorithm

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Singly Linked Lists

Doubly Linked Lists

Doubly Linked Lists

Time v. Space

Time v. Space

ArrayList v. LinkedList

Questions About Lists?

Midterm Overview and Review

Midterm Topic Coverage

Midterm Questions?

Reminders

Announcements

Review: `LinkedList` `addToFront`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList`: `get`

`LinkedList` Insertion Algorithm

`ArrayList` v. `LinkedList`