taylorialcom/ DataStructures

Linked Lists

A LinkedList stores a collection of references to objects.

Overview

A LinkedList is a data structure that organizes the data contained within it by making each location, called a node, responsible for holding references to its immediate neighbors in the list (along with a reference to the actual data we wish to store in the list). It's a fascinating data structure, but before we get too far, it's time for a quiz. What do the following photos have in common?

images? above about the similar What is

If you answered that each individual is balancing an object on his/her head, you are half way to understanding the linked list. Just for fun, we'll call each person in the photos above a node. A node is something that can keep track of an object (by balancing it on his/her head, in this case).

But nodes can do more than just keep track of an object. Consider the following nodes...

http://www.flickr.com/photos/bijapuri/4737039561/

Each node here is holding the hand of his/her two closest neighbors. This is cool, but not nearly as cool as it would be if each was balancing an object on his/her head. Shut your eyes and see if you can imagine objects appearing on their heads? If so, you've just realized two things: 1) pretty much how a linked list works and 2) that it really is cool.

The LinkedList itself just manages how to get to the front of the chain of nodes and the back of the chain of nodes. Essentially, the LinkedList contains two attributes:

  1. head — a reference to the node at the beginning of the list and
  2. tail — a reference to the node at the end of the list.

In Pictures

Our LinkedList keeps track of the first (or head) node and the last (or tail) node. Each node is responsible for holding hands with its neighbors. Of course, if you don't have a neighbor, leaving your hand dangling in the air just looks stupid, so our stick figures put their hand(s) in their pocket(s) to signify that they don't have a neighbor.

A LinkedList containing one diamond consists of a reference to the head and tail (which happen to be the same thing) and one node balancing a diamond on its head and both hands in its pockets.

LinkedList with One Element

A LinkedList with two diamonds in it consists of a head pointing to the first node and a tail pointing to the last node. As expected, the two nodes hold hands because they are neighbors. I can get to the second element in my list by either going directly to it (through the tail reference) or by going to the first element and asking it for its next neighbor.

LinkedList with Two Elements

If we add a fat diamond to the LinkedList above it will look something like this:

LinkedList with Three Elements

I can't get to the second element directly now. I either have to go the the first element and ask to see its next neighbor or go to the last element and ask to see its previous neighbor. Either way, it is bound to be a lot of fun, but I've heard it's hard to balance without a big toe, and these guys don't have any toes. Having them balance diamonds on their heads seems like a lot to ask, even if they aren't real diamonds, so in the rest of this discussion we'll draw the LinkedList and Node objects in a way that describes what's going on in memory.

In Textbookish Pictures

Empty LinkedList
Figure 1: Empty LinkedList
LinkedList with One Element
Figure 2: LinkedList with One Element
LinkedList with Two Elements
Figure 3: LinkedList with Two Elements
LinkedList with Three Elements
Figure 4: LinkedList with Three Elements

In Code

In Java, we declare the LinkedList<E> as implementing the List<E> interface and define an inner Node class like this:

public class LinkedList<E> implements List<E> {

    private Node<E> head;
    private Node<E> tail;

    private static class Node<E> {
        private E value;
        private Node<E> next;
        private Node<E> prev;

        public Node(E val, Node<E> nxt, Node<E> prv) {
            value = val;
            next = nxt;
            prev = prv;
        }
    }

    public LinkedList() {
        head = null;
        tail = null;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
    }
    // ...

Introduction to add() (to the end)

If the list is empty, adding an element involves

  1. creating a Node with no neighbors and the element referenced as its value.
  2. Make the head of our list refer to the newly created node
  3. Make the tail of our list refer to the newly created node

You can see this in the code below and the graphic below the code.

If the list has at least one element, then we leave the head of the list alone. Here we need to:

  1. Make the currently last node, tail, have its next neighbor be the newly created node
  2. Make the tail of our list refer to the newly created node

In Code

    @Override
    public boolean add(E element) {
        Node<E> newNode = new Node(element, null, tail);  // 1
        if(head == null) {
            head = newNode;                               // 2
            tail = newNode;                               // 3
        } else {
            tail.next = newNode;                          // 4
            tail = newNode;                               // 5
        }
        return true;
    }

In Pictures

Red indicates what it looked like before the addition and green indicates what it looks like after the addition.

Adding to an Empty LinkedList
Figure 5: Adding to an Empty LinkedList
Adding to a Non-Empty LinkedList
Figure 6: Adding to a Non-Empty LinkedList

In Song

Fa la la la la

isEmpty() and size()

In Code

    @Override
    public boolean isEmpty() {
        return head == null;
    }

    @Override
    public int size() {
        int count = 0;
        Node<E> walker = head;
        while(walker != null) {
            walker = walker.next;
            ++count;
        }
        return count;
    }

Secret Time

    private Node<E> walkTo(int index) {
        if(index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index);
        }
        Node<E> walker = head;
        int i = 0;
        try {
            for(; i < index; ++i) {
                walker = walker.next;
            }
        } catch(NullPointerException e) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + i);
        }
        return walker;
    }
    @Override
    public E get(int index) {
        Node<E> node = walkTo(index);
        if(node==null) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + index);
        }
        return node.value;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = walkTo(index);
        if(node==null) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + index);
        }
        E oldValue = node.value;
        node.value = element;
        return oldValue;
    }

Introduction to add() with an Index

In Code

    @Override
    public void add(int index, E element) {
        Node<E> node = walkTo(index);                                // 1
        if(node==null) {               // At end of list
            add(element);
        } else if(node.prev == null) { // At beginning of list
            Node<E> newNode = new Node(element, node, null);         // 2
            node.prev = newNode;                                     // 3
            head = newNode;                                          // 4
        } else {                       // Somewhere in middle of list
            Node<E> newNode = new Node(element, node, node.prev);    // 5
            node.prev = newNode;                                     // 6
            newNode.prev.next = newNode;                             // 7
        }
    }

In Pictures

Adding to the Beginning of a LinkedList
Figure 7: Adding to the Beginning of a LinkedList
Adding to the Middle of a LinkedList
Figure 8: Adding to the Middle of a LinkedList

Iterators and the LinkedList

In Code

    private class LLIterator implements ListIterator<E> {

        private Node<E> location;
        private int index;
        private boolean isModifiable;

        private LLIterator() {
            location = new Node(null, head, null);
            index = -1;
            isModifiable = false;
        }

ListIterator.hasNext/Previous()

        @Override
        public boolean hasNext() {
          return location.next != null;
        }

        @Override
        public boolean hasPrevious() {
            return index != -1;
        }

ListIterator.next/previousIndex() and ListIterator.set()

        @Override
        public int nextIndex() {
            return index + 1;
        }

        @Override
        public int previousIndex() {
            return index;
        }

        @Override
        public void set(E element) {
            if(!isModifiable) {
                throw new IllegalStateException("Must call next or previous before remove");
            }
            location.value = element;
        }

ListIterator.next/previous()

        @Override
        public E next() {
            if(!hasNext()) {
                throw new NoSuchElementException("No next element available.");
            }
            isModifiable = true;
            location = location.next;
            ++index;
            return location.value;
        }

        @Override
        public E previous() {
            if(!hasPrevious()) {
                throw new NoSuchElementException("No next element available.");
            }
            E value = location.value;
            if(index == 0) {
                location = new Node(null, head, null);
                index = -1;
                isModifiable = false;
            } else {
                location = location.prev;
                --index;
                isModifiable = true;
            }
            return value;
        }

ListIterator.remove()

In Code

        @Override
        public void remove() {
            if(!isModifiable) {
                throw new IllegalStateException("Must call next or previous before remove");
            }
            if(location.prev == null) {  // At beginning of list
                LinkedList.this.head = location.next;        // 1
            } else {                     // In middle of list
                location.prev.next = location.next;          // 2
            }
            if(location.next == null) {  // At end of list
                LinkedList.this.tail = location.prev;        // 3
            } else {                     // In middle of list
                location.next.prev = location.prev;          // 4
            }
            isModifiable = false;
        }

        @Override
        public void add(E element) {
            throw new UnsupportedOperationException("ListIterator.add() not supported.");
        }

    }

In Pictures

Removing the Only Element from a LinkedList
Figure 9: Removing the Only Element from a LinkedList
Removing the First Element from a LinkedList
Figure 10: Removing the First Element from a LinkedList
Removing an Element from the Middle of a LinkedList
Figure 11: Removing an Element from the Middle of a LinkedList

Meanwhile, back in the outer class, i.e., the LinkedList class, we've got more to do. We can implement the iterator-related methods:

    @Override
    public Iterator<E> iterator() {
        return new LLIterator();
    }

    @Override
    public ListIterator<E> listIterator() {
        return new LLIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        if(index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index);
        }
        ListIterator<E> itr = new LLIterator();
        int i = 0;
        try {
            for(; i < index; ++i) {
                itr.next();
            }
        } catch(NoSuchElementException e) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + i);
        }
        return itr;
    }

LinkedList.remove()

    @Override
    public E remove(int index) {
        ListIterator<E> itr = listIterator(index);
        E value = itr.next();
        itr.remove();
        return value;
    }
    @Override
    public boolean remove(Object target) {
        boolean removed = false;
        ListIterator<E> itr = listIterator();
        while(!removed && itr.hasNext()) {
            if(target.equals(itr.next())) {
                itr.remove();
                removed = true;
            }
        }
        return removed;
    }

    @Override
    public boolean contains(Object target) {
        Iterator<E> itr = iterator();
        boolean found = false;
        while(!found && itr.hasNext()) {
            found = target.equals(itr.next());
        }
        return found;
    }

    @Override
    public int lastIndexOf(Object target) {
        int index = size();
        ListIterator<E> itr = listIterator(index);
        boolean found = false;
        while(!found && itr.hasPrevious()) {
            found = target.equals(itr.previous());
            --index;
        }
        if(!found) {
            index = -1;
        }
        return index;
    }
1

Later we'll see that an iterator is designed to provide very similar functionality, but we're going to build up to that gradually.

2

... posting it on the internet for the world to see is probably not helping ensure secrecy here.

3

Because NullPointerException would be caused by walking off the end of the list, which will only happen if we are given an index that is too large for our list.

4

With our implementation, we can't easily use the index to implement hasNext() since we didn't include a size attribute in the LinkedList class. We could call size(), doing something like: return index < size()-1; but that wouldn't be very efficient. Do you know why? You should.