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:

  1. Keep a pointer to the current node.
  2. Loop through the list until we find one where current has the data we're looking for.
  3. If current.prev is not null, set current.prev.next to current.next
  4. Else, set head to current.next
  5. If current.next is not null, set current.next.prev to current.prev
  6. 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:

Advantages of Arrays: