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.