Implementing Lists Using Linked-Lists

1. primitive types: short, int, long, float, double, boolean, char, and byte
2. reference types: arrays and classes

When you declare a variable with a reference type, you get space for a reference (pointer) to that type, not for the type itself. You must use "new" to get space for the type itself. This is illustrated below.

Remember that class objects are also reference types. For example, if you declare a variable of type List, you only get space for a pointer to a list; no actual list exists until you use "new". This is illustrated below, assuming the array implementation of lists, and assuming that the List constructor initializes the items array to be of size 3. Note that because it is an array of Objects, each array element is (automatically) initialized to null (shown using a diagonal line in the picture).

An important consequence of the fact that non-primitive types are really pointers is that assigning from one variable to another can cause aliasing (two different names refer to the same object). For example:

Note that in this example, the assignment to B[1] changed not only that value, but also the value in A[1] (because A and B were pointing to the same array)! However, an assignment to B itself (not to an element of the array pointed to by B) has no effect on A:

A similar situation arises when a non-primitive value is passed as an argument to a method. For example, consider the following 4 statements, and the definition of method changeArray:

1.   int[] A = new int[3];
2.   A[1] = 6;
3.   changeArray(A);
4.   System.out.print(A[1]);

5.   public static void changeArray(int[] X) {
6.     X[1] = 10;
7.     X = new int[2];
8.   }

Note that the method call causes A and X to be aliases (they both point to the same array). Therefore, the assignment X[1] = 10 changes both X[1] and A[1]. However, the assignment X = new int[2] only changes X, not A, so when the call to changeArray finishes, the value of A[1] is still 10, not 0.

To understand this better, consider writing code to create a linked list with two nodes, containing "ant" and "bat", respectively, pointed to by a variable named L. First we need to declare variable L; here's the declaration together with a picture showing what we have so far:

To make L point to the first node of the list, we need to use new to allocate space for that node. We want its data field to contain "ant" and (for now) we don't care about its next field, so we'll use the 1-argument Listnode constructor (which sets the next field to null):

To add the second node to the end of the list we need to create the new node (with "bat" in its data field and null in its next field), and we need to set the next field of the first node to point to the new one:

Linked List Operations

• Adding a node after a given node in the list.
• Removing a given node from the list.

Adding a node

1. n, (a pointer to) a node in a list (i.e., n is a Listnode), and
2. newdat, the data to be stored in a new node

Step 1: create the new node using the given data

Step 2: "link it in":
(a) make the new node's next field point to whatever n's next field was pointing to
(b) make n's next field point to the new node.

Note that it is vital to first copy the value of n's next field into tmp's next field (step 2(a)) before setting n's next field to point to the new node (step 2(b)). If we set n's next field first, we would lose our only pointer to the rest of the list after node n!

Also note that, in order to follow the steps shown in the picture above, we needed to use variable tmp to create the new node (in the picture, step 1 shows the new node just "floating" there, but that isn't possible -- we need to have some variable point to it so that we can set its next field, and so that we can set n's next field to point to it). However, we could in fact accomplish steps 1 and 2 with a single statement that creates the new node, fills in its data and next fields, and sets n's next field to point to the new node! Here is that amazing statement:

n.setNext( new Listnode(newdat, n.getNext()) );  // steps 1, 2(a), and 2(b)

Removing a node

Note that the fact that n's next field is still pointing to a node in the list doesn't matter -- n has been removed from the list, because it cannot be reached from L. It should be clear that in order to implement the remove operation, we first need to have a pointer to the node before node n (because that node's next field has to be changed). The only way to get to that node is to start at the beginning of the list. We want to keep moving along the list as long as the current node's next field is not pointing to node n. Here's the appropriate code:

Listnode tmp = L;
while (tmp.getNext() != n) tmp = tmp.getNext();  // find the node before n

Note that this kind of code (moving along a list until some condition holds) is very common. For example, similar code would be used to implement a lookup operation on a linked list (an operation that determines whether there is a node in the list that contains a given piece of data).

Note also that there is one case when the code given above will not work. When n is the very first node in the list, the picture is like this:

In this case, the test (tmp.getNext() != n) will always be false, and eventually we will "fall off the end" of the list (i.e., tmp will become null, and we will get a runtime error when we try to dereference a null pointer). We will take care of that case in a minute; first, assuming that n is not the first node in the list, here's the code that removes n from the list:

Listnode tmp = L;
while (tmp.getNext() != n) tmp = tmp.getNext();  // find the node before n 
tmp.setNext( n.getNext() );                      // remove n from the linked list

How can we test whether n is the first node in the list, and what should we do in that case? If n is the first node, then L will be pointing to it, so we can test whether L == n. The following before and after pictures illustrate removing node n when it is the first node in the list:

Note that if your linked lists do include a header node, there is no need for the special case code given above for the remove operation; node n can never be the first node in the list, so there is no need to check for that case. Similarly, having a header node can simplify the code that adds a node before a given node n.

Note that if you do decide to use a header node, you must remember to initialize an empty list to contain one (dummy) node, you must remember not to include the header node in the count of "real" nodes in the list (e.g., if you implement a size operation), and you must remember to ignore the header node in operations like contains.

The disadvantage of this approach is that it requires O(N) time to add a node to the end of a list with N items. An alternative is to add a lastNode field (often called a tail pointer) to the List class, and to implement the methods that modify the linked list so that lastNode always points to the last node in the linked list (which will be the header node if the list is empty). There is more opportunity for error (since several methods will need to ensure that the lastNode field is kept up to date), but the use of the lastNode field will mean that the worst-case running time for this version of add is always O(1).

Here's a picture of the "ant, bat, cat" list, when the implementation includes a lastNode pointer:

1. Listnode items (the pointer to the header node)
2. Listnode lastNode (the pointer to the last node in the list)
3. int numItems

• space requirements
• time requirements
• ease of implementation

• In the linked-list implementation, one pointer must be stored for every item in the list, while the array stores only the items themselves.
• On the other hand, the space used for a linked list is always proportional to the number of items in the list. This is not necessarily true for the array implementation as described: if a lot of items are added to a list and then removed, the size of the array can be arbitrarily greater than the number of items in the list. However, we could fix this problem by modifying the remove operation to shrink the array when it becomes too empty.

• The array implementation requires O(N) worst-case time to add or remove an item in a list with N items, because existing items need to be moved. It requires only constant time to get an item from a given position.
• In contrast, adding items to the end of a linked list can be implemented to require only O(1) time (if we maintain a pointer to the last node in the list). Adding items at a given position, and removing the item at a given position will still take O(N) time in the worst case. Furthermore, getting an item from a given position pos takes O(pos) time (which in the worst case is O(N)), because we need to traverse the list, start at the beginning, until we reach the specified position.

In terms of ease of implementation, straightforward implementations of both the array and linked-list versions seem reasonably easy. However, the methods for the linked-list version seem to require more special cases, and achieving O(1) time for adding to the end of the list in the linked-list version requires maintaining an extra pointer (to the last node).

1. doubly linked lists
2. circular linked lists

Another way to fix the problem is to use a doubly linked list. Here's the conceptual picture:

Each node in a doubly linked list contains three fields: the data, and two pointers. One pointer points to the previous node in the list, and the other pointer points to the next node in the list. The previous pointer of the first node, and the next pointer of the last node are both null. Here's the Java class definition for a doubly linked list node:

public class DblListnode {
  //*** fields ***
    private DblListnode prev;
    private Object data;
    private DblListnode next;

  //*** methods ***
    // 3 constructors
    public DblListnode() {
	this(null, null, null);
    }

    public DblListnode(Object d) {
	this(null, d, null);
    }

    public DblListnode(DblListnode p, Object d, DblListnode n) {
        prev = p;
	data = d;
	next = n;
    }

    // access to fields
    public Object getData() {
        return data;
    }

    public DblListnode getNext() {
        return next;
    }

    public Object getPrev() {
        return prev;
    }

    // modify fields
    public void setData(Object ob) {
        data = ob;
    }

    public void setNext(DblListnode n) {
        next = n;
    }

    public void setPrev(DblListnode p) {
        prev = p;
    }
}

To remove a given node n from a doubly linked list, we need to change the prev field of the node to its right, and we need to change the next field of the node to its left, as illustrated below.

Here's the code for removing node n:

// Step 1: change the prev field of the node after n
  DblListnode tmp = n.getNext();
  tmp.setPrev( n.getPrev() );

// Step 2: change the next field of the node before n
  tmp = n.getPrev();
  tmp.setNext( n.getNext() );

The class definitions are the same as for the non-circular versions. The difference is that, instead of being null, the next field of the last node points to the first node, and (for doubly linked circular lists) the prev field of the first node points to the last node.

The code given above for removing node n from a doubly linked list will work correctly except when node n is the first node in the list. In that case, the variable L that points to the first node in the list needs to be updated, so special-case code will always be needed unless the list includes a header node.

Another issue that you must address if you use a circular linked list is that if you're not careful, you may end up going round and round in circles! For example, what happens if you try to search for a particular value val using code like this:

Listnode tmp = L;
while (tmp != null && !tmp.getData().equals(val)) tmp = tmp.getNext();

The major advantage of doubly linked lists is that they make some operations (like the removal of a given node, or a right-to-left traversal of the list) more efficient.

The major advantage of circular lists (over non-circular lists) is that they eliminate some special-case code for some operations. Also, some applications lead naturally to circular list representations. For example, a computer network might best be modeled using a circular list.