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) Get the solution of 7.1
7.2 Re-do Concept Exercise 7.1 by using an iterator. Get the solution of 7.2
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. Get the solution of 7.3
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? Get the solution of 7.4
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.
a. 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)
b. 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. Get the solution of 7.5
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? Get the solution of 7.6
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? Get the solution of 7.7
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? Get the solution of 7.8
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 team1. 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 team1 and team2 to league. Get the solution of 7.1
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. Get the solution of 7.2
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. Get the solution of 7.3
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. Get the solution of 7.4
7.5 Hypothesize the error in the following code:
LinkedList<Double> duesList = new LinkedList<Double>();
ListItr<Double> itr = duesList.listIterator();
Test your hypothesis. Get the solution of 7.5
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:
a. itr.add (8.8); itr.next(); itr.remove();
b. itr.add (8.8); itr.remove(); itr.next();
c. itr.next(); itr.add (8.8); itr.remove();
d. itr.next(); itr.remove(); itr.add (8.8);
e. itr.remove(); itr.add (8.8); itr.next();
f. itr.remove(); itr.next(); itr.add (8.8);
Test your hypotheses. Get the solution of 7.6
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. Get the solution of 7.7
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
I was
>so much
older then
The newly added line becomes the current line. Get the solution of 7.8
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. Get the solution of 7.9
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) Get the solution of 7.10
