Linked Lists

Objective #1: Understand the java.util.List interface and some of its methods.

• The java.util.List<E> library interface includes the following AP subset methods:
  
  
  • int size();
  • boolean add(E x);
  • void add(int index, E x);
  • E get(int index);
  • E set(int index, E x);
  • E remove(int index);
  • Iterator<E> iterator();
  • ListIterator<E> listIterator();
    
    
• A list holds references to objects, not actual objects.
• The same object can be inserted into a list several times. The same object can also belong to several lists.
• Usually, an object (except immutable String's, Integer's, & Double's) can be modified after it is inserted into a list.
• Indices are checked to be within (0, list.size() - 1) however in some implementations, methods will throw an indexOutOfBoundsException if called with an invalid index argument

Objective #2: Use linked lists from the standard library (java.util.LinkedList).

• A linked list is a set of nodes (our textbook calls them links) that have fields which are references to the next node. In other words each node is linked to the next node. However, a doubly-linked list is a list in which each node has one link to the next node and another link to the previous node.
• The LinkedList<E> class (java.util.LinkedList) implements the List interface.
• In addition to the methods from java.util.List<E> above, the LinkedList<E> class includes these additional methods from the AP subset:
  
  
  • void addFirst(E x);
  • void addLast(E x);
  • E getFirst();
  • E getLast();
  • E removeFirst();
  • E removeLast();
    
    
• Linked lists allow fast insertion and removal of nodes, especially if the node that you are inserting is the first or the last node. But specific element access of other "inner" nodes is slow. Even though the LinkedList class includes the get and set methods from the List interface, these two methods are really only meant to be used with the ArrayList implementation of List (where an array is used in the behind-the-scenes implementation). They give the ability for random access to array lists. Using get and set with LinkedList objects is very inefficient. The linked list must be traversed and therefore the operation is O(n). To access the "middle" elements of linked list, an iterator (explained below) should be used.
• The underlying implementation of the official Java LinkedList class (i.e. java.util.LinkedList) is assumed to work in O(1) time. It uses a doubly-linked list so that all add/set/remove operations at the beginning and end of the list are constant-time or O(1) operations.
• Here's a recursive method that computes the sum of the Integer's stored in a Linked List
  
  public ListNode sum(ListNode node)
  {
     if (node == null)
        return 0;
     else
        return ((Integer) node.getValue()).intValue() + sum(node.getNext());
  }
  
  
• Here's an interesting recursive method that creates and returns a copy of the list that is passed as a parameter
  
  public ListNode copy(ListNode node)
  {
     if (node == null)
        return null;
     else
        return new ListNode(node.getValue(), mystery(node.getNext());
  }
  

Objective #3: Use iterators to traverse linked lists.

• An iterator is an object that is used to maintain the current position in a list and provides other useful methods for handling the list.
• When an iterator is constructed, it is positioned in front of the first element of the list.
• The AP subset includes iterators from the interfaces java.util.Iterator and java.util.ListIterator
  
• The iterator method of LinkedList returns an Iterator object. Three methods from the Iterator interface are covered on the AP exam:
  
  
  
  • boolean hasNext();
    
    The hasNext method should be called before calling the next method in case the iterator is at the end of the linked list.
    
    
  • E next();
    
    The next method is used to move an iterator as in
    
    iterator.next();
    
    The next method returns the object of the link that it is passing overtop of. The next method throws a NoSuchElementException if you are already past the end of the list.
    
    
  • void remove();
    
    The remove method removes and returns the object that was returned by the last call to next. The remove method can only be called once after calling next and you can't call it immediately after a call to the add method. If you call the remove method improperly, it throws an IllegalStateException.
    
    
  • While not covered on the AP exam, the previous and hasPrevious methods of the Iterator class allows you to move the iterator backwards.
    
    
• The listIterator method of LinkedList returns a ListIterator<E> object. A ListIterator<E> object includes all of the methods from Iterator<E> plus methods for traversing the list in reverse (not on AP exam) and methods for adding a value and setting an element's value. The two additional methods from the ListIterator<E> interface that are covered on the AP exam are:
  
  
  
  
  • void add(E x);
    
    The add method inserts an element before the current iterator position and then moves the iterator past the inserted element.
    
    
  • void set(E x);
    
    The set method overwrites the element that was last iterated over. You can only call set after a call to next.
    
    
• The following algorithm can be used to traverse a linked list
  
  Iterator iter = list.iterator();
  while (iter.hasNext())
  {
     Object object = iter.next();
     . . .
  }
  
• Iterators can be used with array lists as well as linked lists since ArrayList implements List also.

Objective #4: Implement linked lists.

• The AP subset includes the following ListNode class that will be used to help implement linked lists on the AP exam. This is more or less equivalent to our textbook author, Cay Horstmann's, inner Link class that is provided in Ch. 19.
  
  public class ListNode
  {
     public ListNode(Object initValue, ListNode initNext)
     {
        value = initValue;
        next = initNext;
     }
     public Object getValue()
     {
        return value;
     }
     public ListNode getNext()
     {
        return next;
     }
     public void setValue(Object theNewValue)
     {
        value = theNewValue;
     }
     public void setNext(ListNode theNewNext)
     {
        next = theNewNext;
     }
     private Object value;
     private ListNode next;
  }
  
  
• Even though the standard java.util.LinkedList class (which implements the standard java.util.List interface) is provided by Sun, it is a good exercise to implement your own customized linked list class using ListNode. You may be asked on the AP exam to implement part of a customized LinkedList class. For example, you may be asked to implement any one of the methods addFirst, addLast, getFirst, getLast, removeFirst, or removeLast. Be sure to take care of all boundary cases involving head and tail nodes.
  
  
• Suppose head points to the first node in a list. This algorithm can be used to traverse and print out all the values in the list
  
  ListNode node;
  for (node = head; node != null; node = node.getNext())
  {
     System.out.println(node.getValue());
  }
  
  
• Sun's java.util.LinkedList implements a list as a doubly-linked list where its nodes have next and previous fields. Each node of the linked list contains a reference to its next node and its previous node. The first node (i.e. head) has a reference to null for its previous node and the last node (i.e. tail) in the list has a reference to null for its next node. The java.util.LinkedList class also contains references to the first node and the last node. The reference to the first node is sometimes called a header node and the reference to the last node is often called a trailer node. These references are also called dummy nodes since they do not store values, just references. They are not printed when traversing the linked list.
• A circularly-linked list is a linked list implementation in which the last node points to the first node with its next reference rather than null. In order to be able to traverse a circularly-linked list and know when to stop, usually the implemenation of a circularly-linked list has a header node. In this case the expression   temp.getNext() == head   can be used to terminate the traversing loop.
• A linked list does not provide direct, random access to the list's elements. To get to a given node, you must traverse the list from the beginning and follow the links until you get to the desired node.
• A new node can be added to or removed from a linked list without having to shift nodes as in an array list. Rather, only a few links need to be rearranged.

Objective #5: Distinguish between abstract and concrete data types.

• An abstract data type (ADT) is a data type that is explained with pseudocode or OOD. You would use an abstract data type to discuss how you were going to handle data. An ADT is just a set of specifications that explain the operations that can be performed on the data. An ADT can usually be implemented in different ways. Often there is no best way to implement an ADT. One implementation may use more memory than another. Or, one implementation may cause the execution of a program to take longer than another implementation.
  
  
• A concrete data type is one that has been implemented in a programming language and can be used in code to actually store real data. You would usually use an abstract data type as a design model when implementing and writing out the concrete data type.
  
  
• Here is a chart that visually depicts the relationship between Lists, Stacks & Queues.

Objective #7: Use stacks.

• A stack uses last-in-first-out (LIFO) storage.
• A stack uses the operation push to place an item on top of the stack.
• A stack uses the operation pop to remove and return the top item of the stack.
• The AP subset includes the java.util.Stack<E> class with these methods:
  
  
  
  • boolean isEmpty();
  • E push(E x);
  • E pop();
  • E peek();
    
    Don't be confused if you look at the API for the Stack class. In addition to the isEmpty method that is inherited from the parent Vector class, there is a similar method named empty. The AP Exam will use the isEmpty method rather than the empty method.
    
    
• Here is an example of a client program that uses a Stack
  
  

  import java.util.Stack;
  
  public class Ch19DemoStack 
  {
  	public static void main(String[] args) 
  	{
  		Stack<String> myFriends = new Stack<String>();
  		myFriends.push("Britney");
  		myFriends.push("Paris");
  		myFriends.push("Hannah");
  		myFriends.push("Fergi");
  		myFriends.push("Lindsay");
  		myFriends.pop();
  		
  		if (!myFriends.isEmpty())
  		{
  			System.out.println(myFriends.peek());		
  		}
  		
  		System.out.println(myFriends.get(2)); 
  		// don't do this since using the get method would 
  		// violate the abstract data structure definition of a stack
  		// even though the Stack class inherits the get method
  		
  	}
  }
  
  

• A stack could be implemented using an array, an ArrayList, or a linked list. The following MysteryStack class is implemented using an ArrayList. The push and pop operations are O(1) since the top of the stack is the end of the ArrayList.
  
  public class MysteryStack
  {
     public MysteryStack()
     {
        items = new java.util.ArrayList();
     }
     public boolean isEmpty()
     {
        return items.size() == 0;
     }
     public void push(Object obj)
     {
        items.add(obj);
     }
     public Object pop()
     {
        return items.remove(items.size() - 1);
     }
     public Object peek()
     {
        return items.get(items.size() - 1);
     }
     private java.util.ArrayList items;
  }
  
  Notice that instead of importing ArrayList at the top of the file, you can type out java.util.ArrayList.
  
  Can you implement MysteryStack so that it uses a LinkedList?
  Can you implement MysteryStack so that it uses an array (i.e. [])?
  
  
• In practical programming, stacks are useful when testing mathematical expressions for balanced parentheses, evaluating postfix expressions, & keeping track of the scope of variables in within various sets of curly braces.

Objective #8: Use queues.

• A queue is an abstract data type that defines first-in-first-out (FIFO) storage of data elements. Queue is a concrete data type (specifically an interface) in Java.
• A queue is like a line of people waiting for concert tickets or to be served lunch in the cafeteria. The first person to get in line will eventually be the first person out of line. In fact, the word "queue" is a synonym for "line".
• A queue uses the add method to add an item to the queue. Because a queue is FIFO, the add method adds the new item to the end (or rear) of the queue.
• A queue uses the remove method to remove an item from the queue. Because a queue is FIFO, the remove method removes the next item from the beginning (or front) of the queue.
  
  
• The AP subset includes four methods from the java.util.Queue interface
  
     boolean isEmpty();
     boolean add(E x);
     E remove();
     E peek();
  
  Don't be confused. The isEmpty and add methods are inherited from the parent interface Collection.
  
  
• In a former version of Java, an enqueue method was used instead of add, a dequeue method was used instead of remove, and a peekFront method was used instead of peek. Don't be surprised if you see enqueue, dequeue and peekFront on old worksheets or practice AP exam workbooks.
  
  
• A queue could be implemented with an array, an ArrayList, or a linked list. Here is a MysteryQueue class that uses a linked list.
  
  public class MysteryQueue
  {
     public MysteryQueue()
     {
        items = new java.util.LinkedList();
     }
     public boolean isEmpty()
     {
        return items.size() == 0;
     }
     public boolean add(Object obj)
     {
        items.addLast(obj);
        return true;
     }
     public Object remove()
     {
        return items.removeFirst();
     }
     public Object peek()
     {
        if (items.size() > 0)
           return items.getFirst();
        return false;
     }
     private java.util.LinkedList items;
  }
  
  
• Can you implement a class named MysteryQueue upon an ArrayList? How about a fixed array ( [] )?
• In practical programming, queues are useful when simulating anything where a line tends to develop. Examples are network printer queues, line of cars at a car wash, airplanes waiting for permission to take-off on an airport runway, customers waiting in line at a grocery store, and email messages in an email server. In general, a queue is used to process events in the order that they arrive.
• Even though there is a Stack class from Sun, there is no Queue class. But there is a Queue interface. So you will likely see some kind of custom queue class that implements the Queue interface on various AP Exam questions. Or you may see a client program like the following where a LinkedList object is referenced as a Queue
  
  

  import java.util.LinkedList;
  import java.util.Queue;
  
  public class Ch19DemoQueue 
  {
  	public static void main(String[] args) 
  	{
  		Queue<String> myFriends = new LinkedList<String>();
  		myFriends.add("Britney");
  		myFriends.add("Paris");
  		myFriends.add("Hannah");
  		myFriends.add("Fergi");
  		myFriends.add("Lindsay");
  		myFriends.remove();
  		
  		if (!myFriends.isEmpty())
  		{
  			System.out.println(myFriends.peek());		
  		}
  		
  		System.out.println(myFriends.get(2)); 
  		// don't use the get method since it would 
  		// violate the abstract data structure definition of a queue
  	}
  }