Adds elem into this list as the first element.public voidaddLast(E elem)Adds elem into this list as the last element.A LinkedList is a good base for a queueand indeed it implements the Queue interface discussed nextor
any other list in which most of the action is not at the end. For a stack, or for building up a list of elements as
you find them, an ArrayList is more efficient because it requires fewer objects: the one array instead of
one object for each element in the list. You can also efficiently scan an ArrayList without creating an
Iterator object, by simply using an int as an index. This can be a good reason to use an ArrayList for
a list that will be scanned frequently.
Here is a Polygon class that stores a list of Point objects that are the polygon's vertices:
import java.util.List;
import java.util.ArrayList;
public class Polygon {
private List
new ArrayList
public void add(Point p) {
vertices.add(p);
}
public void remove(Point p) {
vertices.remove(p);
}
public int numVertices() {
return vertices.size();
}
// ... other methods ...
}
Notice that vertices is a List reference that is assigned an ArrayList object. You should declare a
variable to be as abstract a type as possible, preferring the abstract List type to the implementation class
ArrayList. As written, you could change Polygon to use a LinkedList if that would be more efficient
by changing only one line of codethe line that creates the list. All the other code can remain unchanged.
Exercise 21.1: Write a program that opens a file and reads its lines one at a time, storing each line in a List
sorted by String.compareTo. The line-reading class you created for Exercise 20.4 should prove helpful.
21.6.3. RandomAccess Lists
The marker interface RandomAccess marks list implementations that support fast random access. Random
access means that any element of the list can be accessed directly. For example, ArrayList implements
RandomAccess because any element can easily be accessed by its index. In contrast, a LinkedList does
not implement RandomAccess because accessing an element by index requires traversing from one end of
the list. Some algorithms for manipulating random access lists perform poorly when applied to sequential
lists, so the purpose of the RandomAccess interface is to allow an algorithm to adapt depending on the kind
of list it is given. As a rule of thumb, if code such as
for (int i = 0; i < list.size(); i++)