Linked Lists - Building Java Programs: A Back to Basics Approach - page 976

17. Write a method called doubleList that doubles the size of a list by appending a copy of the original sequence to
the end of the list. For example, if a variable list stores the values [1, 3, 2, 7] and we make the call of
list.doubleList(); then after the call it should store [1, 3, 2, 7, 1, 3, 2, 7] . Notice that the list has
been doubled in size by having the original sequence appear twice in a row. You may not make assumptions about
how many elements are in the list. You may not call any methods of the class to solve this problem. If the
original list contains n nodes, then you should construct exactly n nodes to be added. You may not use any auxiliary
data structures such as arrays or ArrayList s to solve this problem. Your method should run in O( n ) time where n is
the number of nodes in the list.
18. Write a method called rotate that moves the value at the front of a list of integers to the end of the list. For
example, if a variable called list stores the values [8, 23, 19, 7, 45, 98, 102, 4] , then the call of
list.rotate(); should move the value 8 from the front of the list to the back of the list, changing the list to store
[23, 19, 7, 45, 98, 102, 4, 8] . If the method is called for a list of 0 elements or 1 element, it should have
no effect on the list. You may not construct any new nodes to solve this problem nor change any of the data values
stored in the nodes. You must solve the problem by rearranging the links of the list.
19. Write a method called shift that rearranges the elements of a list of integers by moving to the end of the list all val-
ues that are in odd-numbered positions and otherwise preserving list order. For example, suppose that a variable list
stores the values [10, 31, 42, 23, 44, 75, 86] . The call of list.shift(); should rearrange the list to store
[10, 42, 44, 86, 31, 23, 75] . It doesn't matter whether the value itself is odd or even; what matters is
whether the value appears in an odd index (index 1, 3, 5, etc). Also notice that the original order of the list is otherwise
preserved. You may not construct any new nodes nor use any auxiliary data structures to solve this problem. You also
may not change any data fields of the nodes; you must solve this problem by rearranging the links of the list.
20. Write a method called reverse that reverses the order of the elements in the list. (This is very challenging!) For
example, if the variable list initially stores the values [1, 8, 19, 4, 17] , the call of list.reverse();
should change the list to store [17, 4, 19, 8, 1] .
Programming Projects
1. The actual List interface in the java.util package has several methods beyond the ones implemented in this
chapter. Write a version of LinkedList<E> that adds some or all of these methods. The methods to add are the fol-
lowing (some headers are slightly modified; see the Java API Specification for descriptions of each method):
• public void addAll(int index, List<E> list)
• public boolean containsAll(List<E> list)
• public boolean equals(Object o)
• public int lastIndexOf(Object o)
• public boolean remove(Object o)
• public void removeAll(List<E> list)
• public void retainAll(List<E> list)
• public Object[] toArray()
2. The java.util package has an interface called ListIterator that extends the Iterator interface and
includes additional methods that are specific to iterating through the elements of lists forward or backward.
Write a class called LinkedListIterator2 that adds some or all of these methods for iterating over a