ArrayList and LinkedList

We have already looked at the general properties of collection classes in Java. We will now look at some specific collection classes and how to use them. As we have seen, these classes can be divided into two categories: lists and sets.

A list consists of a sequence of items arranged in a linear order. A list has a definite order, but is not necessarily sorted into ascending order.

A set is a collection that has no duplicate entries. The elements of a set might or might not be arranged into some definite order.

There are two obvious ways to represent a list: as a dynamic array and as a linked list. Both of these options are available in generic form as the collection classes java.util.ArrayList and java.util.LinkedList. These classes are part of the Java Collection Framework. Each implements the interface List, and therefore the interface Collection. An object of type ArrayList represents an ordered sequence of objects of type T, stored in an array that will grow in size whenever necessary as new items are added. An object of type LinkedList also represents an ordered sequence of objects of type T, but the objects are stored in nodes that are linked together with pointers.

The LinkedList class is generally more efficient in applications where items will often be added or removed at the beginning of the list or in the middle of the list. In an array, these operations require moving a large number of items up or down one position in the array, to make a space for a new item or to fill in the hole left by the removal of an item. In a linked list, nodes can be added or removed at any position by changing a few pointer values, so the operation takes only some constant amount of time, independent of how many items are in the list.

The ArrayList class is more efficient when random access to items is required. Random access means accessing the k-th item in the list, for any integer k. Random access is used when you get or change the value stored at a specified position in the list. This is trivial for an array, but for a linked list it means starting at the beginning of the list and moving from node to node along the list for k steps.

Operations that can be done efficiently for both types of lists include sorting and adding an item at the end of the list.

All lists implement methods from interface Collection that were including size(), isEmpty(), add(T), remove(Object) and clear(). The add(T) method adds the object at the end of the list. The remove(Object) method involves first finding the object, which is not very efficient for any list since it involves going through the items in the list from beginning to end until the object is found. The interface List adds some methods for accessing list items according to their numerical positions in the list. Suppose that list is an object of type List. Then we have the methods:

  • list.get(index) – returns the object of type T that is at position index in the list, where index is an integer. Items are numbered 0, 1, 2, …,list.size()-1. The parameter must be in this range, or an IndexOutOfBoundsException is thrown.
  • list.set(index,obj) – stores the object obj at position number index in the list, replacing the object that was there previously. The object obj must be of type T. This does not change the number of elements in the list or move any of the other elements.
  • list.add(index,obj) – inserts an object obj into the list at position number index, where obj must be of type T. The number of items in the list increases by one, and items that come after position index move down one position to make room for the new item. The value of index must be in the range 0 to list.size(), inclusive. If index is equal to list.size(), then obj is added at the end of the list.
  • list.remove(index) – removes the object at position number index, and returns that object as the return value of the method. Items after this position move up one space in the list to fill the hole, and the size of the list decreases by one. The value of index must be in the range 0 to list.size()-1
  • list.indexOf(obj) – returns an int that gives the position of obj in the list, if it occurs. If it does not occur, the return value is -1. The object obj can be of any type, not just of type T. If obj occurs more than once in the list, the index of the first occurrence is returned.

These methods are defined both in class ArrayList<T> and in class LinkedList<T>, although some of them — get and set — are only efficient for ArrayLists. The class LinkedList<T> adds a few additional methods, which are not defined for an ArrayList. If linkedlist is an object of type LinkedList<T>, then we have:

  • linkedlist.getFirst() – returns the object of type T that is the first item in the list. The list is not modified. If the list is empty when the method is called, an exception of type NoSuchElementException is thrown (the same is true for the next three methods as well).
  • linkedlist.getLast() – returns the object of type T that is the last item in the list. The list is not modified.
  • linkedlist.removeFirst() – removes the first item from the list, and returns that object of type T as its return value.
  • linkedlist.removeLast() – removes the last item from the list, and returns that object of type as its return value.
  • linkedlist.addFirst(obj) — adds the obj, which must be of type T, to the beginning of the list.
  • linkedlist.addLast(obj) — adds the object obj, which must be of type T, to the end of the list. (This is exactly the same as linkedlist.add(obj)but is defined to keep the naming consistent.)

These methods are defined to make it easy to use a LinkedList as if it were a stack or a queue. For example, we can use a LinkedList as a queue by adding items onto one end of the list (using the addLast() method) and removing them from the other end (using the removeFirst()method).

If list is an object of type List<T>, then the method list.iterator(), defined in the interface Collection<T>, returns an Iterator that can be used to traverse the list from beginning to end. However, for Lists, there is a special type of Iterator, called a ListIterator, which offers additional capabilities. ListIterator<T> is an interface that extends the interface Iterator<T>. The method list.listIterator() returns an object of type ListIterator<T>.

ListIterator has the usual Iterator methods, hasNext(), next(), and remove(), but it also has methods has Previous(), previous(), and add(obj) that make it possible to move backwards in the list and to add an item at the current position of the iterator. To understand how these work, it’s best to think of an iterator as pointing to a position between two list elements, or at the beginning or end of the list. In this diagram, the items in a list are represented by squares, and arrows indicate the possible positions of an iterator:

LinkedList

If iter is of type ListIterator<T>, then iter.next() moves the iterator one space to the right along the list and returns the item that the iterator passes as it moves. The method iter.previous() moves the iterator one space to the left along the list and returns the item that it passes. The method iter.remove() removes an item from the list; the item that is removed is the item that the iterator passed most recently in a call to either iter.next() or iter.previous(). There is also a method iter.add(obj) that adds the specified object to the list at the current position of the iterator (where obj must be of type T). This can be between two existing items or at the beginning of the list or at the end of the list.

The lists that are used in class LinkedList<T> are doubly linked lists. Each node in the list contains two pointers, one to the next node in the list and one to the previous node. This makes it possible to efficiently implement both the next() and previous() methods of a ListIterator. Also, to make the addLast() and getLast() methods of a LinkedList efficient, the class LinkedList<T> includes an instance variable that points to the last node in the list.)

As an example of using a ListIterator, suppose that we want to maintain a list of items that is always sorted into increasing order. When adding an item to the list, we can use a ListIterator to find the position in the list where the item should be added. Once the position has been found, we use the same list iterator to place the item in that position. The idea is to start at the beginning of the list and to move the iterator forward past all the items that are smaller than the item that is being inserted. At that point, the iterator’s add() method can be used to insert the item. To be more definite, suppose that stringList is a variable of type List<String>. Assume that that the strings that are already in the list are stored in ascending order and that newItem is a string that we would like to insert into the list. The following code will place newItem in the list in its correct position, so that the modified list is still in ascending order:


ListIterator iter = stringList.listIterator();

// Move the iterator so that it points to the position where
// newItem should be inserted into the list.  If newItem is
// bigger than all the items in the list, then the while loop
// will end when iter.hasNext() becomes false, that is, when
// the iterator has reached the end of the list.

while (iter.hasNext()) {
   String item = iter.next();
   if (newItem.compareTo(item) <= 0) {
         // newItem should come BEFORE item in the list.
         // Move the iterator back one space so that
         // it points to the correct insertion point,
         // and end the loop.
      iter.previous();
      break;
   }
}

iter.add(newItem);

Here, stringList might be of type ArrayList<String> or of type LinkedList<String>. The algorithm that is used to insert newItem into the list will be about equally efficient for both types of lists, and it will even work for other classes that implement the interface List<String>. It would be easier to design an insertion algorithm that uses array-like indexing with the methods get(index) and add(index,obj). However, that algorithm would be inefficient for LinkedLists because random access is so inefficient for linked lists.

Next: TreeSet and HashSet