Linked Lists II

After reviewing the material below, play around with the singly-linked list and doubly-linked list visualizations at https://visualgo.net/en/list. (Stacks, Queues, and Deques coming next week!)

Here is a video lecture for the material outlined below. If you prefer (or want supplemental) textbook readings, this topic is based on sections 9.4–9.5 from Bailey.

The video contains sections on

1. List operations (0:37)
2. Operations at the head of the list (6:41)
3. Analyzing addFirst (9:05)
4. removeFirst (10:20)
5. Operations at the end of the list (15:12)
6. removeLast (19:15)
7. Analyzing addLast and removeLast (22:34)
8. Upgrade: tail reference (25:07)
9. Upgrade: doubly-linked list (28:21)
10. Time efficiency comparisons (33:19)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=17ddcd74-be81-4c89-b3d0-acac0161933a

We've done a lot of directly manipulating linked list nodes to get our heads around a structure consisting of a chain of references. But to be a useful general-purpose data structure, our linked list is going to better encapsulation—ideally a single object with a bunch of useful methods like ArrayList. Let's start out by looking at the method signatures for some of the operations we'll want our linked list to support.

// post: returns number of elements in list
public int size();

// post: returns true iff list has no elements
public boolean isEmpty();

// post: value is added to beginning of list
public void addFirst(E value);

// post: value is added to end of list
public void addLast(E value);

// pre: list is not empty
// post: returns first value in list
public E getFirst();

// pre: list is not empty
// post: returns last value in list
public E getLast();

// pre: list is not empty
// post: removes first value from list
public E removeFirst();

// pre: list is not empty
// post: removes last value from list
public E removeLast();

// pre: 0 <= i < size()
// post: returns object found at that location
public E get(int i);

// pre: 0 <= i <= size()
// post: adds ith entry of list to value o
public void add(int i, E o);

// pre: 0 <= i < size()
// post: removes and returns object found at that location
public E remove(int i);

You may notice many of these methods are similar (or identical) to ArrayList methods. This is no accident! Extensible arrays and linked lists are two approaches to providing a list-like data structure. They have different properties, and are thus appropriate for different situations.

One important difference in the methods is the presence of methods explicitly for accessing/modifying the beginning and end (head and tail) of the list (e.g., getFirst, removeFirst, addLast). Such operations are so commonly used on linked lists that it makes sense to provide these versions (as opposed to doing everything with plain add and remove).

We'll begin our LinkedList implementation by deciding what fields it should have. As we saw last time, with a reference to the first node in a chain, we can use the next fields to work our way to any subsequent node. So our data structure will keep track of the front (often call the head) of the list:

public class LinkedList<E> {
    private ListNode<E> head;
}

Note that I'm using Java generics to allow our linked list to be declared to store different types of data.

The ListNode class is familiar to us from the last video, but we need to define it somewhere our linked list can access it. Since a ListNode is an internal part of a LinkedList object, and not something intended to be used on its own, I'm going to make it an inner class. Java actually lets us define classes inside of other classes for exactly this purpose of defining object types we need for a particular implementation.

public class LinkedList<E> {
    private ListNode<E> head;

    private class ListNode<E> {
        private E data;
        private ListNode<E> next;

        ListNode(E data, ListNode<E> next) {
            this.data = data;
            this.next = next;
        }
    }
}

I declare the inner ListNode class to be private because I want it to only be available inside the definition of LinkedList.

Now on the constructor, which should initialize an empty list. An empty list is one with no nodes in it, and Java uses the special value null to indicate when an object variable doesn't refer to any actual object. Thus, our constructor would look like

public LinkedList() {
    head = null;
}

This naturally suggests an implementation for the isEmpty method:

public boolean isEmpty() {
    return head == null;
}

Before getting to methods that deal with adding and removing nodes, let's look at our size method. It's task is to count the number of nodes in the list and return that number. Last time we looked at how we could use a loop to traverse our chain of nodes, and we can use this same technique to count them.

public int size() {
    ListNode<E> current = head;
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

While this will work, from a performance perspective it's unsatifying. Every time our list is asked for its size, it will loop through all the nodes—an operation that is linear in the size of the list (if there are \(n\) nodes, our loop will take a number of operations proportional to \(n\)). A better design would be to keep track of the number of nodes as we add and remove them, so we don't have to re-count every time.

public class LinkedList<E> {
    private ListNode<E> head;
    private int count;

    private class ListNode<E> {
        private E data;
        private ListNode<E> next;

        ListNode(E data, ListNode<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public LinkedList() {
        head = null;
        count = 0;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return count;
    }
}

This is an example of trading off space for time. By adding a count field, our LinkedList object takes up slightly more memory. In return, our size method goes from linear time to constant time, which is a big improvement. These kind of tradeoffs are very common in data structure design (and software design in general).

The slow part of the addLast and removeLast implementations above is the loop to find the tail node. What if we could just always keep track of which node is the tail node like we do with the head node? Then we could do away with the loop and achieve a constant time addLast and removeLast.

First, let's augment out implementation with a field tail that keeps track of the tail node:

public class LinkedList<E> {
    private ListNode<E> head;
    private ListNode<E> tail;
    private int count;

    private class ListNode<E> {
        private E data;
        private ListNode<E> next;

        ListNode(E data, ListNode<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public LinkedList() {
        head = null;
        tail = null;
        count = 0;
    }

    // ...
}

Seems simple enough, but how do we use it? Here's our addLast now that we have a tail field:

public void addLast(E data) {
    ListNode<E> newTail = new ListNode(data, null);
    // update the list
    tail.next = newTail;
    tail = newTail;
    count++;
}

This is definitely an upgrade from the old addLast! It's much simpler and now a constant time operation.

What about removeLast? Here we run into a problem. Removing the tail node requires setting the next field of the previous node to null. But we have no way to get a reference to that previous node other than traversing the list from the head. That is, the tail node doesn't keep track of the previous node in the list. In order to remove from the end of the list efficiently, we will need to modify our list design.

Here we continue the tradeoff of space and time. To make removing from the tail efficient in term of time, we will have each node maintain a reference to the previous node in the list.

private class ListNode<E> {
    private ListNode<E> prev;
    private E data;
    private ListNode<E> next;

    ListNode(E data, ListNode<E> next, ListNode<E> prev) {
        this.prev = prev;
        this.data = data;
        this.next = next;
    }
}

This will make each node take up more space, but allows us to implement an efficient removeLast method:

public E removeLast() {
    if (size() <= 1) {
        return removeFirst();
    }
    tail = tail.previous;
    tail.next = null;
    count--;
}

We call this form of linked list a doubly-linked list due to the fact that each node has two links: one to the next node and one to the preivous node. When our nodes only have a link to the next node, we say we have a singly-linked list.

Now that we have these three different structures for representing a list, how would we go about choosing which one to use? It will depend on which list operations you need to be efficient—there's no one choice that's always best. Need to frequently remove from the front of the list? A either type of linked list can do this in constant time, so you would use one of those. Also removing from the end of the list? That narrows it down to a doubly-linked list. On the other hand, if you need to frequently access elements in the middle of the list, an ArrayList will do that far more efficiently (i.e., constant time).

Here's a chart comparing these three structures across a variety of operations:

1. Intuitively, we might think that addFirst and removeFirst only modify the head field of the list, while addLast and removeLast only modify the tail field. However, there are situations where each of these operations must modify both head and tail. (Such special cases are often called edge cases or boundary cases). When would each of these operations need to modify both?
2. The chart above shows that both the ArrayList and linked lists take linear time to remove an element from a specific position in the list (remove(index)). Why is this? Is it the same reason for both data structures or different reasons?
3. When you add or remove the element found at index i of a singly-linked list, you must create a temporary current node reference and advance it through the list. At which index's node should the loop stop, relative to i?
4. In an ArrayList, it is possible to overrun the capacity of the array, at which point the list must be resized to fit. Is resizing necessary on a linked list? What limits the number of elements that a linked list can have?
5. Write an implementation of the public E remove(int index) method for a doubly-linked list.
6. Write an implementation of the public boolean contains(E element) method for a doubly-linked list.

• Questions?
• Form questions
• checkstyle mistake
  • Need to install the Checkstyle for Java extension (I mistakenly thought it was part of the coding pack from lab 0)
  • Checkstyle will not be graded for lab 1, but will be part of future labs

• Demo CoinStripTest

  Testing if CoinStrip constructor creates games with random coin amounts and positions... Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
        at CoinStrip.getCoinPosition(CoinStrip.java:33)
        at CoinStripTest.randomCoins(CoinStripTest.java:83)
        at CoinStripTest.main(CoinStripTest.java:150)
  

  • You might see a message like this, what does it mean?
  • First is a message printed by CoinStripTest about the test it's performing
    • Testing if CoinStrip constructor creates games with random coin amounts and positions...
  • Then the the type of exception and any accompanying error message
    • Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
  • Then it displays the method calls that led to the exception, along with the line numbers
    • The function calls go from most recent to least recent, top to bottom
    • So line 150 of CoinStripTest.java (in the main method of CoinStripTest) called CoinStripTest.randomCoins
    • Then line 83 of CoinStripTest.java called CoinStrip.getCoinPosition
    • The exception occurred on line 33 of CoinStrip.java inside the getCoinPosition method
  • BEWARE: if you are using a Java library data structure like ArrayList, the list of method calls may include a whole bunch of method calls from inside the ArrayList class
    • To find where the problem occurred in your code (I promise you it's not a bug with ArrayList), look for the reference to a CoinStrip method with a line number in CoinStrip.java

• Demo converting Rock, Paper, Scissors main to CoinStrip's main

  public static void main(String[] args) {
      CoinStrip game = new CoinStrip();
      Scanner scan = new Scanner(System.in);
      int turn = 0;
  
      while (!game.isGameOver()) {
          System.out.println(game);
  
          System.out.print("Enter player " + turn + "'s move: ");
          int coin = scan.nextInt();
          int spaces = scan.nextInt();
  
          while (!game.isValidMove(coin, spaces)) {
              System.out.println("\nInvalid move! Try again");
              System.out.println(game);
  
              System.out.print("Enter player " + turn + "'s move: ");
              coin = scan.nextInt();
              spaces = scan.nextInt();
          }
  
          game.makeMove(coin, spaces);
          turn = (turn + 1) % 2;  // will flip turn between 0 and 1
      }
  
      // turn will be modified even when a player makes the winning move
      // so the winner is the opposite of the player indicated by turn as this point
      System.out.println("Player " + (turn + 1) % 2 + " wins!");
      scan.close();
  }