Creating a LinkedList class from scratch

If you’re actually building a real system, then yes, you’d typically just use the stuff in the standard library if what you need is available there. That said, don’t think of this as a pointless exercise. It’s good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don’t exist in the standard libraries.

There are some differences between the way you’re creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you’re building a singly linked list. What you’re doing is more appropriate for a class assignment.

With your LinkedList class, an instance will always be a list of at least one element. With this kind of setup you’d use null for when you need an empty list.

Think of next as being “the rest of the list”. In fact, many similar implementations use the name “tail” instead of “next”.

Here’s a diagram of a LinkedList containing 3 elements:

linked list diagram

Note that it’s a LinkedList object pointing to a word (“Hello”) and a list of 2 elements. The list of 2 elements has a word (“Stack”) and a list of 1 element. That list of 1 element has a word (“Overflow”) and an empty list (null). So you can treat next as just another list that happens to be one element shorter.

You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.

To append, you check if next is null. If it is, create a new one element list and set next to that.

next = new LinkedList(word);

If next isn’t null, then append to next instead.

next.append(word);

This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java*, and wouldn’t risk a stack overflow with very long lists, but I’m guessing that level of complexity isn’t needed for your assignment.


* Some languages have tail call elimination, which is an optimization that lets the language implementation convert “tail calls” (a call to another function as the very last step before returning) into (effectively) a “goto”. This makes such code completely avoid using the stack, which makes it safer (you can’t overflow the stack if you don’t use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.

Leave a Comment