Doubly Linked Lists Continued

Looping Through

Looping through the doubly linked list forwards is exactly the same as it was with the singly linked list:


// loop through the list forwards
void print() {
    Node current = head;
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
}

Looping through the list backwards is much easier now, however. We can use the tail reference, along with the "prev" links, to loop through backwards just as easily as forwards:


// loop through the list backwards
void printBackwards() {
    Node current = tail;
    while (current != null) {
        System.out.println(current.data);
        current = current.prev;
    }
}

Deleting Nodes

Deleting a node is also much the same as for a singly-linked list, but we have to make sure that we make, not only the next pointer route around the deleted node, but also the prev pointer. Another difference is that we do not need to keep two pointers as well search, but only one — since the previous is now easy to find:

Keep a pointer to the current node.
Loop through the list until we find one where current has the data we're looking for.
If current.prev is not null, set current.prev.next to current.next
Else, set head to current.next
If current.next is not null, set current.next.prev to current.prev
Else, set tail to current.prev

Below is this algorithm implemented in Java:


public void remove(Type value) {
    Node current = head;
    while (current != null) {
        // if we found the node
        if (current.data.equals(value)) {

            if (current.prev != null) {
                current.prev.next = current.next;
            } else {
                head = current.next;
            }

            if (current.next != null) {
                current.next.prev = current.prev;
            } else {
                tail = current.prev;
            }

            return;
        }

        // move on to the next one
        current = current.next;
    }
}

The code for this doubly-linked list is available in DoubleList.java.

Linked Lists vs. Arrays

Linked lists and arrays both store data. So how would we decide which one to use to store something in our program?

The choice of which data structure to use has a huge impact on our programs in terms of efficiency. Some operations are much faster with an array and some are much faster with a linked list.

Advantages of Linked Lists:

Nodes can be inserted at any point quickly.
Nodes can be deleted quickly.
Linked lists can expand and shrink more easily.

Advantages of Arrays:

Arrays can be indexed directly.
Arrays take less space (no need to store an extra references for each element).
Arrays can be looped through more quickly.