A linked list is a data structure used for collecting a sequence of objects that allows efficient addition and removal of elements in the middle of the sequence.

To understand the need for such a data structure, imagine a program that maintains a sequence of employee objects, sorted by the last names of the employees. When a new employee is hired, an object needs to be inserted into the sequence. Unless the company happened to hire employees in alphabetical order, the new object probably needs to be inserted somewhere near the middle of the sequence. If we use an array to store the objects, then all objects following the new hire must be moved toward the end.

Conversely, if an employee leaves the company, the object must be removed, and the hole in the sequence needs to be closed up by moving all objects that come after it. Moving a large number of values can involve a substantial amount of processing time. We would like to structure the data in a way that minimizes this cost.

Rather than storing the values in an array, a linked list uses a sequence of nodes. Each node stores a value and a reference to the next node in the sequence (see Figure 1). When you insert a new node into a linked list, only the neighboring node references need to be updated. The same is true when you remove a node. What's the catch? Linked lists allow speedy insertion and removal, but element access can be slow.

Figure 15.1. Inserting an Element into a Linked List

For example, suppose you want to locate the fifth element. You must first traverse the first four. This is a problem if you need to access the elements in arbitrary order. The term "random access" is used in computer science to describe an access pattern in which elements are accessed in arbitrary (not necessarily random) order. In contrast, sequential access visits the elements in sequence. For example, a binary search requires random access, whereas a linear search requires sequential access.

Of course, if you mostly visit elements in sequence (for example, to display or print the elements), you don't need to use random access. Use linked lists when you are concerned about the efficiency of inserting or removing elements and you rarely need element access in random order.

The Java library provides a linked list class. In this section you will learn how to use that library class. In the next section you will peek under the hood and see how some of its key methods are implemented.

The LinkedList class in the java.util package is a generic class, just like the Array-List class. That is, you specify the type of the list elements in angle brackets, such as LinkedList<String> or LinkedList<Product>.

The methods shown in Table 1 give you direct access to the first and the last element in the list.

How do you add and remove elements in the middle of the list? The list will not give you references to the nodes. If you had direct access to them and somehow messed them up, you would break the linked list. As you will see in the next section, when you implement some of the linked list operations yourself, keeping all links between nodes intact is not trivial.

Instead, the Java library supplies a ListIterator type. A list iterator describes a position anywhere inside the linked list (see Figure 2).

Figure 15.2. A List Iterator

Conceptually, you should think of the iterator as pointing between two elements, just as the cursor in a word processor points between two characters (see Figure 3). In the conceptual view, think of each element as being like a letter in a word processor, and think of the iterator as being like the blinking cursor between letters.

You obtain a list iterator with the listIterator method of the LinkedList class:

LinkedList<String> employeeNames = ...;
ListIterator<String> iterator = employeeNames.listIterator();

Note that the iterator class is also a generic type. A ListIterator<String> iterates through a list of strings; a ListIterator<Product> visits the elements in a LinkedList<Product>.

Initially, the iterator points before the first element. You can move the iterator position with the next method:

iterator.next();

The next method throws a NoSuchElementException if you are already past the end of the list. You should always call the method hasNext before calling next—it returns true if there is a next element.

if (iterator.hasNext())
iterator.next();

The next method returns the element that the iterator is passing. When you use a ListIterator<String>, the return type of the next method is String. In general, the return type of the next method matches the type parameter of the list.

You traverse all elements in a linked list of strings with the following loop:

while (iterator.hasNext())
{
   String name = iterator.next();
   Do something with name
}

As a shorthand, if your loop simply visits all elements of the linked list, you can use the "for each" loop:

for (String name : employeeNames)
{
   Do something with name
}

Figure 15.3. A Conceptual View of the List Iterator

Then you don't have to worry about iterators at all. Behind the scenes, the for loop uses an iterator to visit all list elements (see Special Topic 15.1 on page 635).

The nodes of the LinkedList class store two links: one to the next element and one to the previous one. Such a list is called a doubly linked list. You can use the previous and hasPrevious methods of the ListIterator interface to move the iterator position backwards.

The add method adds an object after the iterator, then moves the iterator position past the new element.

iterator.add("Juliet");

You can visualize insertion to be like typing text in a word processor. Each character is inserted after the cursor, and then the cursor moves past the inserted character (see Figure 3). Most people never pay much attention to this—you may want to try it out and watch carefully how your word processor inserts characters.

The remove method removes the object that was returned by the last call to next or previous. For example, the following loop removes all names that fulfill a certain condition:

while (iterator.hasNext())
{
   String name = iterator.next();
   if (name fulfills condition)
      iterator.remove();
}

You have to be careful when using the remove method. It can be called only once after calling next or previous. The following is an error:

iterator.next();
iterator.next();
iterator.remove();
iterator.remove(); // Error: You cannot call remove twice.

You cannot call remove immediately after a call to add:

iter.add("Fred");
iter.remove(); // Error: Can only call remove after calling next or previous

If you call the remove method improperly, it throws an IllegalStateException.

Table 2 summarizes the methods of the ListIterator interface.

if (iter.hasPrevious())
{
   s = iter.previous();
}

iter.next();
iter.remove();

Here is a sample program that inserts strings into a list and then iterates through the list, adding and removing elements. Finally, the entire list is printed. The comments indicate the iterator position.

ch15/uselist/ListTester.java

1  import java.util.LinkedList;
2  import java.util.ListIterator;
3
4  /**
5     A program that tests the LinkedList class.
6  */
7  public class ListTester
8  {
9     public static void main(String[] args)
10     {
11        LinkedList<String> staff = new LinkedList<String>();
12        staff.addLast("Diana");
13        staff.addLast("Harry");
14        staff.addLast("Romeo");
15        staff.addLast("Tom");
16
17        // | in the comments indicates the iterator position
18
19        ListIterator<String> iterator = staff.listIterator(); // |DHRT
20        iterator.next(); // D|HRT
21        iterator.next(); // DH|RT
22
23        // Add more elements after second element
24
25        iterator.add("Juliet"); // DHJ|RT
26        iterator.add("Nina"); // DHJN|RT
27
28        iterator.next(); // DHJNR|T
29

30        // Remove last traversed element
31
32        iterator.remove(); // DHJN|T
33
34        // Print all elements
35
36        for (String name : staff)
37           System.out.print(name + " ");
38        System.out.println();
39        System.out.println("Expected: Diana Harry Juliet Nina Tom");
40       }
41    }

Program Run

Diana Harry Juliet Nina Tom
Expected: Diana Harry Juliet Nina Tom

2. Why don't we need iterators with arrays?

for (Type variable : collection)

public interface Iterable<E>
{
   Iterator<E> iterator();
}

boolean hasNext();
E next();

for (Type variable : collection)
   body

Iterator<Type> iter = collection.iterator();
while (iter.hasNext())
{

Type variable = iter.next();
   body
}

In the last section you saw how to use the linked list class supplied by the Java library. In this section, we will look at the implementation of a simplified version of this class. This shows you how the list operations manipulate the links as the list is modified.

To keep this sample code simple, we will not implement all methods of the linked list class. We will implement only a singly linked list, and the list class will supply direct access only to the first list element, not the last one. Our list will not use a type parameter. We will simply store raw Object values and insert casts when retrieving them. The result will be a fully functional list class that shows how the links are updated in the add and remove operations and how the iterator traverses the list.

A Node object stores an object and a reference to the next node. Because the methods of both the linked list class and the iterator class have frequent access to the Node instance variables, we do not make the instance variables of the Node class private. Instead, we make Node a private inner class of the LinkedList class. Because none of the LinkedList methods returns a Node object, it is safe to leave the instance variables public.

public class LinkedList
{
   ...
   class Node
   {
      public Object data;
      public Node next;
   }
}

Our LinkedList class holds a reference first to the first node (or null, if the list is completely empty).

public class LinkedList
{
   private Node first;
   ...
   public LinkedList()
   {
      first = null;
   }

   public Object getFirst()
   {
      if (first == null)
         throw new NoSuchElementException();

return first.data;
   }
}

Now let us turn to the addFirst method (see Figure 4). When a new node is added to the list, it becomes the head of the list, and the node that was the old list head becomes its next node:

public class LinkedList
{
   . . .
   public void addFirst(Object element)
   {
      Node newNode = new Node();

      newNode.data = element;

      newNode.next = first;

      first = newNode;
   }
   . . .
}

Figure 15.4. Adding a Node to the Head of a Linked List

Figure 15.5. Removing the First Node from a Linked List

Removing the first element of the list works as follows. The data of the first node are saved and later returned as the method result. The successor of the first node becomes the first node of the shorter list (see Figure 5). Then there are no further references to the old node, and the garbage collector will eventually recycle it.

public class LinkedList
{
   . . .
   public Object removeFirst()
   {
      if (first == null)
         throw new NoSuchElementException();
      Object element = first.data;
      first = first.next;

      return element;
   }
   . . .
}

Next, we need to implement the iterator class. The ListIterator interface in the standard library declares nine methods. We omit four of them (the methods that move the iterator backwards and the methods that report an integer index of the iterator).

Our LinkedList class declares a private inner class LinkedListIterator, which implements our simplified ListIterator interface. Because LinkedListIterator is an inner class, it has access to the private features of the LinkedList class—in particular, the instance variable first and the private Node class.

Note that clients of the LinkedList class don't actually know the name of the iterator class. They only know it is a class that implements the ListIterator interface.

public class LinkedList
{
   ...
   public ListIterator listIterator()
   {
      return new LinkedListIterator();

}

   class LinkedListIterator implements ListIterator
   {
       private Node position;
       private Node previous;
      ...
      public LinkedListIterator()
      {
          position = null;
          previous = null;
      }
   }
    ...
}

Each iterator object has a reference, position, to the last visited node. We also store a reference to the last node before that, previous. We will need that reference to adjust the links properly in the remove method.

The next method is simple. The position reference is advanced to position.next, and the old position is remembered in previous. There is a special case, however—if the iterator points before the first element of the list, then the old position is null, and position must be set to first.

class LinkedListIterator implements ListIterator
{
    ...
   public Object next()
   {
      if (!hasNext())
         throw new NoSuchElementException();
      previous = position; // Remember for remove

      if (position == null)
         position = first;
      else
         position = position.next;

      return position.data;
   }
   ...
}

The next method is supposed to be called only when the iterator is not yet at the end of the list, so we declare the hasNext method accordingly. The iterator is at the end if the list is empty (that is, first == null) or if there is no element after the current position (position.next == null).

class LinkedListIterator implements ListIterator
{
   ...
   public boolean hasNext()
   {
      if (position == null)
         return first != null;
      else
         return position.next != null;
   }
    ...
}

Figure 15.6. Removing a Node from the Middle of a Linked List

Removing the last visited node is more involved. If the element to be removed is the first element, we just call removeFirst. Otherwise, an element in the middle of the list must be removed, and the node preceding it needs to have its next reference updated to skip the removed element (see Figure 6). If the previous reference equals position, then this call to remove does not immediately follow a call to next, and we throw an IllegalStateException.

According to the declaration of the remove method, it is illegal to call remove twice in a row. Therefore, the remove method sets the position reference to previous.

class LinkedListIterator implements ListIterator
{
   . . .
   public void remove()
   {
      if (previous == position)
         throw new IllegalStateException();
      if (position == first)
      {
         removeFirst();
      }
      else
      {
         previous.next = position.next;

      }
      position = previous;

   }
   . . .
}

The set method changes the data stored in the previously visited element. Its implementation is straightforward because our linked lists can be traversed in only one direction. The linked list implementation of the standard library must keep track of whether the last iterator movement was forward or backward. For that reason, the standard library forbids a call to the set method following an add or remove method. That restriction is unnecessary in our implementation, and we do not enforce it.

public void set(Object element)
{
   if (position == null)
      throw new NoSuchElementException();
   position.data = element;
}

Finally, the most complex operation is the addition of a node. You insert the new node after the node last visited by the iterator (see Figure 7).

class LinkedListIterator implements ListIterator
{
   . . .
   public void add(Object element)
   {
      if (position == null)
      {
         addFirst(element);
         position = first;
      }
      else
      {
         Node newNode = new Node();
         newNode.data = element;
         newNode.next = position.next;

         position.next = newNode;

         position = newNode;

      }
      previous = position;

    }
    . . .
}

Figure 15.7. Adding a Node to the Middle of a Linked List

At the end of this section is the complete implementation of our LinkedList class.

You now know how to use the LinkedList class in the Java library, and you have had a peek "under the hood" to see how linked lists are implemented.

ch15/impllist/LinkedList.java

1   import java.util.NoSuchElementException;
2
3   /**
4      A linked list is a sequence of nodes with efficient
5      element insertion and removal. This class
6      contains a subset of the methods of the standard
7      java.util.LinkedList class.
8   */
9   public class LinkedList
10   {
11      private Node first;
12
13      /**
14         Constructs an empty linked list.
15      */
16      public LinkedList()
17      {
18         first = null;
19      }
20
21      /**
22         Returns the first element in the linked list.
23         @return the first element in the linked list
24      */
25      public Object getFirst()
26      {
27          if (first == null)
28             throw new NoSuchElementException();
29         return first.data;
30      }
31
32      /**
33         Removes the first element in the linked list.
34         @return the removed element
35      */
36      public Object removeFirst()
37      {
38         if (first == null)
39             throw new NoSuchElementException();
40         Object element = first.data;
41         first = first.next;
42         return element;
43      }
44
45      /**
46         Adds an element to the front of the linked list.
47         @param element the element to add
48      */
49      public void addFirst(Object element)
50      {
51         Node newNode = new Node();
52         newNode.data = element;
53         newNode.next = first;
54         first = newNode;
55      }
56

57     /**
58        Returns an iterator for iterating through this list.
59        @return an iterator for iterating through this list
60     */
61     public ListIterator listIterator()
62     {
63       return new LinkedListIterator();
64     }
65
66     class Node
67     {
68       public Object data;
69       public Node next;
70     }
71
72     class LinkedListIterator implements ListIterator
73     {
74          private Node position;
75          private Node previous;
76
77          /**
78          Constructs an iterator that points to the front
79          of the linked list.
80          */
81          public LinkedListIterator()
82          {
83             position = null;
84             previous = null;
85          }
86
87          /**
88            Moves the iterator past the next element.
89            @return the traversed element
90          */
91          public Object next()
92          {
93            if (!hasNext())
94               throw new NoSuchElementException();
95            previous = position; // Remember for remove
96
97            if (position == null)
98               position = first;
99            else
100                position = position.next;
101
102            return position.data;
103         }
104
105         /**
106            Tests if there is an element after the iterator position.
107            @return true if there is an element after the iterator position
108         */
109         public boolean hasNext()
110         {
111             if (position == null)
112                return first != null;
113             else
114                return position.next != null;
115         }

116
117         /**
118           Adds an element before the iterator position
119           and moves the iterator past the inserted element.
120           @param element the element to add
121         */
122           public void add(Object element)
123         {
124            if (position == null)
125            {
126                addFirst(element);
127                position = first;
128            }
129           else
130            {
131                 Node newNode = new Node();
132                 newNode.data = element;
133                 newNode.next = position.next;
134                 position.next = newNode;
135                 position = newNode;
136            }
137                previous = position;
138         }
139
140         /**
141           Removes the last traversed element. This method may
142           only be called after a call to the next() method.
143         */
144          public void remove()
145         {
146           if (previous == position)
147              throw new IllegalStateException();
148
149             if (position == first)
150           {
151                removeFirst();
152           }
153           else
154           {
155              previous.next = position.next;
156           }
157              position = previous;
158         }
159
160         /**
161              Sets the last traversed element to a different value.
162              @param element the element to set
163         */
164              public void set(Object element)
165         {
166              if (position == null)
167                 throw new NoSuchElementException();
168              position.data = element;
169         }
170      }
171   }

ch15/impllist/ListIterator.java

1  /**
2     A list iterator allows access to a position in a linked list.
3     This interface contains a subset of the methods of the
4     standard java.util.ListIterator interface. The methods for
5     backward traversal are not included.
6  */
7  public interface ListIterator
8  {
9     /**
10       Moves the iterator past the next element.
11       @return the traversed element
12     */
13     Object next();
14
15     /**
16       Tests if there is an element after the iterator position.
17       @return true if there is an element after the iterator position
18     */
19     boolean hasNext();
20
21     /**
22       Adds an element before the iterator position
23       and moves the iterator past the inserted element.
24        @param element the element to add
25     */
26     void add(Object element);
27
28     /**
29       Removes the last traversed element. This method may
30       only be called after a call to the next() method.
31     */
32     void remove();
33
34     /**
35       Sets the last traversed element to a different value.
36       @param element the element to set
37     */
38     void set(Object element);
39  }

4. Conceptually, an iterator points between elements (see Figure 3). Does the position reference point to the element to the left or to the element to the right?

5. Why does the add method have two separate cases?

public class LinkedList
{
   ...
   private static class Node
   {
      ...
   }
}

There are two ways of looking at a linked list. One way is to think of the concrete implementation of such a list as a sequence of node objects with links between them (see Figure 8).

On the other hand, you can think of the abstract concept that underlies the linked list. In the abstract, a linked list is an ordered sequence of data items that can be traversed with an iterator (see Figure 9).

Figure 15.8. A Concrete View of a Linked List

Figure 15.9. An Abstract View of a List

Figure 15.10. A Concrete View of an Array List

Figure 15.11. An Abstract View of an Array

Similarly, there are two ways of looking at an array list. Of course, an array list has a concrete implementation: a partially filled array of object references (see Figure 10). But you don't usually think about the concrete implementation when using an array list. You take the abstract point of view. An array list is an ordered sequence of data items, each of which can be accessed by an integer index (see Figure 11).

The concrete implementations of a linked list and an array list are quite different. The abstractions, on the other hand, seem to be similar at first glance. To see the difference, consider the public interfaces stripped down to their minimal essentials.

An array list allows random access to all elements. You specify an integer index, and you can get or set the corresponding element.

public class ArrayList
{
    ...
   public Object get(int index) { ... }
   public void set(int index, Object element) { ... }
    ...
}

With a linked list, on the other hand, element access is a bit more complex. A linked list allows sequential access. You need to ask the linked list for an iterator. Using that iterator, you can easily traverse the list elements one at a time. But if you want to go to a particular element, say the 100th one, you first have to skip all elements before it.

public class LinkedList
{
    ...
   public ListIterator listIterator() { ... }
    ...
}

public interface ListIterator
{
   Object next();
   boolean hasNext();
   void add(Object element);
   void remove();
   void set(Object element);
   ...
}

Here we show only the fundamental operations on array lists and linked lists. Other operations can be composed from these fundamental operations. For example, you can add or remove an element in an array list by moving all elements beyond the insertion or removal index, calling get and set multiple times.

Of course, the ArrayList class has methods to add and remove elements in the middle, even if they are slow. Conversely, the LinkedList class has get and set methods that let you access any element in the linked list, albeit very inefficiently, by performing repeated sequential accesses.

In fact, the term ArrayList signifies that its implementors wanted to combine the interfaces of an array and a list. Somewhat confusingly, both the ArrayList and the LinkedList class implement an interface called List that declares operations both for random access and for sequential access.

That terminology is not in common use outside the Java library. Instead, let us adopt a more traditional terminology. We will call the abstract types array and list. The Java library provides concrete implementations ArrayList and LinkedList for these abstract types. Other concrete implementations are possible in other libraries. In fact, Java arrays are another implementation of the abstract array type.

To understand an abstract data type completely, you need to know not just its fundamental operations but also their relative efficiency.

In an abstract list, an element can be added or removed in constant time (assuming that the iterator is already in the right position). A fixed number of node references need to be modified to add or remove a node, regardless of the size of the list. Using the big-Oh notation, an operation that requires a bounded amount of time, regardless of the total number of elements in the structure, is denoted as O(1). Random access in an abstract array also takes O(1) time.

Adding or removing an arbitrary element in an abstract array of size n takes O(n) time, because on average n/2 elements need to be moved. Random access in an abstract list takes O(n) time because on average n/2 elements need to be skipped.

Table 3 shows this information for abstract arrays and lists.

Why consider abstract types at all? If you implement a particular algorithm, you can tell what operations you need to carry out on the data structures that your algorithm manipulates. You can then determine the abstract type that supports those operations efficiently, without being distracted by implementation details.

For example, suppose you have a sorted collection of items and you want to locate items using the binary search algorithm (see Section 14.7). That algorithm makes a random access to the middle of the collection, followed by other random accesses. Thus, fast random access is essential for the algorithm to work correctly. Once you know that an abstract array supports fast random access and an abstract list does not, you then look for concrete implementations of the abstract array type. You won't be fooled into using a LinkedList, even though the LinkedList class actually provides get and set methods.

In the next section, you will see additional examples of abstract data types.

7. How would you sketch an abstract view of a doubly linked list? A concrete view?

8. How much slower is the binary search algorithm for an abstract list compared to the linear search algorithm?

In this section we will consider two common abstract data types that allow insertion and removal of items at the ends only, not in the middle. A stack lets you insert and remove elements at only one end, traditionally called the top of the stack. To visualize a stack, think of a stack of books (see Figure 12).

New items can be added to the top of the stack. Items are removed at the top of the stack as well. Therefore, they are removed in the order that is opposite from the order in which they have been added, called last in, first out or LIFO order. For example, if you add items A, B, and C and then remove them, you obtain C, B, and A. Traditionally, the addition and removal operations are called push and pop.

A queue is similar to a stack, except that you add items to one end of the queue (the tail) and remove them from the other end of the queue (the head). To visualize a queue, simply think of people lining up (see Figure 13). People join the tail of the queue and wait until they have reached the head of the queue. Queues store items in a first in, first outor FIFO fashion. Items are removed in the same order in which they have been added.

Figure 15.12. A Stack of Books

Figure 15.13. A Queue

There are many uses of queues and stacks in computer science. The Java graphical user interface system keeps an event queue of all events, such as mouse and keyboard events. The events are inserted into the queue whenever the operating system notifies the application of the event. Events are removed and passed to event listeners in the order in which they were inserted. Another example is a print queue. A printer may be accessed by several applications, perhaps running on different computers. If each of the applications tried to access the printer at the same time, the printout would be garbled. Instead, each application places all bytes that need to be sent to the printer into a file and inserts that file into the print queue. When the printer is done printing one file, it retrieves the next one from the queue. Therefore, print jobs are printed using the "first in, first out" rule, which is a fair arrangement for users of the shared printer.

Stacks are used when a "last in, first out" rule is required. For example, consider an algorithm that attempts to find a path through a maze. When the algorithm encounters an intersection, it pushes the location on the stack, and then it explores the first branch. If that branch is a dead end, it returns to the location at the top of the stack and explores the next untried branch. If all branches are dead ends, it pops the location off the stack, revealing a previously encountered intersection. Another important example is the run-time stack that a processor or virtual machine keeps to organize the variables of nested methods. Whenever a new method is called, its parameters and local variables are pushed onto a stack. When the method exits, they are popped off again. This stack makes recursive method calls possible.

There is a Stack class in the Java library that implements the abstract stack type and the push and pop operations.

The Queue interface in the standard Java library has methods add to add an element to the tail of the queue, remove to remove the head of the queue, and peek to get the head element of the queue without removing it.

The standard library provides a number of queue classes for programs in which multiple activities, called threads, run in parallel. These queues are useful for sharing work between threads. We do not discuss those classes in this book. The LinkedList class also implements the Queue interface, and you can use it when a queue is required:

Queue<String> q = new LinkedList<String>();

Table 4 shows how to use the stack and queue methods in Java.

The Stack class in the Java library uses an array list to implement a stack. Exercise P15.15 shows how to use a linked list instead.

You would definitely not want to use an array list to implement a queue. Removing the first element of an array list is inefficient—all other elements must be moved toward the beginning. A queue can be efficiently implemented as a linked list. Moreover, Exercise P15.16 shows you how to implement a queue efficiently as a "circular" array, in which all elements stay at the position at which they were inserted, but the index values that denote the head and tail of the queue change when elements are added and removed.

In this chapter, you have seen the two most fundamental abstract data types, arrays and lists, and their concrete implementations. You also learned about the stack and queue types. In the next chapter, you will see additional data types that require more sophisticated implementation techniques.

10. Why wouldn't you want to use a stack to manage print jobs?

Reverse Polish Notation

In the 1920s, the Polish mathematician Jan realized that it is possible to dispense with parentheses in arithmetic expressions, provided that you write the operators before their arguments, for example, + 3 4 instead of 3 + 4. Thirty years later, Australian computer scientist Charles Hamblin noted that an even better scheme would be to have the operators follow the operands. This was termed reverse Polish notation or RPN.

Reverse Polish notation might look strange to you, but that is just an accident of history. Had earlier mathematicians realized its advantages, today's schoolchildren might be using it and not worry about precedence rules and parentheses.

Standard Notation	Reverse Polish Notation
3 + 4	3 4 +
3 + 4 × 5	3 4 5 × +
3 × (4 + 5)	3 4 5 + ×
(3 + 4) × (5 + 6)	3 4 + 5 6 + ×
3 + 4 + 5	3 4 + 5 +

In 1972, Hewlett-Packard introduced the HP 35 calculator that used reverse Polish notation. The calculator had no keys labeled with parentheses or an equals symbol. There is just a key labeled ENTER to push a number onto a stack. For that reason, Hewlett-Packard's marketing department used to refer to their product as "the calculators that have no equal".

Figure 15.14. The Calculator with No Equal

Over time, calculator vendors have adapted to the standard algebraic notation rather than forcing its users to learn a new notation. However, those users who have made the effort to learn reverse Polish notation tend to be fanatic proponents, and to this day, some Hewlett-Packard calculator models still support it.

java.util.Collection<E>      java.util.LinkedList<E>     java.util.ListIterator<E>
   add                          addFirst                    add
   contains                     addLast                     hasPrevious
   iterator                     getFirst                    previous
   remove                       getLast                     set
   size                         removeFirst
java.util.Iterator<E>           removeLast
   hasNext                 java.util.List<E>
   next                         listIterator
   remove

LinkedList<String> staff = new LinkedList<String>();
staff.addFirst("Harry");
staff.addFirst("Diana");
staff.addFirst("Tom");
System.out.println(staff.removeFirst());
System.out.println(staff.removeFirst());
System.out.println(staff.removeFirst());

LinkedList<String> staff = new LinkedList<String>();
staff.addFirst("Harry");
staff.addFirst("Diana");
staff.addFirst("Tom");
System.out.println(staff.removeLast());
System.out.println(staff.removeFirst());
System.out.println(staff.removeLast());

LinkedList<String> staff = new LinkedList<String>();
staff.addFirst("Harry");
staff.addLast("Diana");
staff.addFirst("Tom");
System.out.println(staff.removeLast());
System.out.println(staff.removeFirst());
System.out.println(staff.removeLast());

LinkedList<String> staff = new LinkedList<String>();
ListIterator<String> iterator = staff.listIterator();
iterator.add("Tom");
iterator.add("Diana");
iterator.add("Harry");
iterator = staff.listIterator();
if (iterator.next().equals("Tom"))
   iterator.remove();
while (iterator.hasNext())
   System.out.println(iterator.next());

LinkedList<String> staff = new LinkedList<String>();
ListIterator<String> iterator = staff.listIterator();
iterator.add("Tom");
iterator.add("Diana");
iterator.add("Harry");
iterator = staff.listIterator();
iterator.next();
iterator.next();
iterator.add("Romeo");
iterator.next();
iterator.add("Juliet");
iterator = staff.listIterator();
iterator.next();
iterator.remove();
while (iterator.hasNext())
   System.out.println(iterator.next());

Programming Exercises

P15.1 Using only the public interface of the linked list class, write a method

public static void downsize(LinkedList<String> staff)

that removes every other employee from a linked list.

P15.2 Using only the public interface of the linked list class, write a method

public static void reverse(LinkedList<String> staff)

that reverses the entries in a linked list.

P15.3 Add a method reverse to our implementation of the LinkedList class that reverses the links in a list. Implement this method by directly rerouting the links, not by using an iterator.

P15.4 Add a method size to our implementation of the LinkedList class that computes the number of elements in the list, by following links and counting the elements until the end of the list is reached.

P15.5 Add an instance variable currentSize to our implementation of the LinkedList class. Modify the add and remove methods of both the linked list and the list iterator to update the currentSize variable so that it always contains the correct size. Change the size method of the preceding exercise so that it simply returns the value of this instance variable.

P15.6 The linked list class of the standard library has an add method that allows efficient insertion at the end of the list. Implement this method for the LinkedList class in Section 15.2. Add an instance variable to the linked list class that points to the last node in the list. Make sure the other mutator methods update that variable.

P15.7 Repeat Exercise P15.6, but use a different implementation strategy. Remove the reference to the first node in the LinkedList class, and make the next reference of the last node point to the first node, so that all nodes form a cycle. Such an implementation is called a circular linked list.

P15.8 Reimplement the LinkedList class of Section 15.2 so that the Node and LinkedList-Iterator classes are not inner classes.

P15.9 Add an instance variable previous to the Node class in Section 15.2, and supply previous and hasPrevious methods in the iterator.

P15.10 The LISP language, created in 1960, implements linked lists in a very elegant way. You will explore a Java analog in this set of exercises. The key observation is that the tail of an abstract list—that is, the list with its head node removed—is also a list. The tail of that list is again a list, and so on, until you reach the empty list. Here is a Java interface for such as list:

public interface LispList
{
   boolean isEmpty();
   Object head();
   LispList tail();
   ...
}

There are two kinds of lists, empty lists and nonempty lists:

public class EmptyList extends LispList { ... }
public class NonEmptyList extends LispList { ... }

These classes are quite trivial. The EmptyList class has no instance variables. Its head and tail methods simply throw an UnsupportedOperationException, and its isEmpty method returns true. The NonEmptyList class has instance variables for the head and tail.

Here is one way of making a lisp list with three elements:

LispList list = new NonEmptyList("A", new NonEmptyList("B",
   new NonEmptyList("C", new EmptyList())));

This is a bit tedious, and it is a good idea to supply a convenience method cons that calls the constructor, as well as a static variable NIL that is an instance of an empty list. Then our list construction becomes

LispList list = NIL.cons("C").cons("B").cons("A");

Note that you need to build up the list starting from the (empty) tail.

To see the elegance of this approach, consider the implementation of a toString method that produces a string containing all list elements. The method must be implemented by both subclasses:

public class EmptyList
{
    ...
   public String toString() { return ""; }
}

public class NonEmptyList
{
    ...
   public String toString() { return head() + " " + tail().toString(); }
}

Note that no if statement is required. A list is either empty or nonempty, and the correct toString method is invoked due to polymorphism.

In this exercise, complete the LispList interface and the EmptyList and NonEmptyList classes. Write a test program that constructs a list and prints it.

P15.11 Add a method length to the LispList interface of Exercise P15.10 that returns the length of the list. Implement the method in the EmptyList and NonEmptyList classes.

P15.12 Add a method

LispList merge(LispList other)

to the LispList interface of Exercise P15.10 that returns the length of the list. Implement the method in the EmptyList and NonEmptyList classes. When merging two lists, alternate between the elements, then add the remainder of the longer list. For example, merging the lists with elements 1 2 3 4 and 5 6 yields 1 5 2 6 3 4.

P15.13 Add a method

boolean contains(Object obj)

to the LispList interface of Exercise P15.10 that returns true if the list contains an element that equals obj.

P15.14 The standard Java library implements a Stack class, but in this exercise you are asked to provide your own implementation. Do not implement type parameters. Use an Object[] array to hold the stack elements. When the array fills up, allocate an array of twice the size and copy the values to the larger array.

P15.15 Implement a Stack class by using a linked list to store the elements. Do not implement type parameters.

P15.16 Implement a queue as a circular array as follows: Use two index variables head and tail that contain the index of the next element to be removed and the next element to be added. After an element is removed or added, the index is incremented (see Figure 15 on page 661).

After a while, the tail element will reach the top of the array. Then it "wraps around" and starts again at 0—see Figure 16 on page 661. For that reason, the array is called "circular".

public class CircularArrayQueue
{
   private int head;
   private int tail;
   private int theSize;
   private Object[] elements;

   public CircularArrayQueue(int capacity) { ... }
   public void add(Object x) { ... }
   public Object remove() { ... }
   public int size() { ... }
}

This implementation supplies a bounded queue—it can eventually fill up. See the next exercise on how to remove that limitation.

P15.17 The queue in Exercise P15.16 can fill up if more elements are added than the array can hold. Improve the implementation as follows. When the array fills up, allocate a larger array, copy the values to the larger array, and assign it to the elements instance variable. Hint: You can't just copy the elements into the same position of the new array. Move the head element to position 0 instead.

Figure 15.15. Adding and Removing Queue Elements

Figure 15.16. A Queue That Wraps Around the End of the Array

P15.18 Modify the insertion sort algorithm of Special Topic 14.1 to sort a linked list.

P15.19 Modify the Invoice class of Chapter 12 so that it implements the Iterable<LineItem> interface. Then demonstrate how an Invoice object can be used in a "for each" loop.

P15.20 In a paint program, a "flood fill" fills all empty pixels of a drawing with a given color, stopping when it reaches occupied pixels. In this exercise, you will implement a simple variation of this algorithm, flood-filling a 10 × 10 array of integers that are initially 0. Prompt for the starting row and column. Push the (row, column) pair on a stack. (You will need to provide a simple Pair class.)

Then repeat the following operations until the stack is empty.

• Pop off the (row, column) pair from the top of the stack.

• If it has not yet been filled, fill it now. (Fill in numbers 1, 2, 3, and so on, to show the order in which the square is filled.)

• Push the coordinates of any unfilled neighbors in the north, east, south, or west direction on the stack.

When you are done, print the entire array.

P15.21 Repeat Exercise P15.20, but use a queue instead.

P15.22 Use a stack to enumerate all permutations of a string. Suppose you want to find all permutations of the string meat. Push the string +meat on the stack. Now repeat the following operations until the stack is empty.

• Pop off the top of the stack.

• If that string ends in a + (such as tame+), remove the + and print the string

• Otherwise, remove each letter in turn from the right of the +, insert it just before the +, and push the resulting string on the stack. For example, after popping e+mta, you push em+ta, et+ma, and ea+mt.

P15.23 Repeat Exercise P15.22, but use a queue instead.

P15.24 Write a program to display a linked list graphically. Draw each element of the list as a box, and indicate the links with line segments. Draw an iterator as in Figure 3. Supply buttons to move the iterator and to add and remove elements.

Programming Projects

Project 15.1 Implement a class Polynomial that describes a polynomial such as

p(x) = 5x10 + 9x7 − x − 10

Store a polynomial as a linked list of terms. A term contains the coefficient and the power of x. For example, you would store p(x) as

(5, 10), (9, 7), (−1, 1), (−10, 0)

Supply methods to add, multiply, and print polynomials, and to compute the derivative of a polynomial.

Project 15.2 Make the list implementation of this chapter as powerful as the implementation of the Java library. (Do not implement type parameters, though.)

• Provide bidirectional iteration.

• Make Node a static inner class.

• Implement the standard List and ListIterator interfaces and provide the missing methods. (Tip: You may find it easier to extend AbstractList instead of implementing all List methods from scratch.)

Project 15.3 Implement the following algorithm for the evaluation of arithmetic expressions.

Each operator has a precedence. The + and - operators have the lowest precedence, * and / have a higher (and equal) precedence, and ^ (which denotes "raising to a power" in this exercise) has the highest. For example,

3 * 4 ^ 2 + 5

should mean the same as

(3 * (4 ^ 2)) + 5

with a value of 53.

In your algorithm, use two stacks. One stack holds numbers, the other holds operators. When you encounter a number, push it on the number stack. When you encounter an operator, push it on the operator stack if it has higher precedence than the operator on the top of the stack. Otherwise, pop an operator off the operator stack, pop two numbers off the number stack, and push the result of the computation on the number stack. Repeat until the top of the operator stack has lower precedence. At the end of the expression, clear the stack in the same way. For example, here is how the expression 3 * 4 ^ 2 + 5 is evaluated:

You should enhance this algorithm to deal with parentheses. Also, make sure that subtractions and divisions are carried out in the correct order. For example, 12 − 5 − 3 should yield 4.