Java Using Nodes with LinkedList

You don’t actually need a separate LinkedList class; the ListNode class is a linked list. Or, to state it differently, a reference to the head of the list is a reference to the list.

The use of head, tail, current, prev in the sample code you posted has come from a double-linked list which is a data type that has links in both directions. This is more efficient for certain types of applications (such as finding the nth last item).

So I would recommend renaming your ListNode class to LinkedList and renaming next to tail.

To add a new item to the list you need a method that creates a new list with the new item at it’s head. Here is an example:

class LinkedList<E> {
    ...

    private LinkedList(E value, LinkedList<E> tail) {
        this.data = value;
        this.tail = tail;
    }

    public LinkedList<E> prependItem(E item) {
        return new LinkedList(item, this);
    }
}

Then to add a new item i to list you use list = list.prependItem(i);

If for some reason you need to always add the items to the end, then:

private LinkedList(E value) {
    this.data = value;
    this.tail = null;
}

public void appendItem(E item) {
    LinkedList<E> list = this;
    while (list.tail != null)
        list = list.tail;
    list.tail = new LinkedList<>(item);
}

However this is obviously pretty inefficient for long lists. If you need to do this then either use a different data structure or just reverse the list when you have finished adding to it.

Incidentally, an interesting side effect of this is that a reference to any item in the list is a reference to a linked list. This makes recursion very easy. For example, here’s a recursive solution for finding the length of a list:

public int getLength(LinkedList list) {
    if (list == null) {
        return 0;
    } else {
        return 1 + getLength(list.getTail());
    }
}

And using this a simple (but very inefficient!) solution to the problem you provided – I’ve renamed the method to make its function more obvious:

public LinkedList getTailOfListOfLengthN(LinkedList list, int n) {
    int length = getLength(list);
    if (length < n) {
        return null;
    } else if (length == n) {
        return list;
    } else {
        return getTailOfLengthN(list.getTail(), n);
    }
}

And to reverse the list:

public LinkedList<E> reverse() {
    if (tail == null) {
        return this;
    } else {
        LinkedList<E> list = reverse(tail);
        tail.tail = this;
        tail = null;
        return list;
    }
}

As I hope you can see this makes the methods a lot more elegant than separating the node list classes.

Leave a Comment Cancel reply