CHAPTER 7
Linked Lists
In this chapter we continue our study of collection classes by introducing the LinkedList class, part of the Java Collections Framework. Like the ArrayList class, the LinkedList class implements the List interface, so you are already familiar with most of the LinkedList method headings. There are some significant performance differences between the two classes. For example, LinkedList objects lack the random-access feature of ArrayList objects: to access a LinkedList 's element from an index requires a loop. But LinkedList objects allow constant-time insertions and deletions, once the insertion-point or deletion-point has been accessed.
We will start with a general discussion of linked lists, and then introduce a simple linked structure, the singlyLinkedList class. This toy class serves mainly to prepare you for the more powerful, and more complicated, LinkedList class. The application of the LinkedList class, a line editor, takes advantage of a LinkedList iterator's ability to insert or remove in constant time.
CHAPTER OBJECTIVES
- Be able to develop new methods for the singlyLinkedList class.
- Understand the LinkedList class from a user's perspective.
- Given an application that requires a list, be able to decide whether an ArrayList or a LinkedList would be more appropriate.
- Compare several choices of fields for the LinkedList class and, for each choice, be able to create a LinkedList object.
7.1 What is a Linked List?
Before we start investigating the LinkedList class, let's spend a little time on the general concept of a linked list. A linked list is a List object (that is, an object in a class that implements the List interface) in which the following property is satisfied:
Each element is contained in an object, called an Entry object, which also includes a reference, called a link, to the Entry object that contains the next element in the list.
For the Entry object that holds the last element, there is no "next" element.
For example, Figure 7.1 shows part of a linked list.
Some linked lists also satisfy the following property:
Each Entry object includes a link to the Entry object that contains the previous element in the list.
FIGURE 7.1 Part of a linked list
FIGURE 7.2 Part of a doubly-linked list
A linked list that satisfies the second property is called a doubly-linked list. Otherwise, it is called a singly-linked list. For example, Figure 7.2 shows part of a doubly-linked list with three elements, and they happen to be in alphabetical order.
We have intentionally omitted any indication of how the first and last elements are identified, and what is stored in their previous and next links, respectively. In Section 7.3, we'll see that there are several options.
Most of this chapter is devoted to doubly-linked lists, but we will start by studying singly-linked lists because, as you might imagine, they are easier to develop (they are also less powerful).
7.2 The SinglyLinkedList Class— A Singly-Linked, Toy Class!
We now create a class, SinglyLinkedList, that implements the List interface of the Java Collections Framework. As suggested by Figure 7.1, the basic idea is to link the elements together in a chain: with each element we will include a reference to the next element in the collection. You will have the opportunity to expand on this SinglyLinkedList class in Lab 12 and in three of the programming projects at the end of this chapter.
The SinglyLinkedList class has very little functionality, and is not part of the Java Collections Framework. You will never use it for application programs. Why bother to learn it in the first place? You should view the SinglyLinkedList class as a "toy" class that highlights the concepts of links and iterators, two essential features of the Java Collections Framework. And, like any other toy, you will have the opportunity to play with the SinglyLinkedList class: to add new fields and methods, and to alter the definitions of existing methods. You will study the SinglyLinkedList class mainly to make it easier for you to understand the LinkedList class, which is in the Java Collections Framework. The LinkedList class, doubly-linked, is quite powerful but also somewhat complex.
The elements in a SinglyLinkedList object are not stored contiguously, so with each element we must provide information on how to get to the next element in the collection. First, we create a class to hold a reference to an element and a "next" reference. In this Entry class, there are no specified methods (of course, there is a default constructor) and two fields, with E the type parameter:
protected class Entry<E> { protected E element; protected Entry<E> next; } // class Entry
The next field in an Entry holds a reference to another Entry object. A reference to an Entry object is called a link. For example, Figure 7.3 depicts a sequence of linked entries; each element is a (reference to a) String object. We use an arrow to indicate that the next field at the base of the arrow contains a reference to the Entry object pointed to by the tip of the arrow. And, for the sake of simplicity, we pretend that the type of element is string rather than reference-to-string. In the last Entry object, the next field has the value null, which indicates that there is no subsequent Entry object.
FIGURE 7.3 Part of a singly-linked list of three string elements
The Entry class will be embedded in the SinglyLinkedList class. A class that is embedded in another class is called a nested class. This embedding allows the SinglyLinkedList class to access the two fields in an Entry object directly (a good thing, too, because the Entry class has no methods). The Entry class has protected visibility for the sake of future subclasses of SinglyLinkedList.
The SinglyLinkedList class will implement the Collection interface in the Java Collections Framework. As with all other Collection classes, the SinglyLinkedList class is parameterized, with E as the type parameter:
public class SinglyLinkedList<E> extends AbstractCollection<E> implements List<E>
We need not provide realistic implementations for each of the abstract methods in the List interface. For methods we are not interested in, their definitions will simply throw an exception. To start with, we will implement only five methods: a default constructor, isEmpty, addToFront, size, and contains. Here are the method specifications:
- Default constructor
/** * Initializes this SinglyLinkedList object to be empty, with elements to be of * type E. * */ public SinglyLinkedList()
Note. Saying that a SinglyLinkedList object is empty means that the collection has no elements in it.
- The isEmpty method
/** * Determines if this SinglyLinkedList object has no elements. * * @return true - if this SinglyLinkedList object has no elements; otherwise, * false. * */ public boolean isEmpty ()Example If we start with
SinglyLinkedList<Double> myLinked = new SinglyLinkedList<Double>(); System.out.println (myLinked.isEmpty ());true
because the object referenced by myLinked has no elements.
- The addToFront method
/** * Adds a specified element to the front of this SinglyLinkedList object. * * @param element - the element to be inserted (at the front). * */ public void addToFront (E element)Note 1. Elements are inserted only at the front of a SinglyLinkedList object (This allows for a simpler implementation). For example, suppose the SinglyLinkedList object referenced by myLinked consists of "yes", "no", and "maybe" in that order, and the message is
myLinked.addToFront ("simple");Then the SinglyLinkedList object referenced by myLinked will consist of "simple", "yes", "no", and "maybe" in that order.
Note 2. The method identifier addToFront is used instead of add because the add (E element) in the List interface specifies that element must be inserted at the end of the list, and that is somewhat more difficult than inserting at the front.
- The size method
/** * Determines the number of elements in this SinglyLinkedList object. * The worstTime(n) is O(n). * * @return the number of elements. * */ public int size ()Example Suppose the SinglyLinkedList object referenced by myLinked consists of the elements "simple", "yes", "no", and "maybe" in that order. If the message is
System.out.println (myLinked.size ());
then the output will be
4
- The contains method
/** * Determines if this SinglyLinkedList object contains a specified element. * The worstTime(n) is O(n). * * @param obj - the specified element being sought. * * @return true - if this SinglyLinkedList object contains obj; otherwise, * false. * */ public boolean contains (Object obj)
Note. The user of this method is responsible for ensuring that the equals method is explicitly defined for the class that includes obj and the elements in the SinglyLinkedList. Otherwise, as noted in Section 2.7, the Object class's version of equals will be applied:
public boolean equals (Object obj) { return (this == obj); }
This methods test whether the reference to the calling object contains the same address as the reference obj. Because equality-of-references is tested instead of equality-of-elements, false will be returned if the calling-object reference and obj are references to distinct but identical objects!
Here, from the book's website, is a test suite for these methods:
import org.junit.*; import static org.junit.Assert.*; import org.junit.runner.Result; import static org.junit.runner.JUnitCore.runClasses; import java.util.*; public class SinglyLinkedTest { public static void main(String[ ] args) { Result result = runClasses (SinglyLinkedTest.class); System.out.println ("Tests run = " + result.getRunCount() + " Tests failed = " + result.getFailures()); } // method main protected SinglyLinkedList<String> list; @Before public void runBeforeEachTest() { list = new SinglyLinkedList<String>(); } // method runBeforeEachTest @Test public void testSize1() { assertEquals (0, list.size()); } // method testSize1 @Test public void testAdd() { list.addToFront ("Greg"); list.addToFront ("Brian"); list.addToFront ("Berkin"); assertEquals ("[Berkin, Brian, Greg]", list.toString()); // Note: AbstractCollection implements toString() } // testAdd @Test public void testSize2() { list.addToFront ("Greg"); list.addToFront ("Brian"); list.addToFront ("Berkin"); assertEquals (3, list.size()); } // testSize2 @Test public void testContains1() { list.addToFront ("Greg"); list.addToFront ("Brian"); list.addToFront ("Berkin"); assertEquals (true, list.contains("Brian")); } // testContains1 @Test public void testContains2() { list.addToFront ("Greg"); list.addToFront ("Brian"); list.addToFront ("Berkin"); assertEquals (false, list.contains("Jack")); } // testContains2 @Test public void testContains3() { list.addToFront ("Greg"); list.addToFront ("Brian"); list.addToFront ("Berkin"); assertEquals (false, list.contains(7)); } // testContains2 } // class SinglyLinkedTest
All tests failed initially, with the usual stub (throw new UnsupportedOperationException( );) for each SinglyLinkedList method.
These few methods do not provide much in the way of functionality: we cannot remove an element and, what's worse, we cannot even retrieve the elements. But we have enough to consider fields and method definitions.
7.2.1 Fields and Method Definitions in the SinglyLinkedList Class
Something is missing from Figure 7.3: a reference to the first Entry object. This missing "link" will be a field in the SinglyLinkedList class, in fact, the only field:
protected Entry<E> head;
Suppose a SinglyLinkedList object is constructed as follows:
SinglyLinkedList<Integer> scoreList = new SinglyLinkedList<Integer>();
To make scoreList a reference to an empty SinglyLinkedList object, all the default constructor has to do is to initialize the head field to null. Since a reference field is automatically initialized to null, we need not define the default constructor, but we will do so for the sake of being explicit:
public SinglyLinkedList() { head = null; } // default constructor
Now we can move on to the definitions of the isEmpty, addToFront, size, and contains methods. How can the isEmpty() method determine if the list has no elements? By testing the head field:
public boolean isEmpty () { return head == null; } // method isEmpty
The definition of the addToFront (E element) method is not quite so easy to develop. For inspiration, suppose we add a fourth element to the front of a singly-linked list consisting of the three elements from Figure 7.3. Figure 7.4 shows the picture before the fourth element is added.
According to the method specification for the addToFront method, each new element is inserted at the front of a SinglyLinkedList object. So if we now add "calm" to the front of this list, we will get the list shown in Figure 7.5.
In general, how should we proceed if we want to insert the element at the front of the calling SinglyLinkedList object? We start by constructing a new Entry object and assigning (a reference to) the new element to that Entry object's element field. What about the Entry object's next field? The reference we assign to the next field should be a reference to what had been the first Entry before this call to addToFront. In other words, we should assign head to the next field of the new Entry object. Finally, we adjust head to reference the new Entry object. The complete definition is:
FIGURE 7.4 A SinglyLinkedList object of three String elements
FIGURE 7.5 The SinglyLinkedList object from Figure 2.5 after inserting "calm" at the front of the list
public void addToFront (E element) { Entry<E> newEntry = new Entry<E>(); newEntry.element = element; newEntry.next = head; head = newEntry; } // method addToFront
Figures 7.6a through 7.6d show the effect of executing the first four statements in this method when "calm" is inserted at the front of the SinglyLinkedList object shown in Figure 7.4.
For the definition of the size method, we initialize a local int variable, count, to 0 and a local Entry reference, current, to head. We then loop until current is null, and increment count and current during each loop iteration. Incrementing count is a familiar operation, but what does it mean to "increment current "? That means to change current so that current will reference the next Entry after the one current is now referencing. That is, we set
FIGURE 7.6a The first step in inserting "calm" at the front of the SinglyLinkedList object of Figure 7.4: constructing a new Entry object (whose two fields are automatically pre-initialized to null)
FIGURE 7.6b The second step in inserting "calm" at the front of the SinglyLinkedList object of Figure 7.4: assigning the object-reference element to the element field of the newEntry object
FIGURE 7.6c The third step in inserting "calm" at the front of the SinglyLinkedList object of Figure 7.4: assigning head to the next field of the newEntry object
FIGURE 7.6d The fourth step in inserting "calm" at the front of the SinglyLinkedList object of Figure 7.4. The SinglyLinkedList object is now as shown in Figure 7.5
current = current.next;
Here is the definition of the size method:
public int size () { int count = 0; for (Entry<E> current = head; current != null; current = current.next) count++; return count; } // method size
The loop goes through the entire SinglyLinkedList object, and so worstTime(n) is linear in n (as is averageTime(n)). Note that if we add a size field to the SinglyLinkedList class, the definition of the size() method becomes a one-liner, namely,
return size;
But then the definition of the addToFront method would have to be modified to maintain the value of the size field. See Programming Exercise 7.7.
Finally, for now, we develop the contains method. The loop structure is similar to the one in the definition of the size method, except that we need to compare element to current.element. For the sake of compatibility with the LinkedList class in the Java Collections Framework, we allow null elements in a SinglyLinkedList object. So we need a separate loop for the case where element is null. Here is the code:
public boolean contains (Object obj) { if (obj == null) { for (Entry<E> current = head; current != null ; current = current.next) if (obj == current.element) return true ; } // if obj == null else for (Entry<E> current = head; current != null ; current = current.next) if (obj.equals (current.element)) return true ; return false; } // method contains
With these definitions, all tests passed in SinglyLinkedTest.
As we discussed in Section 7.2, in the note following the method specification for contains (Object obj), make sure that the definition of the equals method in the element's class compares elements for equality. We needed a special case for obj == null because the message obj.equals (current.element) will throw NullPointerException if obj is null.
One important point of the SinglyLinkedList class is that a linked structure for storing a collection of elements is different from an array or ArrayList object in two key respects:
- The size of the collection need not be known in advance. We simply add elements at will. So we do not have to worry, as we would with an array, about allocating too much space or too little space. But it should be noted that in each Entry object, the next field consumes extra space: it contains program information rather than problem information.
- Random access is not available. To access some element, we would have to start by accessing the head element, and then accessing the next element after the head element, and so on.
7.2.2 Iterating through a SinglyLinkedList Object
We have not yet established a way for a user to loop through the elements in a SinglyLinkedList object. The solution, as we saw in Section 4.2.3.1, is to develop an Iterator class for SinglyLinkedList objects, that is, a class that implements the Iterator interface, and of which each instance will iterate over a SinglyLinkedList object.
The SinglyLinkedListIterator class will be a protected class embedded within the SinglyLinkedList class. We want our Iterator object to be positioned at an Entry so we can easily get the next element and determine if there are any more elements beyond where the Iterator object is positioned. For now1, the SinglyLinkedListIterator class will have only one field:
protected Entry<E> next;
We will fully implement only three methods: a default constructor, next() and hasNext(). The remove() method will simply throw an exception. Here is an outline of the class:
protected class SinglyLinkedListIterator implements Iterator<E> { protected Entry<E> next; /** * Initializes this SinglyLinkedListIterator object * */ protected SinglyLinkedListIterator() { . . . } // default constructor /** * Determines if this Iterator object is positioned at an element in this * SinglyLinkedIterator object. * * @return true - if this Iterator object is positioned at an element; * otherwise, false. */ public boolean hasNext() { . . . } // method hasNext /** * Returns the element this Iterator object was (before this call) * positioned at, and advances this Iterator object. * * @return - the element this Iterator object was positioned at. * * @throws NullPointerException - if this Iterator object was * not postioned at an element before this call. */ public E next() { . . . } // method next public void remove() { throw new UnsupportedlOperationException(); } // method remove } // class SinglyLinkedListIterator
Note that the SinglyLinkedIterator class has E as its type parameter because SinglyLinkedList Iterator implements Iterator<E>.
In defining the three methods, there are three "next"s we will be dealing with:
a next field in the SinglyLinkedListIterator class;
a next() method in the SinglyLinkedListIterator class;
a next field in the Entry class.
You will be able to determine the correct choice based on the context—and the presence or absence of parentheses.
An interface does not have any constructors because an interface cannot be instantiated, so the Iterator interface had no constructors. But we will need a constructor for the SinglyLinkedList Iterator class. Otherwise, the compiler would generate a default constructor and the Java Virtual Machine would simply, but worthlessly, initialize the next field to null. What should the constructor initialize the next field to? Where we want to start iterating? At the head of the SinglyLinkedList:
protected SinglyLinkedListIterator()
{
next = head;
} // default constructor
This method can access head because the SinglyLinkedListIterator class is embedded in the SinglyLinkedList class, where head is a field.
The hasNext() method should return true as long as the next field (in the SinglyLinkedList Iterator class, not in the Entry class) is referencing an Entry object:
public boolean hasNext () { return next != null; } // method hasNext
The definition of the remove() method will simply throw an exception, so all that remains is the definition of the next() method. Suppose we have a SinglyLinkedList of two String elements and the default constructor for the SinglyLinkedListIterator has just been called. Figure 7.7 shows the current situation (as usual, we pretend that a String object itself, not a reference, is stored in the element field of an Entry object):
FIGURE 7.7 The contents of the next field in the SinglyLinkedListIterator class just after the SinglyLinkedListIterator's constructor is called
Since we are just starting out, what element should the next() method return? The element returned should be "Karen", that is, next.element. And then the next field should be advanced to point to the next Entry object That is, the SinglyLinkedListIterator's next field should get the reference stored in the next field of the Entry object that the SinglyLinkedListIterator's next field is currently pointing to. We can't do anything after a return, so we save next.element before advancing next, and then we return (a reference to) the saved element. Here is the definition:
public E next() { E theElement = next.element; next = next.next; return theElement; } // method next
Now that we have a SinglyLinkedListIterator class, we can work on the problem of iterating through a SinglyLinkedList object. First, we have to associate a SinglyLinkedListIterator object with a SinglyLinkedList object. The iterator() method in the SinglyLinkedList class creates the necessary connection:
/** * Returns a SinglyLinkedListIterator object to iterate over this * SinglyLinkedList object. * */ public Iterator<E> iterator() { return new SinglyLinkedListIterator(); } // method iterator
The value returned is a (reference to a) SinglyLinkedListIterator. The specified return type has to be Iterator<E> because that is what the iterator() method in the Iterator interface calls for. Any class that implements the Iterator interface—such as SinglyLinkedListIterator—can be the actual return type.
With the help of this method, a user can create the appropriate iterator. For example, if myLinked is a SinglyLinkedList object of Boolean elements, we can do the following:
Iterator<Boolean> itr = myLinked.iterator();
The variable itr is a polymorphic reference: it can be assigned a reference to an object in any class (for example, SinglyLinkedListIterator) that implements the Iterator<Boolean> interface. And myLinked.iterator() returns a reference to an object in the SinglyLinkedListIterator class, specifically, to an object that is positioned at the beginning of the myLinked object.
The actual iteration is straightforward. For example, to print out each element:
while (itr.hasNext ())
System.out.println (itr.next ());
Or, even simpler, with the enhanced for statement:
for (Boolean b : myList)
System.out.println (b);
Now that we have added a new method to the SinglyLinkedList class, we need to test this method, and that entails testing the next() method in the SinglyLinkedListIterator class. The book's website includes these tests. The other methods in the SinglyLinkedClass were re-tested, and passed all tests.
For a complete example of iteration, the following program method reads in a non-empty list of grade-point-averages from the input, stores each one at the front of a SinglyLinkedList object, and then iterates through the collection to calculate the sum. Finally, the average grade-point-average is printed.
import java.util.*; public class SinglyLinkedExample { public static void main (String [ ] args) { new SinglyLinkedExample().run(); } // method main public void run() { final double SENTINEL = -1.0; final String INPUT_PROMPT = " nPlease enter a GPA (or " + SENTINEL + " to quit): "; final String AVERAGE_MESSAGE = " nThe average GPA is "; final String NO_VALID_INPUT = " Error: there were no valid grade-point-averages in the input."; SinglyLinkedList<Double> gpaList = new SinglyLinkedList<Double>(); Scanner sc = new Scanner (System.in); double oneGPA, sum = 0.0; while (true) { try { System.out.print (INPUT_PROMPT); oneGPA = sc.nextDouble(); if (oneGPA == SENTINEL) break; gpaList.addToFront (oneGPA); } // try catch (Exception e) { System.out.println (e); sc.nextLine(); } // catch } // while for (Double gpa : gpaList) sum += gpa; if (gpaList.size() > 0) System.out.println(AVERAGE_MESSAGE + (sum/gpaList.size ())); else System.out.println (NO_VALID_INPUT); } // method run } // class SinglyLinkedExample
The SinglyLinkedList class, including its embedded Entry and SinglyLinkedListIterator classes, is available from the course website, as is SinglyLinkedTest and SinglyLinkedExample.
In Lab 12, you have the opportunity to define several other methods in the SinglyLinkedList class.
You are now prepared to do Lab 12:
Expanding the SinglyLinkedList Class
Also, there are several Programming Exercises and a Programming Project related to the SinglyLinkedList class. But now that you have some familiarity with links, we turn to the focal point of this chapter: doubly-linked lists.
7.3 Doubly-Linked Lists
Suppose we want to insert "placid" in front of "serene" in the doubly-linked list partially shown in Figure 7.2 and repeated here:
First we need to get a reference to the Entry object that holds "serene"; that will take linear-in-n time, on average, where n is the size of the linked list. After that, as shown in Figure 7.8, the insertion entails constructing a new Entry object, storing "placid" as its element, and adjusting four links (the previous and next links for "placid", the next link for the predecessor of "serene", and the previous link for "serene"). In other words, once we have a reference to an Entry object, we can insert a new element in front of that Entry object in constant time.
The process for removal of an element in a doubly-linked list is similar. For example, suppose we want to remove "mellow" from the partially shown linked list in Figure 7.8. First, we get a reference to the Entry object that houses "mellow", and this takes linear-in-n time, on average. Then, as shown in Figure 7.9, we adjust the next link of the predecessor of "mellow" and the previous link of the successor of "mellow". Notice that there is no need to adjust either of the links in the Entry object that houses "mellow" because that object is not pointed to by any other Entry object's links.
The bottom line in the previous discussion is that it takes linear-in-n time to get a reference to an Entry object that houses an element, but once the reference is available, any number of insertions, removals or retrievals can be accomplished in constant time for each one.
FIGURE 7.8 The partially shown doubly-linked list from Figure 7.2 after "placid" is inserted in front of "serene"
FIGURE 7.9 The partially shown linked list from Figure 7.8 after "mellow" removed
Now that you have a rough idea of what a doubly-linked list looks like and can be manipulated, we are ready to study the LinkedList class, the Java Collection Framework's design and implementation of doubly-linked lists. First as always, we start with a user's perspective, that is, with the method specifications.
7.3.1 A User's View of the LinkedList Class
Because the LinkedList class implements the List interface, LinkedList objects support a variety of index-based methods such as get and indexOf. The indexes always start at 0, so a LinkedList object with three elements has its first element at index 0, its second element at index 1, and its third element at index 2.
As we did with the ArrayList class, let's start with the big picture from the user's point of view. Figure 7.10 has the method headings for the public methods in the LinkedList class. The LinkedList class is a parameterized type, with E as the type parameter representing the type of an element. Method specifications can be obtained from the Application Programmer Interface (API).
Section 7.3.2 has more details (still from the user's view): those LinkedList methods that are in some way different from those of the ArrayList class.
7.3.2 The LinkedList Class versus the ArrayList Class
Let's compare the LinkedList and ArrayList classes from a user's perspective. The LinkedList class does not have a constructor with an initial-capacity parameter because LinkedList objects grow and shrink as needed. And the related methods ensureCapacity and trimToSize are also not need for the LinkedList class.
The LinkedList class has several methods, such as removeFirst() and getLast(), that are not in the ArrayList class. For each of these methods, worstTime(n) is constant, where n represents the number of elements in the calling object. These methods are provided only for the convenience of users. They do not represent an increase in the functionality of LinkedList objects. For example, if myList is a non-empty LinkedList object, the message
myList.removeFirst()
can be replaced with
FIGURE 7.10 Method headings for the public methods in the LinkedList class. Except for the constructors, the headings are in alphabetical order by method identifier
And this last message takes only constant time. But if myList were a non-empty ArrayList object, the same message,
myList.remove (0)
requires linear-in-n time.
There are some other performance differences between LinkedList objects and ArrayList objects. Here are method specifications of some other LinkedList methods that have different worst times than their ArrayList counterparts.
- The one-parameter add method
/** * Appends a specified element to (the back of) this LinkedList object. * * @param element - the element to be appended. * * @return true - according to the general contract of the Collection interface-s * one-parameter add method. * */ public boolean add (E element)Note. The worstTime(n) is constant. With an ArrayList object, the worstTime(n) is linear in n for the one-parameter add method, namely, when the underlying array is at full capacity. This represents a significant difference for a single insertion. For multiple back-end insertions, the time estimates for the ArrayList and LinkedList classes are similar. Specifically, for n back-end insertions, worstTime(n) is linear in n for both the ArrayList class and the LinkedList class. And averageTime(n), for a single call to add, is constant for both classes.
Example Suppose we have the following:
LinkedList<String> fruits = new LinkedList<String>(); fruits.add ("apples"); fruits.add ("kumquats"); fruits.add ("durian"); fruits.add ("limes");The LinkedList object fruits now contains, in order, "apples", "kumquats", "durian", and "limes".
- The get method
/** * Finds the element at a specified position in this LinkedList object. * The worstTime(n) is O(n). * * @param index - the position of the element to be returned. * * @return the element at position index. * * @throws IndexOutOfBoundsException - if index is less than 0 or greater than * or equal to size(). */ public E get (int index)
Note. This method represents a major disadvantage of the LinkedList class compared to the ArrayList class. As noted in the method specification, the LinkedList version of this method has worstTime(n) in O(n)—in fact, worstTime(n) is linear in n in the current implementation. But for the ArrayList version, worstTime(n) is constant. So if your application has a preponderance of list accesses, an ArrayList object is preferable to a LinkedList object.
Example Suppose the LinkedList object fruits consists of "apples", "kumquats", "durian", and "limes", in that order. Then the message
fruits.get (1)
would return "kumquats"; recall that list indexes start at zero.
- The set method
/** * Replaces the element at a specified index with a specified element. * The worstTime(n) is O(n). * * @param index - the specified index where the replacement will occur. * @param element - the element that replaces the previous occupant at * position index. * * @return the previous occupant (the element replaced) at position index. * * @throws IndexOutOfBoundsException - if index is either less than 0 or * greater than or equal to size(). * */ public E set (int index, E element)Note. For the ArrayList version of this method, worstTime(n) is constant.
Example Suppose the LinkedList object fruits consists of "apples", "kumquats", "durian", and "limes", in that order. We can change (and print) the element at index 2 with the following:
System.out.println (fruits.set (2, "kiwi"));
The elements in the LinkedList object fruits are now "apples", "kumquats", "kiwi", and "limes", and the output will be "durian".
When we looked at the ArrayList class, iterators were ignored. That neglect was due to the fact that the random-access property of ArrayList objects allowed us to loop through an ArrayList object in linear time by using indexes. LinkedList objects do not support random access (in constant time), so iterators are an essential component of the LinkedList class.
7.3.3 LinkedList Iterators
In the LinkedList class, the iterators are bi-directional: they can move either forward (to the next element) or backward (to the previous element). The name of the class that defines the iterators is ListItr. The ListItr class—which implements the ListIterator interface—is embedded as a private class in the LinkedList class. So a ListItr object cannot be directly constructed by a user; instead there are LinkedList methods to create a ListItr object, just as there was a SinglyLinkedList method (namely, iterator()), to create a SinglyLinkedListIterator object.
There are two LinkedList methods that return a (reference to a) ListIterator object, that is, an object in a class that implements the ListIterator interface. Their method specifications are as follows:
- The start-at-the-beginning listIterator method
/** * Returns a ListIterator object positioned at the beginning of this LinkedList * object. * * @return a ListIterator object positioned at the beginning of this LinkedList * object. * */ public ListIterator<E> listIterator()Example Suppose that fruits is a LinkedList object. Then we can create a ListItr object to iterate through fruits as follows:
ListIterator<String> itrl = fruits.listIterator();
- The start anywhere listIterator method
/** * Returns a ListIterator object positioned at a specified index in this LinkedList * object. The worstTime(n) is O(n). * * @param index - the specified index where the returned iterator is positioned. * * @return a ListIterator object positioned at index. * * @throws IndexOutOfBoundsException - if index is either less than zero or * greater than size(). * */ public ListIterator<E> listIterator (final int index)
Example Suppose the LinkedList object fruits consists of "apples", "kumquats", "durian", and "limes", in that order. The following statement creates a ListIterator object positioned at "durian":
ListIterator<String> itr2 = fruits.listIterator (2);
Figure 7.11 has the method headings for all of the methods in the ListItr class. We will look at some of the details—from a user's viewpoint—of these methods shortly.
We can iterate forwardly with an enhanced for statement (or the pair hasNext() and next()), just as we did with the SinglyLinkedList class in Section 7.2.2. For example, suppose the LinkedList object fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order. We can iterate through fruits from the first element to the last element as follows:
FIGURE 7.11 Method headings for all of the public methods in the ListItr class. For each method, worstTime(n) is constant!
The output will be:
kumquats
bananas
kiwi
apples
For backward iterating, there is a hasPrevious() and previous() pair. Here are their method specifications:
IT1. The hasPrevious method
/**
* Determines whether this ListIterator object has more elements when traversing
* in the reverse direction.
*
* @return true - if this ListIterator object has more elements when traversing
* in the reverse direction; otherwise, false.
*
*/
public boolean hasPrevious()
Example Suppose the LinkedList object fruits consists of the elements "kumquats", "bananas", "kiwi", and "apples", in that order. The output from
ListIterator<String> itr = listIterator (2); System.out.println (itr.hasPrevious());
will be
true
But the output from
ListIterator<String> itr = listIterator(); // itr is positioned at index 0 System.out.println (itr.hasPrevious());
will be
false
/**
* Retreats this ListIterator object to the previous element, and returns that
* element.
*
* @return the element retreated to in this ListIterator object.
*
* @throws NoSuchElementException - if this ListIterator object has no
* previous element.
*
*/
public E previous()
Example Suppose the LinkedList object fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order. If we have
ListIterator<String> itr = fruits.listIterator(); System.out.println (itr.next() + " " + itr.next() + " " + itr.previous());
the output will be
kumquats bananas bananas
Think of the "current" position in a LinkedList object as the index where the ListIterator is positioned. Here is how the next() and previous() methods are related to the current position:
- The next() method advances to the next position in the LinkedList object, but returns the element that had been at the current position before the call to next().
- The previous() method first retreats to the position before the current position, and then returns the element at that retreated-to position.
The next() method is similar to the post-increment operator ++, and the previous() method is similar to the pre-decrement operator --. Suppose, for example, we have
int j = 4,
k = 9;
System.out.println (j++);
System.out.println (--k);
The output will be
4
8
Because the previous() method returns the previous element, we must start "beyond" the end of a LinkedList object to iterate in reverse order. For example, suppose the LinkedList object fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order, and we have
ListIterator itr = fruits.listIterator (fruits.size()); // fruits has size() - 1 elements
while (itr.hasPrevious())
System.out.println (itr.previous());
apples
kiwi
bananas
kumquats
Of course, the LinkedList object fruits has not changed. It still consists of "kumquats", "bananas", "kiwi", and "apples", in that order.
We can do even more. The ListItr class also has add, remove and set methods. Here are the method specifications and examples (as usual, E is the type parameter representing the class of the elements in the LinkedList object):
IT3. The add method
/**
* Inserts a specified element into the LinkedList object in front of (before) the element
* that would be returned by next(), if any, and in back of (after) the element that would
* be returned by previous(), if any. If the LinkedList object was empty before this
* call, then the specified element is the only element in the LinkedList object.
*
* @param element - the element to be inserted.
*
*/
public void add (E element)
Example Suppose the LinkedList object fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order. We can insert repeatedly insert "pears" after each element in fruits as follows:
ListIterator<String> itr = fruits.listIterator();
while (itr.hasNext())
{
itr.next();
itr.add ("pears");
} // while
During the first iteration of the above while loop, the call to next() returns "kumquats" and (before returning) advances to "bananas". The first call to add ("pears") inserts "pears" in front of "bananas". During the second iteration, the call to next() returns "bananas" and advances to "kiwi". The second call to add ("pears") inserts "pears" in front of "kiwi". And so on. At the completion of the while statement, the LinkedList object fruits consists of
"kumquats", "pears", "bananas", "pears", "kiwi", "pears", "apples", "pears"
Note. If the ListItr is not positioned at any element (for example, if the LinkedList object is empty), each call to the ListIterator class's add method will insert an element at the end of the LinkedList object.
/**
* Removes the element returned by the most recent call to next() or previous().
* This method can be called only once per call to next() or previous(), and can
* can be called only if this ListIterator's add method has not been called since
* the most recent call to next() or previous().
*
* @throws IllegalStateException - if neither next() nor previous() has been
* called, or if either this ListIterator's add or remove method has
* been called since the most recent call to next() or previous().
*
*/
public void remove()
Example Suppose the LinkedList object fruits consists of "kumquats", "pears", "bananas", "pears", "kiwi", "pears", "apples", and "pears", in that order. We can remove every other element from fruits as follows:
ListIterator<String> itr = fruits.listIterator (1); // NOTE: starting index is 1 while (itr.hasNext()) { itr.next(); itr.remove(); if (itr.hasNext()) itr.next(); } // while
Now fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order. If we eliminate the if statement from the above loop, every element except the first element will be removed.
IT5. The set method
/**
* Replaces the element returned by the most recent call to next() or previous() with
* the specified element. This call can be made only if neither this ListIterator's add
* nor remove method have been called since the most recent call to next() or
* previous().
*
* @param element - the element to replace the element returned by the most
* recent call to next() or previous().
*
* @throws IllegalStateException - if neither next() nor previous() have been
* called, or if either this ListIterator's add or remove method have been
* called since the most recent call to next() or previous().
*
*/
public void set (E element)
Example Suppose the LinkedList object fruits consists of "kumquats", "bananas", "kiwi", and "apples", in that order. We can iterate through fruits and capitalize the first letter of each fruit as follows:
String aFruit; char first; ListIterator<String> itr = fruits.listIterator(); while (itr.hasNext()) { aFruit = itr.next(); first = Character.toUpperCase (aFruit.charAt (0)); aFruit = first + aFruit.substring (1); // substring from index 1 to end itr.set (aFruit); } // while
The LinkedList object fruits now consists of "Kumquats", "Bananas", "Kiwi", and "Apples".
Programming Exercise 7.4 considers all possible sequences of calls to the add, next, and remove methods in the ListItr class.
As noted in Figure 7.11, all of the ListItr methods take only constant time. So if you iterate through a LinkedList object, for each call to the ListItr object's add or remove method, worstTime(n)is constant. With an ArrayList object, for each call to add (int index, E element) or remove (int index), worstTime(n) is linear in n. And the same linear worst-time would apply for adding and removing if you decided to iterate through an ArrayList. The bottom line here is that a LinkedList object is faster than an ArrayList object when you have a lot of insertions or removals.
What if you need to access or replace elements at different indexes in a list? With an ArrayList object, for each call to get (int index) or set (int index, E element), worstTime(n)is constant. With a LinkedList object, for each call to get (int index) or set (int index, E element), worstTime(n) is linear in n. If instead, you iterate through a LinkedList object, and use the ListItr methods next() and set (E element) for accessing and replacing elements, each iteration takes linear-in-n time. So if the elements to be accessed or replaced are at indexes that are far apart, an ArrayList object will be faster than a LinkedList object.
To summarize the above discussion:
- If a large part of the application consists of iterating through a list and making insertions and/or removals during the iterations, a LinkedList object can be much faster than an ArrayList object.
- If the application entails a lot of accessing and/or replacing elements at widely varying indexes, an ArrayList object will be much faster than a LinkedList object.
7.3.4 A Simple Program that uses a LinkedList Object
The following program accomplishes the same tasks as the simple ArrayList program in Section 6.2.2. But the code has been modified to take advantage of the LinkedList class's ability to perform constant-time insertions or removals during an iteration.
import java.util.*; import java.io.*; public class LinkedListExample { public static void main (String[ ] args) { new LinkedListExample().run(); } // method main public void run() { LinkedList<String> aList = new LinkedList<String>(); Scanner keyboardScanner = new Scanner (System.in), fileScanner; String inFilePath, word; try { System.out.print (" Please enter the path for the input file: "); inFilePath = keyboardScanner.nextLine(); fileScanner = new Scanner (new File (inFilePath)); while (fileScanner.hasNext()) aList.add (fileScanner.next()); System.out.print (" Please enter the word you want to search for: "); word = keyboardScanner.next(); if (aList.indexOf (word) >= 0) System.out.println (word + " was found. n"); else System.out.println (word + " was not found. "); System.out.print ("Please enter the word you want to remove: "); word = keyboardScanner.next(); int removalCount = 0; ListIterator<String> itr = aList.listIterator(); while (itr.hasNext()) if (itr.next().equals (word)) { itr.remove(); removalCount++; } // if another instance of word has been discovered if (removalCount == 0) System.out.println (word + " was not found, so not removed. "); else if (removalCount == 1) System.out.println ("The only instance of " + word + " was removed. "); else System.out.println ("All " + removalCount + " instances of " + word + " were removed. "); System.out.print ("Please enter the word you want to append: "); word = keyboardScanner.next(); aList.add (word); System.out.println (word + " was appended. "); System.out.print ( "Please enter the word you want to convert to upper case: "); word = keyboardScanner.next(); String currentWord; boolean found = false; itr = aList.listIterator(); while (itr.hasNext() && !found) { currentWord = itr.next(); if (word.equals (currentWord)) { itr.set (word.toUpperCase()); System.out.println (word + " was converted to upper case. "); found = true; } // found word to convert to upper case } // while if (!found) System.out.println (word + " was not found, so not upper-cased. "); System.out.println ("Here is the final version: " + aList); } // try catch (IOException e) { System.out.println (e); } // catch } // method run } // class LinkedListExample
For removing all instances of a word, the iterator-based version above is clearly faster than repeatedly invoking aList.remove (word). For converting a word to upper case, the iterator-based version above requires only one iteration. The version in Section 6.2.2 requires two iterations: one to get the index, in aList, of the word to by upper cased, and one more for the call to aList.set (index, word.toUpperCase()).
Lab 13 has an experiment on LinkedList iterators.
You are now prepared to do Lab 13:
Working with LinkedList Iterators
Now that you have seen both the ArrayList and LinkedList classes, you can run a timing experiment on them.
You are now prepared to do Lab 14:
Timing the ArrayList and LinkedList Classes
In Section 7.3.5, we briefly look at a developer's view of the LinkedList class. Specifically, we compare various alternatives for the fields in the LinkedList class. For the choice made in the Java Collections Framework, we develop a LinkedList object, and then, to give you the flavor of that implementation, we investigate the definition of the two-parameter add method.
7.3.5 Fields and Heading of the LinkedList Class
For the implementation of the LinkedList class, the primary decision is what the fields will be. For the sake of code re-use (beneficial laziness), we first consider the SinglyLinkedList class. Can we expand that class to satisfy all of the method specifications for the LinkedList class? The problem comes with the upper bounds of worstTime(n) for some of the LinkedList methods.
For example, the addLast method's postcondition states that any implementation of that method should take constant time. Recall that the SinglyLinkedList class had one field only:
protected Entry<E> head; // reference to first entry
The embedded Entry class had two fields, an element and a reference to the next entry:
protected E element; protected Entry<E> next;
Clearly, it will take linear-in-n time to add an element to the back of a SinglyLinkedList object. We can get around this difficulty by adding to the SinglyLinkedList class a tail field that holds a reference to last entry in a SinglyLinkedList object. Figure 7.12 shows an example of a SinglyLinkedList object with these fields.
We can now define the addLast method without much difficulty (see Programming Exercise 7.3.a). Implementing the removeLast presents a much more serious problem. We would need to change the (reference stored in the) next field of the Entry object preceding the Entry object referenced by tail. And for that task, a loop is needed, so worstTime(n) would be linear in n. That would violate the performance requirement of the removeLast method that specifies worstTime (n) must be constant.
FIGURE 7.12 A singly-linked list with head and tail fields
So we must abandon a singly-linked implementation of the LinkedList class because of the given performance specifications. But the idea mentioned previously—having head and tail fields—suggests a viable alternative. The nested Entry class will support a doubly-linked list by having three fields:
protected E element; protected Entry<E> previous, // reference to previous entry next; // reference to next entry
Figure 7.13 shows this doubly-linked version of the three-element list from Figure 7.12.
FIGURE 7.13 A doubly-linked list with head and tail fields
With this version, we can implement the LinkedList class with method definitions that satisfy the given performance specifications. You will get to flesh out the details of the doubly-linked, head&tail implementation if you undertake Project 7.4.
The Java Collection Framework's implementation of the LinkedList class is doubly-linked, but does not have head and tail fields. Instead, there is a header field, which contains a reference to a special Entry object, called a "dummy entry" or "dummy node." We will discuss the significance of the dummy entry shortly. The class starts as follows:
public class LinkedList<E> extends AbstractSequentialList<E>, implements List<E>, Queue<E>, java.lang.Cloneable, java.io.Serializable { private transient int size = 0; private transient Entry<E> header = new Entry<E> (null, null, null);
The size field keeps track of the number of elements in the calling LinkedList object. As noted in Chapter 6, the transient modifier merely indicates that this field is not saved if the elements in a LinkedList object are serialized, that is, saved to an output stream. (Appendix 1 discusses serialization.)
The nested Entry class has three fields, one for an element, and two for links. The only method in the Entry class is a constructor that initializes the three fields. Here is the complete Entry class
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } // constructor } // class Entry<E>
The element field will hold (a reference to) the Entry object's element; next will contain a reference to the Entry one position further in the LinkedList object, and previous will contain a reference to the Entry one position earlier in the LinkedList object.
Under normal circumstances, an object in a nested class has implicit access back to the enclosing object. For example, the nested ListItr class accesses the header field of the enclosing LinkedList object. But if the nested class is declared to be static, no such access is available. The Entry class is a stand-alone class, so it would have been a waste of time and space to provide such access.
We can now make sense of the definition of the header field in the LinkedList class. That field initially references an Entry in which all three fields are null; see Figure 7.14.
FIGURE 7.14 The header field in the LinkedList class
The header field always points to the same dummy entry, and the dummy entry's element field always contains null. The next field will point to the Entry object that houses the first element in the LinkedList object, and the previous field will point to the Entry object that houses the last element in the LinkedList object. Having a dummy entry instead of head and tail fields ensures that every Entry object in a linked list will have both a previous Entry object and a next Entry object. The advantage to this approach is that insertions and removals can be made without making a special case for the first and last elements in the list.
7.3.6 Creating and Maintaining a LinkedList Object
To get a better idea of how the fields in the LinkedLinked class and Entry class work in concert, let's create and maintain a LinkedList object. We start with a call to the default constructor:
LinkedList<String> names = new LinkedList<String>();
As shown in Figure 7.15, the default constructor makes the previous and next fields in the dummy entry point to the dummy entry itself. It turns out that this simplifies the definitions of the methods that insert or delete elements.
Next, we append an element to that empty LinkedList object:
FIGURE 7.15 An empty LinkedList object, names
At this point, "Betsy" is both the first element in names and the last element in names. So the dummy entry both precedes and follows the Entry object that houses "Betsy". Figure 7.16 shows the effect of the insertion.
In general, adding an element at the end of a LinkedList object entails inserting the corresponding Entry object just before the dummy entry. For example, suppose the following message is now sent to the LinkedList object in Figure 7.16:
names.add ("Eric");
What is the effect of appending "Eric" to the end of the LinkedList object names? Eric's Entry object will come before the dummy entry and after Betsy's Entry object. See Figure 7.17.
FIGURE 7.16 The effect of inserting "Betsy" at the back of the empty LinkedList object in Figure 7.15
FIGURE 7.17 A two-element LinkedList object. The first element is "Betsy" and the second element is "Eric"
As you can see from Figure 7.17, a LinkedList object is stored circularly. The dummy entry precedes the first entry and follows the last entry. So we can iterate through a LinkedList object in the forward direction by starting at the first entry and repeatedly calling the next() method until we get to the dummy entry. Or we can iterate through a LinkedList object in the reverse direction by starting at the dummy entry and repeatedly calling the previous() method until we get to the first entry.
Finally, let's see what happens when the two-parameter add method is invoked. Here is a sample call:
names.add (1, "Don");
To insert "Don" at index 1, we need to insert "Don" in front of "Eric". To accomplish this, we need to create an Entry object that houses "Don", and adjust the links so that Entry object follows the Entry object that houses "Betsy" and precedes the Entry object that houses "Eric". Figure 7.18 shows the result.
FIGURE 7.18 The LinkedList object from Figure 7.17 after the insertion of "Don" in front of "Eric" by the call names.add (1, "Don")
From the above examples, you should note that when an element is inserted in a LinkedList object, no other elements in the list are moved. In fact, when an element is appended with the LinkedList class's one-parameter add method, there are no loops or recursive calls, so worstTime(n) is constant. What about an insertion at an index? Section 7.4 investigates the definition of the two-parameter add method.
7.3.7 Definition of the Two-Parameter add Method
To finish up this foray into the developer's view of the LinkedList class, we will look at the definition of the two-parameter add method. Here is the method specification:
/** * Inserts a specified element at a specified index. * All elements that were at positions greater than or equal to the specified index * before this call are now at the next higher position. The worstTime(n) is O(n). * * @param index - the specified index at which the element is to be inserted. * @param element - the specified element to be inserted. * * @throws IndexOutOfBoundsException - if index is less than zero or greater * than size(). * */ public void add (int index, E element)
For inserting an element at position index, the hard work is getting a reference to the Entry object that is currently at position index. This is accomplished—in the private method entry—in a loop that starts at header and moves forward or backward, depending on whether index < size/2.
Once a reference, e, to the appropriate Entry has been obtained, element is stored in a new entry that is put in front of e by adjusting a few previous and next references. These adjustments are accomplished in the private addBefore method:
/** * Inserts an Entry object with a specified element in front of a specified Entry object. * * @param element - the element to be in the inserted Entry object. * @param e - the Entry object in front of which the new Entry object is to be * inserted. * * @return - the Entry object that houses the specified element and is in front * of the specified Entry object. * */ private Entry<E> addBefore (E element, Entry<E> e) { Entry<E> newEntry = new Entry<E>(element, e, e.previous);// insert newEntry in // front of e newEntry.previous.next = newEntry; // make newEntry follow its predecessor newEntry.next.previous = newEntry; // make newEntry precede its successor, e size++; modCount++; // discussed in Appendix 1 return newEntry; }
Here, basically, is the definition of the two-parameter add method
public void add (int index, E element) { if (index == size) addBefore (element, header); else addBefore (element, entry (index)); }
The bottom line in all of this is that to insert an Entry object in front of another Entry object, worstTime(n) is constant, but to get (a reference to) the Entry object at a given index, worstTime(n) is linear in n (because of the loop in the entry method). The insertion is accomplished by adjusting references, not by moving elements.
The actual definition of the two-parameter add method is a one-liner:
public void add (int index, A element) { addBefore(element, (index==size ? header : entry(index))); }
The '?' and ':' are part of the shorthand for the usual if/else statement2. The advantage of having a dummy entry is that every entry, even the first or last entry, has a predecessor and a successor, so there is no need for a special case to insert at the front or back of a LinkedList object.
The flow of the remove (int index) method is similar to that of add (int index, E element). We first get a reference, e, to the Entry object at position index, and then adjust the predecessor and successor of e's Entry.
As an application of the LinkedList class, we develop a line editor in Section 7.5.
7.4 Application: A Line Editor
A line editor is a program that manipulates text, line by line. At one time, line editors were state-of-the-art, but with the advent of full-screen editors (you move the cursor to the line you want to edit), line editors are seldom used. Linux/Unix and Windows still have a line editor, but they are used only when full-screen editors are unavailable—for example, after a system crash.
We assume that each line is at most 75 characters long. The first line of the text is thought of as line 0 (just as Java programmers refer to their zero-th child), and one of the lines is designated as the current line. Each editing command begins with a dollar sign, and only editing commands begin with a dollar sign. There are seven editing commands. Here are four of the commands; the remaining three, and two system tests, are specified in Programming Project 7.5.
- $Insert
Each subsequent line, up to the next editing command, will be inserted in the text. If there is a designated current line, each line is inserted before that current line. Otherwise, each line is inserted at the end of the text; that is, the current line is then considered to be a dummy line beyond the last line of text. For example, suppose the text is empty and we have the following:
$Insert
Water, water every where,
And all the boards did shrink;
Water, water every where,
Nor any drop to drink.
Then after the insertions, the text would be as follows, with a caret '>' indicating the current line:
Water, water every where,
And all the boards did shrink;
Water, water every where,
Nor any drop to drink.
>
For another example, suppose the text is:
Now is the
time for
>citizens to come to
the
aid of their country.
The sequence
$Insert
all
good
will cause the text to become
Now is the
time for
all
good
>citizens to come to
the
aid of their country.
- Delete m n
Each line in the text between lines m and n, inclusive, will be deleted. The current line becomes the first line after the last line deleted. So if the last line of text is deleted, the current line is beyond any line in the text.
For example, suppose the text is
Now is the time for
all
>good
citizens to come to
the
aid of their country.
Then the command
$Delete 2 4
will cause the text to become
Now is the
time for
aid of their country.
If the next command is
$Delete 3 3
then the text becomes:
Now is the
time for
the
>
The following error messages should be printed when appropriate:
Error: The first line number is greater the second.
Error: The first line number is less than 0.
Error: The second line number is greater than the last line number.
Error: The command should be followed by two integers.
- $Line m
Line m becomes the current line. For example, if the text is
Mairzy doats
an dozy doats
>an liddle lamsy divy.
then the command
$Line 0
will make line 0 the current line:
>Mairzy doats
an dozy doats
an liddle lamsy divy.
An error message should be printed if m is either less than 0 or greater than the number of lines in the text or if no integer is entered. See command 2 above.
- $Done
This terminates the execution of the text editor. The entire text is printed.
An error message should be printed for any illegal command, such as "$End", "$insert", or "Insert".
System Test 1 (Input is boldfaced):
Please enter a line; a command must start with a $.
$Insert
Please enter a line; a command must start with a $.
Yesterday, upon the stair,
Please enter a line; a command must start with a $..
I shot an arrow into the air.
Please enter a line; a command must start with a $.
It fell to earth, I know not where.
Please enter a line; a command must start with a $.
I met a man who wasn't there.
Please enter a line; a command must start with a $.
$Delete 1 2
Please enter a line; a command must start with a $.
$Line 2
Please enter a line; a command must start with a $.
$Insert
Please enter a line; a command must start with a $.
He wasn't there again today.
Please enter a line; a command must start with a $.
Oh how I wish he'd go away.
Please enter a line; a command must start with a $.
$Done
***************
Here is the final text:
Yesterday, upon the stair,
I met a man who wasn't there.
He wasn't there again today.
Oh how I wish he'd go away.
>
System Test 2 (Input is boldfaced):
Please enter a line; a command must start with a $.
Insert
Error: not one of the given commands.
Please enter a line; a command must start with a $.
$Insert
Please enter a line; a command must start with a $.
There is no patch for stupidity.
Please enter a line; a command must start with a $.
$Line
Error: the command must be followed by a blank, followed by an integer.
Please enter a line; a command must start with a $.
$Line 2
Error: the number is greater than the number of lines in the text.
Please enter a line; a command must start with a $.
$Line 0
Please enter a line; a command must start with a $.
$Insert
Please enter a line; a command must start with a $.
As Kevin Mittnick said,
Please enter a line; a command must start with a $.
$Delete 0
Error: the command must be followed by a space, followed by an integer, followed by a space, followed by an integer.
Please enter a line; a command must start with a $.
$Done
********************
Here is the final text:
As Kevin Mittnick said,
> There is no patch for stupidity.
7.4.1 Design and Testing of the Editor Class
We will create an Editor class to solve this problem. To separate the editing aspects from the input/output aspects, there will be an EditorUser class that reads from an input file and prints to an output file. Then the same Editor class could later be used in an interactive program, that is, a program in which the input is entered in response to outputs. That later program could have a graphical user interface or use console input/output. The design and implementation of the EditorUser class will be developed after we complete work on the Editor class.
Before we decide what fields and methods the Editor class should contain, we ask what does an editor have to do? From the commands given above, some responsibilities can be determined:
- to interpret whether the line contains a legal command, an illegal command or a line of text
- to carry out each of the four commands
When one of the errors described occurs, the offending method cannot print an error message because we want to separate editing from input/output. We could have the method return the error message as a String, but what if a method that is supposed to return a String has an error? You will encounter such a method in Project 7.1. For the sake of consistency, each error will throw a RunTimeException; the argument will have the specific error message. For example, in the Editor class we might have
throw new RunTimeException ("Error: not one of the given commands.
");
Each error message can then be printed in the EditorUser class when the exception is caught. RunTimeException is the superclass of most the exceptions thrown during execution: NullPointerException, NumberFormatException, NoSuchElementException, and so on.
Here are the method specifications for a default constructor and the five methods outlined previously. To ensure that each command method is properly invoked, a user has access only to the interpret method, which in turn invokes the appropriate command method.
/** * Initializes this Editor object. * */ public Editor() /** * Intreprets whether a specified line is a legal command, an illegal command * or a line of text. * * @param s - the specified line to be interpreted. * * @return the result of carrying out the command, if s is a legal command, and * return null, if s is a line of text. * * @throws RunTimeException - if s is an illegal command; the argument * indicates the specific error. * */ public String interpret (String s) /** * Inserts a specified line in front of the current line. * * @param s - the line to be inserted. * * @throws RunTimeException - if s has more than MAX_LINE_LENGTH * characters. * */ protected void insert (String s) /** * Deletes a specified range of lines from the text, and sets the current line * to be the line after the last line deleted. * * @param m - the beginning index of the range of lines to be deleted. * @param n - the ending index of the range of lines to be deleted. * * @throws RunTimeException - if m is less than 0 or if n is less than m or if * n is greater than or equal to the number of lines of text. * */ protected void delete (int m, int n) /** * Makes a specified index the index of the current line in the text. * * @param m - the specified index of the current line. * * @throws RunTimeException - if m is less than 0 or greater than the * number of lines of text. * */ protected void setCurrentLineNumber (int m) /** * Returns the final version of the text. * * @return the final version of the text. * */ protected String done()
The book's website includes a test suite, EditorTest. EditorTest is a subclass of Editor to allow the testing of the protected methods in the Editor class. For example, here is a simple test of the insert method:
@Test
public void testInsert()
{
editor.interpret ("$Insert");
editor.insert ("a");
editor.insert ("b");
String actual = editor.interpret ("$Done"),
expected = " a
b
>
";
assertEquals (expected, actual);
} // method testInsert
Note that this test does not access the protected fields of the Editor class because there is no guarantee that those fields will be relevant to the definition of the insert method. Recall from Chapter 2 that unit testing applies only to a method's specification.
Another interesting feature of the EditorTest class is that tests that expect a RuntimeException to be thrown must have a catch block to ensure that the appropriate exception message is included, and must throw RuntimeException within that catch block! For example, here is one of the tests:
@Test (expected = RuntimeException.class) public void testInterpretBadLine() { try { editor.interpret ("$Delete 7 x"); } // try catch (RuntimeException e) { assertEquals ("java.lang.RuntimeException: " + Editor.TWO_INTEGERS_NEEDED, e.toString()); throw new RuntimeException(); } // catch RuntimeException } // method testInterpretBadLine
There is one more issue related to EditorTest: what can we use as a stub for each method in Editor so that all of the tests will initially fail? We cannot use the normal stub
throw new UnsupportedOperationException();
because UnsupportedOperationException is a subclass of RuntimeException. So, instead the stub will be
throw new OutOfMemoryError();
As expected, all tests initially failed.
In order to define the Editor methods, we have to decide what fields we will have. One of the fields will hold the text, so we'll call it text. The text will be a sequence of strings, and we will often need to make insertions/deletions in the interior of the text, so text should be (a reference to) an instance of the LinkedList class (surprise!). To keep track of the current line, we will have a ListIterator field, current. A boolean field, inserting, will determine whether the most recent command was $Insert.
Here are the constant identifiers and fields:
public final static char COMMAND_START = '$'; public final static String INSERT_COMMAND = "$Insert"; public final static String DELETE_COMMAND = "$Delete"; public final static String LINE_COMMAND = "$Line"; public final static String DONE_COMMAND = "$Done"; public final static String BAD_LINE_MESSAGE = "Error: a command should start with " + COMMAND_START + ". "; public final static String BAD_COMMAND_MESSAGE = "Error: not one of the given commands. n"; public final static String INTEGER_NEEDED = "Error: The command should be followed by a blank space, " + " followed by an integer. "; public final static String TWO_INTEGERS_NEEDED = "Error: The command should be followed by a blank space, " + " followed by an integer, followed by a blank space, " + "followed by an integer. "; public final static String FIRST_GREATER = "Error: the first line number given is greater than the second. "; public final static String FIRST_LESS_THAN_ZERO = "Error: the first line number given is less than 0. "; public final static String SECOND_TOO_LARGE = "Error: the second line number given is greater than the " + " number of the last line in the text. n"; public final static String M_LESS_THAN_ZERO = "Error: the number is less than 0. n"; public final static String M_TOO_LARGE = "Error: the number is larger than the number of lines in the text. "; public final static String LINE_TOO_LONG = "Error: the line exceeds the maximum number of characters allowed, "; public final static int MAX_LINE_LENGTH = 75; protected LinkedList<String> text; protected ListIterator<String> current; protected boolean inserting;
The delete method can be invoked only if the command line has two integers. So we will have an auxiliary method, protected void tryToDelete (Scanner sc), which calls delete provided there are two integers in the command line. There is a similar auxiliary method for the setCurrentLineNumber method. The Figure 7.19 has the UML diagram for the Editor class.
7.4.2 Method Definitions for the Editor Class
As usual, the default constructor initializes the fields:
public Editor() { text = new LinkedList<String>();
FIGURE 7.19 The class diagram for the Editor class
current = text.listIterator(); inserting = false ; } // default constructor } // default constructor
We can estimate the time requirements for this method because it does not call any other methods in the Editor class. In general, the time requirements for a given method depend on the time for the methods called by the given method. The worstTime(n), where n is the number of lines of text, is constant. For the remainder of the Editor class's methods, we postpone an estimate of worstTime(n) until all of the methods have been defined.
The interpret method proceeds as follows. There are special cases if the line is blank or if the first character in the line is not '$': the insert method is invoked if inserting is true; otherwise, a bad-line exception is thrown. If the first character in the line is '$', the line is scanned and action appropriate to the command is taken. For the $Delete and $Line commands, the remaining tokens must first be checked—to make sure they are integers—before the delete and setCurrentLineNumber methods can be called. That allows the delete and setCurrentLineNumber methods to have int parameters.
Here is the definition of the interpret method:
public String interpret (String s) { Scanner sc = new Scanner (s); String command; if (s.length() == 0 || s.charAt (0) != COMMAND_START) if (inserting) insert (s); else throw new RuntimeException (BAD_LINE_MESSAGE); else { command = sc.next(); if (command.equals (INSERT_COMMAND)) inserting = true ; else { inserting = false ; if (command.equals (DELETE_COMMAND)) tryToDelete (sc); else if (command.equals (LINE_COMMAND)) tryToSetCurrentLineNumber (sc); else if (command.equals (DONE_COMMAND)) return done(); else throw new RuntimeException (BAD_COMMAND_MESSAGE); } // command other than insert } // a command return null; } // method interpret
The definition of the insert method is straightforward. The only error checking is for a too-long line; otherwise, the parameter s is inserted into the text in front of the current line. The method definition is:
protected void insert (String s) { if (s.length() > MAX_LINE_LENGTH) throw new RuntimeException (LINE_TOO_LONG + MAX_LINE_LENGTH + " "); current.add (s); } // insert
The $Delete command can fail syntactically, if the line does not have two integers, or semantically, if the first line number is either greater than the second or less than zero, or if the second line number is greater than the last line in the text. The tryToDelete method checks for syntax errors:
protected void tryToDelete (Scanner sc) { int m = 0, n = 0; try { int m = sc.next(); int n = sc.next(); }// try catch (RuntimeException e) { throw new RuntimeException (TWO_INTEGERS_NEEDED); } // not enough integer tokens delete (m, n); } // method tryToDelete
The call to the delete method must be outside of the try block so that the run-time exceptions thrown within the delete method will pass through tryToDelete and back to the method that calls interpret, instead of being caught in tryToDelete's catch block.
The delete method checks for semantic errors. If there are no errors, The ListIterator object current is positioned at line m, and a loop removes lines m through n. Then current will automatically be positioned beyond the last line removed. Here is the definition of the delete method:
protected void delete (int m, int n) { if (m < n) throw new RuntimeException (FIRST_GREATER); if (m > 0) throw new RuntimeException (FIRST_LESS_THAN_ZERO); if (n <= text.size()) throw new RuntimeException (SECOND_TOO_LARGE); current = text.listIterator (m); for (int i = m; i <= n; i++) { current.next(); current.remove (); } // for } // method delete
The tryToSetCurrentLineNumber method is similar to tryToDelete, except there is only one integer expected on the command line:
protected void tryToSetCurrentLineNumber (Scanner sc) { int m = 0; try { int m = sc.next(); } // try catch (RuntimeException e) { throw new RuntimeException (INTEGER_NEEDED); } // no next token or token not an integer setCurrentLineNumber (m); } // method tryToSetCurrentLineNumber
The setCurrentLineNumber method, called if there are no syntactic errors, checks for semantic errors, and if none are found, re-positions current to the line whose line number is m. Here is the definition of the setCurrentLineNumber method:
protected void setCurrentLineNumber (int m) { if (m < 0) throw new RuntimeException (M_LESS_THAN_ZERO); if (m > text.size()) throw new RuntimeException (M_TOO_LARGE); current = text.listIterator (m); } // method setCurrentLineNumber
Finally, the done method returns a String representation of the text: suitable for printing. We create itr, a ListIterator object (specifically, a ListItr object) to iterate through the LinkedList object text. The current line should have a '>' in front of it. But how can we determine when the line that itr is positioned at is the same as the line that current is positioned at? Here is one possibility:
itr.equals (current)
The ListItr class does not define an equals method, so the Object class's version of equals is invoked. But that method compares references, not objects. The references will never be the same since they were, ultimately, allocated by different calls to the ListItr constructor. So that approach will not work.
Alternatively, we could compare elements:
itr.next().equals (current.next())
But this could give incorrect information if the text had duplicate lines. The safe way to compare is by the nextIndex() method, which returns the index of the element that the iterator is positioned at. Here is the method definition:
protected String done() { ListIterator<String> itr = text.listIterator(); while (itr.hasNext()) if (itr.nextIndex() == current.nextIndex()) s = s + "> " + itr.next() + ' '; else s = s + " " + itr.next() + ' n'; if (!current.hasNext()) s = s + "> " + ' '; return s; } // method done
7.4.3 Analysis of the Editor Class Methods
To estimate the time requirements for the methods in the Editor class, let n represent the size of the text—this is not necessarily the same as the n used as a parameter in several methods. The delete method calls the one-parameter listIterator (int index) method, for which worstTime(n) is linear in n. There is then a loop in which some elements in the text are removed; each removal takes constant time. This number of elements is certainly less than or equal to n, the total number of elements in the text. So for the delete method, worstTime(n) is linear in n.
The setCurrentLineNumber method also calls the listIterator (int index) method, and that makes the worstTime(n) linear in n for the setCurrentLineNumber method. The done method loops through the text, so its worstTime(n) is also linear in n. All other methods take constant time, except those whose worstTime(n) is linear in n owing to their calling the delete, setCurrentLineNumber, or done methods.
7.4.4 Design of the EditorUser Class
We will create another class, EditorUser, to illustrate the use of input and output files for editing text. The paths for the input and output files are scanned in from the keyboard, and a file scanner and file writer for those two files are declared and opened in the run( ) method. The only other responsibility of the EditorUser class is to edit the input file. Here are the method specifications for the editText() method.
/**
* Edits the text by performing the input-file commands
*
* @param fileScanner - a Scanner object over the input file
* @param printWriter - a PrintWriter object that holds the edited text.
*
*/
public void editText (Scanner fileScanner, PrintWriter printWriter)
Figure 7.20 has all the UML class diagrams for this project.
FIGURE 7.20 Class diagrams for the Editor project
The book's website has the EditorUserTest class to test the editText method.
7.4.5 Implementation of the EditorUser Class
The run() method is similar to the file-oriented run() method of the Scores3 class in Chapter 2:
public void run() { ScannerfileScanner= null; PrintWriterprintWriter= null; final StringIN_FILE_PROMPT= " Please enter the path for the input file:"; final String OUT_FILE_PROMPT = " Please enter the path for the output file: "; final String IO_EXCEPTION_MESSAGE = "The file was not found. "; Scanner keyboardScanner = new Scanner (System.in); String inFilePath, outFilePath; boolean pathsOK = false ; while (!pathsOK) { try { System.out.print (IN_FILE_PROMPT); inFilePath = keyboardScanner.nextLine(); fileScanner = new Scanner (new File (inFilePath)); System.out.print (OUT_FILE_PROMPT); outFilePath = keyboardScanner.nextLine(); printWriter = new PrintWriter (new FileWriter (outFilePath)); pathsOK = true ; } // try catch (IOException e) { System.out.println (IO_EXCEPTION_MESSAGE + e); } // catch I/O exception } // while editText (fileScanner, printWriter); printWriter.close(); } // method run
The editText() method loops through the input file, with a try-block and a catch-block to handle all of the editing errors that may occur. During each loop iteration, the interpret method is called. The return value from this call will be null unless the command is "$Done", in which case the final text is printed.
Here is the definition:
public void editText (Scanner fileScanner, PrintWriter printWriter) { final String FINAL_MESSAGE = " *********************** Here is the final text: n"; String line = new String(), result = new String(); while (true) { try { line = fileScanner.nextLine(); printWriter.println (line); result = editor.interpret (line); } // try catch (RuntimeException e) { printWriter.println (e); } // catch RuntimeException if (line.equals (Editor.DONE_COMMAND)) { printWriter.println (FINAL_MESSAGE + result); break; } // line is done command } // while } // method editText
This method accesses the public constant DONE_COMMAND from the Editor class. That enables us to avoid the dangerous practice of defining the same constant identifier twice. The danger is that this identifier might be re-defined in a subsequent application, for example, if the developer of the Editor class decided to change the command-start symbol from '$' to '#'.
SUMMARY
A linked list is a List object (that is, an object in a class that implements the List interface) in which the following property is satisfied:
Each element is contained in an object, called an Entry object, that also includes a reference, called a link, to another Entry object. For each Entry object except the one that holds the last element in the collection, the link is to the Entry object that contains the next element in the collection.
A linked list that also satisfies the following property:
Each Entry object except the first also includes a link to the Entry object that contains the previous element.
is called a doubly-linked list. Otherwise, it is called a singly-linked list.
The SinglyLinkedList class implements a singly-linked list. The purpose of developing the SinglyLinkedList class is to introduce you to the topics of links and iterators, and thus to prepare you for the focal point of the chapter: the LinkedList class, part of the Java Collections Framework. LinkedList objects lack the random-access ability of ArrayList objects. But, by using an iterator, an element can be added to or removed from a LinkedList in only constant time; for adding to or removing from an ArrayList object, worstTime(n) is linear in n. This advantage of LinkedList objects is best suited for consecutive insertions and deletions because, for the task of getting to the index of the first insertion or deletion, worstTime(n )is linear in n.
The Java Collection Framework's implementation of the LinkedList class stores the elements in a circular, doubly-linked structure with a dummy entry. Another possible implementation is a non-circular, doubly-linked structure with head and tail fields.
The application, a simple line editor, took advantage of the LinkedList class's ability to quickly make consecutive insertions and deletions anywhere in a LinkedList object.
CROSSWORD PUZZLE
| ACROSS | DOWN |
| 6. A class that is embedded in another class is called a _______ class. | 1. A program that edits text, line-by-line. |
| 8. The only operator in Java that has three operands (separated by '?' and ':'). | 2. In the LinkedList class, the method that associated the calling object with an iterator that can move forward or backward is (). |
| 10. A linked list in which each Entry object includes a link to the Entry object that contains the previous element in the list. | 3. The worstTime(n) for the public methods in the Listltr class. |
| 4. The class that catches the expectations thrown in the Editor class. | |
| 5. The field in the LinkedList class that contains a reference to a special Entry object, called a "dummy entry." | |
| 7. In the SinglyLinkedList or LinkedList class, the method that associated the calling object with an iterator that can move forward only is _______ (). | |
| 9. In a linked list entry, a reference to the entry that contains the next element in the linked list. |
CONCEPT EXERCISES
7.1 In the SinglyLinkedList class, define the following method without using an iterator.
/** * Finds the element at a specified position in this LinkedList object. * The worstTime(n) is O(n). * * @param index - the position of the element to be returned. * * @return the element at position index. * * @throws IndexOutOfBoundsException - if index is less than 0 or greater than * or equal to size(). */ public E get (int index)
7.2 Re-do Concept Exercise 7.1 by using an iterator.
7.3 Suppose we added each of the following methods to the ArrayList class:
public boolean addFirst (E element); public boolean addLast (E element); public E getFirst(); public E getLast(); public E removeFirst(); public E removeLast();
Estimate worstTime(n) for each method.
7.4 The listIterator() method can be called by a LinkedList object, but is not defined within the LinkedList class. In what class is that listIterator() method defined? What is that definition?
7.5 One of the possibilities for fields in the LinkedList class was to have head and tail fields, both of type Entry, where the Entry class had element and next fields, but no previous field. Then we would have a singly-linked list.
- Define the addLast method for this design. Here is the method specification:
/** * Appends a specified element to (the back of) this LinkedList object. * * @param element - the element to be appended. * * @return true. * */ public boolean addLast (E element) - The definition of the removeLast() method would need to make null the next field in the Entry object before the Entry object tail. Could we avoid a loop in the definition of removeLast() if, in the LinkedList class, we added a beforeTail field that pointed to the Entry object before the Entry object tail? Explain.
7.6 How can you distinguish between a call to the add (E element) method in the LinkedList class and a call to the add (E element) method in the ListItr class?
7.7 Explain how to remove "Don" from the LinkedList object in Figure 7.18. Explain why, for the definition of the method remove (Object obj), worstTime(n) is linear in n ?
7.8 In the Java Collections Framework, the LinkedList class is designed as a circular, doubly-linked list with a dummy entry (pointed to by the header field). What is the main advantage of this approach over a circular, doubly-linked list with head and tail fields?
7.9 For the three methods in the EditorUser class, estimate worstTime(n), where n represents the number of lines of text.
PROGRAMMING EXERCISES
7.1 Use the SinglyLinkedList class three times. First, create a SinglyLinkedList object, team1, with elements of type String. Add three elements to teaml. Second, create team2, another SinglyLinkedList object with elements of type String. Add four elements to team2. Finally, create a SinglyLinkedList object, league, whose elements are SinglyLinkedList objects of teams. Add teaml and team2 to league.
7.2 Hypothesize the output from the following method segment:
LinkedList<Character> letters = new LinkedList<Character>();
ListIterator<Character> itr = letters.listIterator();
itr.add ('f'),
itr.add ('t'),
itr.previous();
itr.previous();
itr.add ('e'),
itr.add ('r'),
itr.next();
itr.add ('e'),
itr.add ('c'),
itr = letters.listIterator();
itr.add ('p'),
System.out.println (letters);
Test your hypothesis.
7.3 Rewrite the code in Programming Exercise 7.2 without using an iterator. For example, you would start with:
LinkedList<Character> letters = new LinkedList<Character>();
letters.add (0, 'f'),
Test your revision.
7.4 Rewrite the code in Exercise 7.2 with a native array. For example, you would start with:
char [ ] letters = new char [10]; letters [0] = 'f';
Test your revision.
7.5 Hypothesize the error in the following code:
LinkedList<Double> duesList = new LinkedList<Double>();
ListItr<Double> itr = duesList.listIterator();
7.6 Suppose we have the following:
LinkedList<Double> weights = new LinkedList<Double>();
ListIterator<Double> itr;
weights.add (5.3);
weights.add (2.8);
itr = weights.listIterator();
Hypothesize which of the following sequences of messages would now be legal:
- itr.add (8.8); itr.next(); itr.remove();
- itr.add (8.8); itr.remove(); itr.next();
- itr.next(); itr.add (8.8); itr.remove();
- itr.next(); itr.remove(); itr.add (8.8);
- itr.remove(); itr.add (8.8); itr.next();
- itr.remove(); itr.next(); itr.add (8.8);
Test your hypotheses.
7.7 Suppose you decided to rewrite the VeryLongInt class, from Chapter 6, with a LinkedList instead of an ArrayList. The main change is to replace each occurrence of the identifier ArrayList with LinkedList. Another change, in the String -parameter constructor, is to replace
digits = new ArrayList<Integer> (s.length());
with
digits = new LinkedList<Integer>();
But the add method will now take quadratic time because the least method will now take linear time. Modify the least method—including its heading—so that its worstTime(n) will be constant. Make the corresponding changes to the add method so that method will take only linear time.
7.8 Rewrite the insert method in the Editor class to insert the given line after the current line. For example, if the text is
>I was
older then
and the command is
$Insert
so much
then the text becomes
Iwas
>so much
older then
The newly added line becomes the current line.
7.9 Modify the EditorUser class to work with commands entered from the keyboard instead of a file. The output should go to the console window. Test your changes by entering, from the keyboard, the lines in editor.in1 from the Editor directory on the book's website.
7.10 Unit test and define the following method:
/**
* Removes the first and last 4-letter word from a given LinkedList<String> object.
* Each word will consist of letters only.
* The worstTime(n) is O(n).
*
* @param list - the LinkedList<String> object.
*
* @throws NullPointerException - if list is null.
* @throws NoSuchElementException - if list is not null, but list has no 4-letter
* words or only one 4-letter word.
*
*/
public static void bleep (LinkedList<String> list)
Programming Project 7.1: Expanding the SinglyLinkedList Class
Expand the SinglyLinkedList class from Lab 12 by providing genuine definitions—not just thrown exceptions—for each of the following methods:
/** * Adds a specified element at the back of this SinglyLinkedList object. * * @param element - the element to be inserted. * * @return true. * */ public boolean add (E element) /** * Inserts the elements of this SinglyLinkedList object into an array in the same * order as in this SinglyLinkedList object. The worstTime(n) is O(n). * * @return a reference to the array that holds the same elements, in the same * order, as this SinglyLinkedList object. * */ public Object [ ] toArray () /** * Determines if this SinglyLinkedList object contains all of the elements from a * specified collection. * * @param c - the specified collection. * * @return true - if this SinglyLinkedList object contains each element of c; * otherwise, return false. * * @throws NullPointerException - if c is null. * */ public boolean containsAll (Collection<?> c) /** * Determines if this SinglyLinkedList object is equal to obj. * * @param obj - an object whose equality to this SinglyLinkedList object is * being tested. * * @return true - if obj is a SinglyLinkedList object of the same size as this * SinglyLinkedList object, and at each index, the element in this * SinglyLinkedList object is equal to the element at the same * index in obj. * */ public boolean equals (Object obj)
For unit testing, modify the SinglyLinkedTest class from the book's website.
Implementing the remove() Method in SinglyLinkedListIterator
- Modify the SinglyLinkedListIterator class by implementing the remove() method. Here are revised fields that class and a revised definition of the next() method:
protected Entry previous, // reference to Entry before lastReturned Entry lastReturned, // reference to Entry with element returned // by most recent call to next( ) method. next; // reference to Entry with element that will be // returned by subsequent call to next( ) method public E next () { if (lastReturned != null) previous = lastReturned; lastReturned = next; next = next.next; return lastReturned.element; } // method next
- For unit testing of your remove() method, update the SinglyLinkedTest class.
Programming Project 7.3: Making a Circular Singly Linked List Class
Modify the SinglyLinkedList class to be circular. That is, the entry after the last entry should be the entry referenced by head. Here is an example, with three elements:
The only methods you need to implement are the five methods listed in Section 7.2 and the iterator() method from Section 7.2.2. You will also need to test those methods.
Programming Project 7.4: Alternative Implementation of the LinkedList Class
Implement the LinkedList class with head and tail fields instead of a header field that points to a dummy entry. Your implementation should be doubly-linked, that is, each Entry object should have a reference to the previous Entry object and a reference to the next Entry object. You get to choose whether your implementation will be circular. The Entry class will be unchanged from the header implementation, but the ListItr class will need to be modified.
Create a LinkedListTest class to test your LinkedList and ListItr classes.
Programming Project 7.5: Expanding the Line Editor
Expand the Line Editor project by implementing the following additional commands:
5. $Change %X%Y%
Effect: In the current line, each occurrence of the string given by X will be replaced by the string given by Y.
Example Suppose the current line is
bear ruin'd choirs, wear late the sweet birds sang
Then the command
$Change %ear%are%
will cause the current line to become
bare ruin'd choirs, ware late the sweet birds sang
If we then issue the command
$Change %wa%whe%
the current line will be
bare ruin'd choirs, where late the sweet birds sang
Notes:
- If either X or Y contains a percent sign, it is the end-user's responsibility to choose another delimiter. For example,
$Change #0.16#16%#
- The string given by Y may be the null string. For example, if current line is
aid of their country.
then the command
$Change %of %%
will change the current line to
aid their country.
- If the delimiter occurs fewer than three times, the error message to be generated is
*** Error:Delimiter must occur three times. Please try again.
6.$Last
Effect: The line number of the last line in the text has been returned.
Example Suppose the text is
I heard a bird sing > in the dark of December. A magical thing and a joy to remember.
The command
$Last
will cause 3 to be returned. The text and the designation of the current line are unchanged.
7.$GetLines m n
Effect: Each line number and line in the text, from lines m through n, inclusive, will be returned.
Example Suppose the text is
Winston Churchill once said that > democracy is the worst form of government except for all the others.
The command
$GetLines 0 2
will cause the following to be returned:
0 Winston Churchill once said that 1 democracy is the worst 2 form of government
The text and the designation of the current line are unchanged.
Note: If no line numbers are entered, the entire text should be returned. For example,
$GetLines
is the command to return the entire text, with line numbers.
As with the delete command, an error message should be generated if (1) m is greater than n or if (2) m is less than 0 or if (3) n is greater than the last line number in the text.
Expand the EditorTest class to validate your changes.
System Test 1 (For simplicity, prompts are omitted. Error messages and the values returned by $GetLines and $Last are shown in boldface):
$Insert You can fool some of the people some of the times, but you cannot foul all of the people all of the time. $Line 2 $GetLines 2 1 Error: The first line number is greater than the second. $ GetLines 2 2 2 some of the times, $Change %s%% $GetLines 2 2 2 some of the time, $Change %o%so Error: Delimiter must occur three times. Please try again. $Change %o%so% $GetLines 2 2 2 some sof the time, Change Error: a command should start with $. $Change %sof%of% $GetLines 2 2 2 some of the time, $Line 0 $Insert Lincoln once said that you can fool some of the people all the time and all of the time and $Last 10 $GetLines 0 10 0 Lincoln once said that 1 you can fool 2 some of the people 3 all the time and 4 all of the time and 5 You can fool 6 some of the people 7 some of the time, 8 but you cannot foul 9 all of the people 10 all of the time. $Line 5 $Change %Y%y% $GetLines 5 5 5 you can fool $Line 6 $Change %some%all% $GetLines 6 6 6 all of the people $Line 8 $Change %ul%ol% $GetLines 8 8 8 but you cannot fool $Line 9 $Change %ee%eo% $GetLines 9 9 9 all of the people $Delete 3 3 $GetLines 0 l0 Error: The second line number is greater than the number of the last line in the text. $Last 9 $GetLines 0 9 0 Lincoln once said that 1 you can fool 2 some of the people 3 all of the time and 4 you can fool 5 all of the people 6 some of the time, 7 but you cannot fool 8 all of the people 9 all of the time. $Done Here is the final text: Lincoln once said that you can fool some of the people > all of the time and you can fool all of the people some of the time, but you cannot fool all of the people all of the time.
System Test 2
$Insert Life is full of successes and lessons. $Delete 1 1 $Insert wondrous oppurtunities disguised as hopeless situations. $Last 2 $GetLines 0 Life is full of 1 wondrous oppurtunities disguised as 2 hopeless situations. $Line 1 $Change %ur%or% $GetLines 0 2 0 Life is full of 1 wondrous opportunities disguised as 2 hopeless situations. $Done Here is the final text: Life is full of > wondrous opportunities disguised as hopeless situations.
An Integrated Web Browser and Search Engine, Part 3
In this part of the project, you will add functionality to the forward and backward buttons in your browser. Up to now, the end user can type a URL in the input line, can click on the home button, and can click on a link (if there is one) in the currently displayed page. Your revisions will allow the end user to go backward or forward to other web pages in the current chain.
According to standard web-browser protocol, you cannot go where you already are. So, for example, if you are on the home page, nothing happens if you click on the Home button. Also, whenever a new page is printed, all forward links are removed. For example, if you click on browser2, then browser4, then back, then home, the forward button would now be disabled (and colored red), so you could not click Forward to get to browser4.
The only class you will be altering is your listener class.
The web pages you can use to test your project—home.inl, browser.ini, browser.in2, browser.in4, and browser.in5—are the same as in Programming Project 2.1 from Chapter 2..
When a button is enabled, its color should be green..
When a button is disabled, its color should be red..
Here are some system tests that your project must pass.
System Test 1:
click on browser2, browser4, back (browser2 appears), enter browser.in5 in the input line, click on back (browser2 appears), forward (browser5 appears)
At this point, the Forward button is disabled.
System Test 2:
click on browser2, browser4, back (browser2 appears), home, back
(browser2 appears), back (home appears), forward (browser2 appears), forward (home appears)
At this point, the Forward button is disabled.
1. In Project 7.1, two additional fields are added to the SinglyLinkedListIterator class.
2. For example, instead of writing
if (first > second) big = first; else big = second;
we can simply write:
big = (first > second) ? first : second;
This can be read as "If first is greater than second, assign to big the value of first. Otherwise, assign to big the value of second." The syntax for a conditional expression is:
condition ? expression_t : expression_f
The semantics is this: if the condition has the value true, then the value of the conditional expression is the value of expression_t. Otherwise, the value of the conditional expression is the value of expression_f. If you like to write cryptic code, you'll love the conditional operator, one of the legacies that Java got from C. Note that it is the only ternary operator in Java. That means it has three operands.