10.2. Linked Lists

Linked lists

---

We have seen the idea of top-down design. If you need a method, but it is not already available, then create it. The same idea works with types. If you need a particular type of data, but it is not already available, then you create it yourself, along with the methods that you need on it.

Our goal here is implement conceptual lists in Java. It is not possible to add notation [2,4,6], since we cannot add new notation to Java. But we can add methods and a class.

The first issue is how to represent the information in a list. One way to do that is to use a linked list, which consists of zero or more list cells. Each contains a reference to the next cell in the list. The last cell contains a null reference, indicating that the list is empty. Here is a picture of a linked list that represents [2,4,6].

     ____       ____       ____
    |    |     |    |     |    |
    | -------->|  ------->|  -----\
    |----|     |----|     |----|
    | 2  |     | 4  |     | 6  |
    |____|     |____|     |____|

  class ListCell
  {
    public ListCell next;
    public int      item;

    public ListCell(int it, ListCell nxt)
    {
      item = it;
      next = nxt;
    }
  }

But a list cell is not a list; a list has class List, defined as follows. This class supports two approaches in its use. To get the head of L, you can write either L.head() or List.head(L). If you do a static import of the list class, you can just write head(L).

  class List
  {
    private ListCell front;

    private List(ListCell f)
    {
      front = f;
    }

    
    //=============================================
    //                Empty list
    //=============================================

    //---------------------------------------------
    /** new List() yields an empty list		 */
    //---------------------------------------------

    public List()
    {
      front = null;
    }

    //---------------------------------------------
    /** emptyList yields an empty list.		 */
    //---------------------------------------------

    public static List emptyList = new List();
    

    //=============================================
    //               isEmpty
    //=============================================

    //---------------------------------------------
    /** L.isEmpty() is true if list L is empty.  */
    //---------------------------------------------

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

    //---------------------------------------------
    /** isEmpty(L) is true if list L is empty.   */
    //---------------------------------------------

    public static boolean isEmpty(List L)
    {
      return L.front == null;
    }


    //=============================================
    //               head
    //=============================================

    //---------------------------------------------
    /** L.head() is the head of list L (the first
    /   memeber of the list.)  It throws
    /   EmptyListException if L is empty.	 */
    //---------------------------------------------

    public int head()
    {
      if(front == null)
      {
          throw new EmptyListException();
      }
      else
      {
        return front.item;
      }
    }
   
    //---------------------------------------------
    /** head(L) is also the head of list L.      */
    //---------------------------------------------

    public static int head(List L)
    {
      return L.head();
    }
   
    //=============================================
    //               tail
    //=============================================

    //---------------------------------------------
    /** L.tail() is the tail of list L (the list
    /   that you get from L by removing its head.)
    /   It throws EmptyListException if L is empty.*/
    //---------------------------------------------
    
    public List tail()
    {
      if(front == null)
      {
        throw new EmptyListException();
      }
      else
      {
        return new List(front.next);
      }

    }
    
    //---------------------------------------------
    /** tail(L) is also the tail of list L.      */
    //---------------------------------------------

    public static List tail(List L)
    {
      return L.tail();
    }
   

    //=============================================
    //               h:t
    //=============================================

    //---------------------------------------------
    /** L.cons(n) is the list that you get by
    /   adding n to the beginning of list L.     */
    //---------------------------------------------

    public List cons(int n)
    {
      return new List(new ListCell(n, front));
    }

    //---------------------------------------------
    /** cons(n,L) is also the list that you get by
    /   adding n to the beginning of list L.     */
    //---------------------------------------------

    public static List cons(int n, List L)
    {
      return L.cons(n);
    }
  }

Finally, we need to define class EmptyListException.

  class EmptyListException extends RuntimeException
  {
    public EmptyListException()
    {
    }

    public String toString()
    {
       return "EmptyListException";
    }
  }

Building a linked list

---

To build up a list such as [2,4,6], just notice that [2,4,6] = 2:4:6:[ ]. Replacing : by method cons yields

  List twoFourSix = cons(2, cons(4, cons(6, emptyList)));

Exercises

---

1. Write a statement that creates variable W and makes it hold list [5, 3]. Answer

2. What are the values of variables X, Y and k after performing the following sequence of statements? Express your answers in conceptual notation.

     List X = cons(2, cons(4, cons(6, emptyList)));
     List Y = tail(X);
     int  k = head(Y);
     tail(X);
   

   Answer

3. What happens if you do the following statements?

     List X = emptyList;
     List Y = tail(X);
   

   Answer