Creating a LinkedList class from scratch

Question

We were given an assignment to create a LinkedList from scratch, and there are absolutely no readings given to guide us on this migrane-causing task. Also everything online seems to just use Java's built in LinkedList methods and stuff. Anyway, linked lists make perfect sense when using Java's default stuff, but creating it from scratch makes no sense whatsoever. Lets say I have

public class LinkedList {
  private LinkedList next;  
  private final String word;
  // constructor
  public LinkedList(String word, LinkedList next) {
    this.word = word;
    this.next = next;
  }

And thus magically we have a linked list. What is going on? How have I created a linked list like this? How does this work? I'm supposed to write an append method that adds a the given String word parameter to the end of this linkedlist. I tried looking at the addLast built in method for built in java linkedlist class, but it's no help to me, as I really dont understand whats going on. Anyone care to help me out :)

Answer 1

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:

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.}