Main Page

Previous Next

Linked Lists

The LinkedList collection class implements a generalized linked list. We have already seen quite a few of the methods that the class implements as the members of the List interface implemented in the Vector class. Nonetheless, let's quickly go through the methods that the LinkedList class implements. There are two constructors a default constructor that creates an empty list, and a constructor that accepts a Collection argument that will create a LinkedList object containing the objects from the collection that is passed to it.

To add objects to a list you have the add() and addAll() methods exactly as we discussed for a Vector object. You can also add an object at the beginning of a list using the addFirst() method, and you can add one at the end using addLast(). Both methods accept an argument of type Object and do not return a value. Of course, the addLast() method provides the same function as the add() method.

To retrieve an object at a particular index position in the list you can use the get() method, as in the Vector class. You can also obtain references to the first and last objects in the list by using the getFirst() and getLast() methods, respectively. To remove an object you can use the remove() method with an argument that is either an index value or a reference to the object that is to be removed. The removeFirst() and removeLast() methods do what you would expect.

Replacing an existing element in the list at a given index position is achieved by using the set() method. The first argument is the index value and the second argument is the new object at that position. The old object is returned and the method will throw an IndexOutOfBoundsException if the index value is not within the limits of the list. The size() method returns the number of elements in the list.

As with a Vector object, you can obtain an Iterator object by calling iterator(), and you can obtain a ListIterator object by calling listIterator(). You will recall that an Iterator object only allows you to go forward through the elements, whereas a ListIterator enables you to iterate backwards or forwards.

We could change the TryPolyLine example from Chapter 6 to use a LinkedList collection object rather than our homemade version.

Try It Out – Using a Genuine Linked List

We will put this example in a new directory, TryNewPolyLine. We can use the TryPolyLine class that contains main() and the Point class exactly as they are, so if you still have them, copy the source files to the new directory. We just need to change the PolyLine class definition:

import java.util.*;

public class PolyLine {
  // Construct a polyline from an array of points
  public PolyLine(Point[] points) {
    // Add the  points
    for(int i = 0; i < points.length; i++)
      polyline.add(points[i]);
  }
  // Construct a polyline from an array of coordinate
  public PolyLine(double[][] coords) {
    // Add the points
    for(int i = 0; i < coords.length; i++)
       polyline.add(new Point(coords[i][0], coords[i][1]));
  }

  // Add a Point object to the list
  public void addPoint(Point point) {
    polyline.add(point);    // Add the new point
  }

  // Add a point to the list
  public void addPoint(double x, double y) {
    polyline.add(new Point(x, y));
  }

  // String representation of a polyline
  public String toString() {
    StringBuffer str = new StringBuffer("Polyline:");
    Iterator points = polyline.iterator();           // Get an iterator

    while(points.hasNext())
      str.append(" "+ (Point)points.next());         // Append the current point

    return str.toString();
  }

  private LinkedList polyline = new LinkedList();    // Stores points for polyline
}

The class is a lot simpler because the LinkedList class provides all the mechanics of operating a linked list. Since the interface to the PolyLine class is the same as the previous version, the original version of main() will run unchanged and produce exactly the same output.

How It Works

The only interesting bit is the change to the PolyLine class. Point objects are now stored in the linked list implemented by the LinkedList object, polyline. We use the add() method to add points in the constructors and the addPoint() methods. The toString() method now uses an iterator to go through the points in the list. Using a collection class makes the PolyLine class very straightforward.

Previous Next
JavaScript Editor Java Tutorials Free JavaScript Editor