List
Lists promise to maintain elements in a particular sequence. The List interface adds a number of methods to Collection that allow insertion and removal of elements in the middle of a List.
There are two types of List:
n The basic ArrayList, which excels at randomly accessing elements, but is slower when inserting and removing elements in the middle of a List.
n The LinkedList, which provides optimal sequential access, with inexpensive insertions and deletions from the middle of the List. A LinkedList is relatively slow for random access, but it has a larger feature set than the ArrayList.
The following example reaches forward in the book to use a library from the Type Information chapter by importing typeinfo.pets. This is a library that contains a hierarchy of Pet classes along with some tools to randomly generate Pet objects. You don’t need to know the full details at this point, just that (1) there’s a Pet class and various subtypes of Pet and (2) the static Pets.arrayList( ) method will return an ArrayList filled with randomly selected Pet objects:
//: holding/ListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
public class ListFeatures {
public static void main(String[] args) {
Random rand = new Random(47);
List<Pet> pets = Pets.arrayList(7);
print("1: " + pets);
Hamster h = new Hamster();
pets.add(h); // Automatically resizes
print("2: " + pets);
print("3: " + pets.contains(h));
pets.remove(h); // Remove by object
Pet p = pets.get(2);
print("4: " + p + " " + pets.indexOf(p));
Pet cymric = new Cymric();
print("5: " + pets.indexOf(cymric));
print("6: " + pets.remove(cymric));
// Must be the exact object:
print("7: " + pets.remove(p));
print("8: " + pets);
pets.add(3, new Mouse()); // Insert at an index
print("9: " + pets);
List<Pet> sub = pets.subList(1, 4);
print("subList: " + sub);
print("10: " + pets.containsAll(sub));
Collections.sort(sub); // In-place sort
print("sorted subList: " + sub);
// Order is not important in containsAll():
print("11: " + pets.containsAll(sub));
Collections.shuffle(sub, rand); // Mix it up
print("shuffled subList: " + sub);
print("12: " + pets.containsAll(sub));
List<Pet> copy = new ArrayList<Pet>(pets);
sub = Arrays.asList(pets.get(1), pets.get(4));
print("sub: " + sub);
copy.retainAll(sub);
print("13: " + copy);
copy = new ArrayList<Pet>(pets); // Get a fresh copy
copy.remove(2); // Remove by index
print("14: " + copy);
copy.removeAll(sub); // Only removes exact objects
print("15: " + copy);
copy.set(1, new Mouse()); // Replace an element
print("16: " + copy);
copy.addAll(2, sub); // Insert a list in the middle
print("17: " + copy);
print("18: " + pets.isEmpty());
pets.clear(); // Remove all elements
print("19: " + pets);
print("20: " + pets.isEmpty());
pets.addAll(Pets.arrayList(4));
print("21: " + pets);
Object[] o = pets.toArray();
print("22: " + o[3]);
Pet[] pa = pets.toArray(new Pet[0]);
print("23: " + pa[3].id());
}
} /* Output:
1: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug]
2: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Hamster]
3: true
4: Cymric 2
5: -1
6: false
7: true
8: [Rat, Manx, Mutt, Pug, Cymric, Pug]
9: [Rat, Manx, Mutt, Mouse, Pug, Cymric, Pug]
subList: [Manx, Mutt, Mouse]
10: true
sorted subList: [Manx, Mouse, Mutt]
11: true
shuffled subList: [Mouse, Manx, Mutt]
12: true
sub: [Mouse, Pug]
13: [Mouse, Pug]
14: [Rat, Mouse, Mutt, Pug, Cymric, Pug]
15: [Rat, Mutt, Cymric, Pug]
16: [Rat, Mouse, Cymric, Pug]
17: [Rat, Mouse, Mouse, Pug, Cymric, Pug]
18: false
19: []
20: true
21: [Manx, Cymric, Rat, EgyptianMau]
22: EgyptianMau
23: 14
*///:~
The print lines are numbered so the output can be related to the source code. The first output line shows the original List of Pets. Unlike an array, a List allows you to add elements after it has been created, or remove elements, and it resizes itself. That’s its fundamental value: a modifiable sequence. You can see the result of adding a Hamster in output line 2—the object is appended to the end of the list.
You can find out whether an object is in the list using the contains( ) method. If you want to remove an object, you can pass that object’s reference to the remove( ) method. Also, if you have a reference to an object, you can discover the index number where that object is located in the List using indexOf( ), as you can see in output line 4.
When deciding whether an element is part of a List, discovering the index of an element, and removing an element from a List by reference, the equals( ) method (part of the root class Object) is used. Each Pet is defined to be a unique object, so even though there are two Cymrics in the list, if I create a new Cymric object and pass it to indexOf( ), the result will be -1 (indicating it wasn’t found), and attempts to remove( ) the object will return false. For other classes, equals( ) may be defined differently—Strings, for example, are equal if the contents of two Strings are identical. So to prevent surprises, it’s important to be aware that List behavior changes depending on equals( ) behavior.
In output lines 7 and 8, removing an object that exactly matches an object in the List is shown to be successful.
It’s possible to insert an element in the middle of the List, as you can see in output line 9 and the code that precedes it, but this brings up an issue: for a LinkedList, insertion and removal in the middle of a list is a cheap operation (except for, in this case, the actual random access into the middle of the list), but for an ArrayList it is an expensive operation. Does this mean you should never insert elements in the middle of an ArrayList, and switch to a LinkedList if you do? No, it just means you should be aware of the issue, and if you start doing many insertions in the middle of an ArrayList and your program starts slowing down, that you might look at your List implementation as the possible culprit (the best way to discover such a bottleneck, as you will see in the supplement at http://MindView.net/Books/BetterJava, is to use a profiler). Optimization is a tricky issue, and the best policy is to leave it alone until you discover you need to worry about it (although understanding the issues is always a good idea).
The subList( ) method allows you to easily create a slice out of a larger list, and this naturally produces a true result when passed to containsAll( ) for that larger list. It’s also interesting to note that order is unimportant—you can see in output lines 11 and 12 that calling the intuitively named Collections.sort( ) and Collections.shuffle( ) on sub doesn’t affect the outcome of containsAll( ). subList( ) produces a list backed by the original list. Therefore, changes in the returned list are reflected in the original list, and vice versa.
The retainAll( ) method is effectively a "set intersection" operation, in this case keeping all the elements in copy that are also in sub. Again, the resulting behavior depends on the equals( ) method.
Output line 14 shows the result of removing an element using its index number, which is more straightforward than removing it by object reference since you don’t have to worry about equals( ) behavior when using indexes.
The removeAll( ) method also operates based on the equals( ) method. As the name implies, it removes all the objects from the List that are in the argument List. The set( ) method is rather unfortunately named because of the potential confusion with the Set class— "replace" might have been a better name here, because it replaces the element at the index (the first argument) with the second argument.
Output line 17 shows that for Lists, there’s an overloaded addAll( ) method that allows you to insert the new list in the middle of the original list, instead of just appending it to the end with the addAll( ) that comes from Collection.
Output lines 18-20 show the effect of the isEmpty( ) and clear( ) methods.
Output lines 22 and 23 show how you can convert any Collection to an array using toArray( ). This is an overloaded method; the no-argument version returns an array of Object, but if you pass an array of the target type to the overloaded version, it will produce an array of the type specified (assuming it passes type checking). If the argument array is too small to hold all the objects in the List (as is the case here), to Array( ) will create a new array of the appropriate size. Pet objects have an id( ) method, which you can see is called on one of the objects in the resulting array.
[Thinking in Java, 283]
