Linked Lists Continued

Adding to the End

When we added to the start of our linked list, we ended up with the list being the reverse of what we might expect.

Adding to the end of a linked list is more complicated than adding to the beginning because we have to loop through to find the last node in the list first.

How could we write a method to add to the end?


// add an item to the end of the list
public void append(Type item) {
    // if the list is empty, add it to the start instead
    if (head == null) {
        add(item);
    } else {
        // make the new node
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = null;

        // find the last node in the list
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }

        // append the new node to the last one
        last.next = newNode;
    }
}

Removing a Node

So now we have a Linked List class that we can add data to, and access. What if we want to delete elements from the list? The ease of deleting elements is one of the biggest advantages of a linked list.

The following code removes an item by its value.


// remove an item based on the value
public void remove(Type item) {
    // we need to track the node before the one we'll get rid of
    Node current = head;
    Node prev = null;

    // loop through and find the one to delete
    while (current != null) {
        if (current.data.equals(item)) {
            if (prev == null) {
                head = current.next;
            } else {
                prev.next = current.next;
            }
            return;
        }

        // move on to the next node
        prev = current;
        current = current.next;
    }
}

We can also remove items by their index in the array:


// remove an item based on its index
public void remove(int index) {
    // we again will keep track of the previous node
    Node current = head;
    Node prev = null;

    // loop through until we get to this node's index
    for (int i = 0; i < index; i++) {
        if (current == null) {
            return;
        }

        prev = current;
        current = current.next;
    }

    // bypass it
    if (prev == null) {
        head = current.next;
    } else {
        prev.next = current.next;
    } 
}

Looping Through Backwards

How could we loop through the Linked List backwards? This is challenging with the linked list that we currently have.

The easiest way to do this is with recursion:


// print the list backwards recursively
public void printBackwards(Node node) {
    if (node != null) {
        printBackwards(node.next);
        System.out.println(node.data);
    }
}

// call the helper function to print backwards starting from the head
public void printBackwards() {
    printBackwards(head);
}

Conclusion

The complete code is available here: LinkedList4.java. There are a few flaws with linked lists the way we have it:

Adding to the end is not so efficient as adding to the front.
It's hard to know what node comes before another one, making the remove method awkward.
Looping backwards is awkward and slow.

Next week we will look at doubly linked lists which will make it easier to deal with the end of the linked list, and loop through lists backwards.