Copying a list
Last time, we went through several list algorithms, coding from the diagrams. Another important function is copying a list.
What should the signature for this function be?
LinkedList copy();
How do we traverse the list in copying it? What reference(s) (“pointers”) do we need? A current pointer, for the node being copied. A previous pointer, to the copy of the previous node.
What special cases are there (first node copied, last node copied, etc.)? When we copy the first node, we have to create the list … we need to set the instance variable first to point at the first node.
Now let’s write the code.
public LinkedList copy() {
Node current = first;
Node previous = null;
LinkedList l = new LinkedList();
while (current != null) {
Node n = new Node(); n.data= current.data;
if (current == first) l.first = n;
else previous.next = n;
previous = n;
current = current.next;
}
return l;
}
Implementing a list iterator
What are the advantages of implementing a list-iterator class?
Clients can get at elements in the list without having to access private data, and without having to destroy the list.
Here is the interface for a simplified list iterator.
public ListIterator();
public Object next();
public boolean hasNext();
public void add(Object element); // Adds an element before the iterator position and moves the iterator past the inserted element.
public void remove(); // Removes the last traversed element. Can only be called after a call to next().
public void set(Object element); // Sets the last traversed element to a different value.
One important feature of the iterator is that it maintains a current position.
· What is this variable initialized to? null
· When does this variable change value? Methods next, add, and remove change it. remove sets position to previous.
· How is this variable used to enforce the rules on when items can be deleted? A deletion isn’t allowed if previous = position, and remove sets previous = position.
How does a client obtain a new list iterator? It calls the listIterator() method for this list.
myList.listIterator()
Using a list iterator
In this section, we will use the “real” LinkedList and ListIterator defined in java.util. Both are generic. What does that mean?
Suppose we have a LinkedList<Integer and we want to print its elements. Our goal is to print something like
LinkedList( 1 3 5 )
How would we do this?
package llExample;
import java.util.*;
public class ListExample {
public static void main(String args[]) {
LinkedList<Integer> l = new LinkedList();
l.addFirst(5); l.addFirst(3); l.addFirst(1);
ListIterator<Integer> lit = l.listIterator();
System.out.print("LinkedList( ");
while (lit.hasNext()) {
System.out.print(lit.next() + " ");
}
System.out.println(")");
}
}
The for-each loop
In this case, we are visiting the nodes of the linked list in order. So we can use the for statement.
The example given in the text is
LinkedList<String> employeeNames = ...;
for (String name: employeeNames) {
// Do something with name
}
System.out.print("LinkedList( ");
for (int i: l)
System.out.print(i + " ");
System.out.println(")");
Linked lists vs. array lists
Linked lists and array lists are two ways of representing the same information. They have different advantages and disadvantages, but they can both be treated as lists.
How could the functions below be implemented for ArrayList? Let’s assume that ArrayList has
· an array arr
· an instance variable position; what type would it be?
· Also, a variable count that keeps track of the number of elements currently on the list.
public ArrayListIterator()
public Object next()
public boolean hasNext()
What is the advantage of implementing the ListIterator interface for ArrayList as well as LinkedList?
What is the advantage of using an ArrayList?
What is the advantage of using a LinkedList?
So it might be advantageous for a program to switch between representations, depending on what kind of operations predominate on a particular list.
Lecture 10 Programming Concepts—Java XXX