How to Create a Linked List Data Structure in Java

How do I create a Linked List Data Structure in Java?

The obvious solution to developers familiar to Java is to use the LinkedList class already provided in java.util. Say, however, you wanted to make your own implementation for some reason. Here is a quick example of a linked list that inserts a new link at the beginning of the list, deletes from the beginning of the list and loops through the list to print the links contained in it. Enhancements to this implementation include making it a double-linked list, adding methods to insert and delete from the middle or end, and by adding get and sort methods as well.

Note: In the example, the Link object doesn't actually contain another Link object - nextLink is actually only a reference to another link.

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    //Link constructor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    //Print Link data
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

class LinkList {
    private Link first;

    //LinkList constructor
    public LinkList() {
        first = null;
    }

    //Returns true if list is empty
    public boolean isEmpty() {
        return first == null;
    }

    //Inserts a new Link at the first of the list
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    //Deletes the link at the first of the list
    public Link delete() {
        Link temp = first;
        if(first == null){
         return null;
         //throw new NoSuchElementException(); // this is the better way. 
        }
        first = first.nextLink;
        return temp;
    }

    //Prints list data
    public void printList() {
        Link currentLink = first;
        System.out.print("List: ");
        while(currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}  

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        list.printList();

        while(!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("deleted: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

How to implement my own LinkedListLinkedList data structure in Java?

A generic LinkedList just substitutes the type of the value. You don't show your Node class so I don't understand how you're using it. Here is a generic linked list:

class LinkedList<E> {
    static class Node<E> {
        E value;
        Node<E> next;

        Node(E value) {
            this.value = value;
        }
    }

    Node<E> head = new Node<E>(null);
    Node<E> tail = head;
    int size;

    void add(E value) {
        tail = tail.next = new Node<E>(value);
        size++;
    }

    E get(int index) {
        if(index < 0 || size <= index)
            throw new OutOfBoundsException(index);

        Node<E> node = head.next;
        while(index > 0) {
            node = node.next;
            index--;
        }

        return node.value;
    }
}

But I'm not sure what you mean by make that in to an ArrayList. An ArrayList is completely different, it is an array that resizes itself automatically:

class ArrayList<E> {
    Object[] array = new Object[10];
    int size;

    void add(E value) {
        if(size >= array.length) {
            array = Arrays.copyOf(array, (int)(size * 3L / 2L));
        }

        array[size++] = value;
    }

    E get(int index) {
        return (E)array[index];
    }
}

And while I suppose you could hack together a hash table by using a multidimensional array, I don't recommend it. You cannot just go and instantiate an array with 2^32 elements so that means you have to manage intersections. I don't see how an ArrayList<ArrayList> could ever be a working hash table. Here is a simple hash table implementation similar to the Java one. The table is an array of linked lists.

class HashTable<K, V> {
    static class Entry<K, V> {
        K key;
        V value;

        Entry<K, V> next;

        Entry(K key, V value) {
           this.key = key;
           this.value = value;
        }
    }

    Entry[] table = new Entry[8];
    int size;

    void put(K key, V value) {
        Entry<K, V> entry = table[indexFor(key)];
        while(entry != null) {
            if(entry.key.equals(key)) {
                entry.value = value;
                return;
            }

            entry = entry.next;
        }

        resizeIfNeeded();

        addEntry(new Entry<K, V>(key, value));
        size++;
    }

    void addEntry(Entry<K, V> newEntry) {
        int index = indexFor(newEntry.key);
        Entry<K, V> entry = table[index];

        if(entry == null) {
            table[index] = newEntry;

        } else {
            while(entry.next != null)
                entry = entry.next;

            entry.next = newEntry;
        }
    }

    void resizeIfNeeded() {
        if(size < table.length)
            return;

        Entry[] old = table;
        table = new Entry[old.length << 1];

        for(Entry<K, V> entry : old) {
            while(entry != null) {
                addEntry(entry);
                Entry<K, V> next = entry.next;
                entry.next = null;
                entry = next;
            }
        }
    }

    V get(K key) {
        Entry<K, V> entry = table[indexFor(key)];
        while(entry != null) {
            if(entry.key.equals(key))
                return entry.value;

            entry = entry.next;
        }

        return null;
    }

    int indexFor(K key) {
        return key.hashCode() & table.length - 1;
    }
}

As I mentioned in my comment, this sounds like an XY problem. I don't see how this is easier than using the Java data structures. Perhaps you have a different question to ask.

singly-linked list data structure in Java

A handle to a linked list is always the head of the list. The code doesn't reverse the list. It only removes duplicates. More precisely, if temp.data is identical to temp.next.data, then temp.next is being removed.
The head of the list is never changed in this process, therefore it is correct to return the original head, since it is also the head of the modified list.

For instance, suppose the original list was head --> a --> b --> c, where head,a,b,c all denote nodes in the list, and suppose the the value of a is identical to the values of b. To remove duplicates, we effectively change the "next" pointer in a to point to c instead of b. This yields the modified list head --> a --> c. The head node of this list is identical to the head node of the original list, and this is why we return head.

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

Java linked list implementation

Linked lists are basic data structures.

A basic linked list implementation is as follows:

class LinkedListNode {
  int value;
  LinkedListNode next;
}

The basic idea is that you can iterate through the list by checking to see if the list has a next parameter, like so: while (currentNode.next != null) { ... }.

Printing out the values of a linked list takes advantage of the aforementioned while-loop, and you just print the value of the current node.

You can think of a linked list as a line of people who can only see the person ahead of them, and not who is behind them. You know where the person at the very start of the line -- that is, the one with nobody 'behind' him -- is. This person is called the "head" of the list. He knows who is directly in front of him, and each person knows who is directly in front of him. When you reach the point where somebody doesn't have anyone in front of them, you've gone through the whole line.

Here's an example of adding a new element to the end of a list:

LinkedListNode node = myListHead;
while (node.next != null) {
  node = node.next;
}
node.next = new LinkedListNode(...);

Creating a linked list in java is giving error, works for 3 elements but breaks on inserting the fourth

That's because

while(traverse.next != null) {
   traverse = head.next;
}

is an infinite loop. You're always assigning the same value to traverse as head doea not change. If that's not meeting the criteria to exit the loop, it will run forever.