More in The Data Structures series.

In the previous post, we saw how a stack can be implemented in Java. But as that was the first data structures post on this blog, I used an ArrayList internally. In this post, we’ll implement a simple Linked List in Java. Starting with this post, we’ll be getting serious about these data structure implementations. So we’ll write 100% custom implementation without using any built-in classes in Java. Also, I’m not going to explain how the data structures work. Which means, in this post, I’ll not have illustrations like I had for the stack implementation post explaining each step. So we’re going to jump right into the implementation from now on.

The Node

We know that any linked list will contain a node, which is the key component of the linked list. This node will have the actual value that is being stored, and also a pointer to the next node. Because this is a single linked list, we’ll have only one link in this node. We start the implementation with the Node itself, obviously.

There’s one thing to consider here. What type of value will we be storing in this node? Will it be an integer, or a string, or a custom data type? We have to make this decision when we’re writing the code, as we can’t really change this at run time. But what if we don’t know what type of data the user would want to store in this linked list? To make our linked list be able to store any type of data, we’ll use Java’s generic class, which is the T class. Using this, we can decide at run time what type of value a linked list should hold. We’ll define our node like this:

public class Node<T> {

    private T data;
    private Node<T> next;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

As you can see, we have the node class defined as Node<T>, the <T> in the definition indicates that the type of the value will be defined at run time. This node is the building block of the linked list. There will be number of such nodes linked together to make the linked list. let’s see how we can implement the linked list class now.

The Linked List

We’ll define our LinkedList class like this:

public class LinkedList<T> {

    private Node<T> head;

}

We have a head node, which will be the first node that will be inserted to the linked list. Any new node added to the linked list will become the new head. The previous head will be the next node to the new head. We now have to start adding various functions or operations that we can perform on a linked list. We’ll start with a function to add a new node to the linked list, and I’ll call this method push(), because why not?

public void push(T value) {

	// If there's no head, that means we're adding 
	// values to a new linked list. So we'll create a head.
    if (this.head == null) {

        this.head = new Node<T>();
        this.head.setData(value);

    } else {

    	// If there's already a head, we'll create a new node,
    	// and make the new node's "next" point to the current 
    	// head of the linked list, and then make the new node
    	// the new head.
    	
        Node<T> newNode = new Node<T>();
        newNode.setData(value);
        newNode.setNext(this.head);
        this.head = newNode;

    }
}

I think this method is self-explanatory. We’re adding a new head every time we’re pushing a new value to the linked list. Next, we need to be able to traverse a linked list, as that is one of the main features of a linked list. While traversing a single linked list, we start with the head node and make our way to the end of the linked list. We start from the head because we have a reference only to the head of the linked list. The traversal method could be written like this:

public void traverse() {

    if (this.head != null) {

    	// We'll start the traversal from the head.
        Node<T> currentNode = this.head;

        // We'll continue the traversal until the currentNode becomes null,
        // which means we have reached the end of the linked list.
        while (currentNode != null) {
            System.out.print(currentNode.getData() + " -> ");

            // We're moving to the next node here.
            currentNode = currentNode.getNext();
        }

        System.out.println("END");

    } else {
        System.out.println("Linked list is empty.");
    }
}

I have added comments in the method to make it clear what we’re doing there. If something is not very clear or you need help understanding it, please let me know in the comments below.

Next, we need to be able to delete a node from the linked list. If I give a value, we have to traverse the linked list till we find the node with that value, point the previous node’s next to the current node’s next, so that when we delete the current node, we don’t lose every other node after it, we still need to have the linked list intact. The logic for this could look a bit intimidating at first, but if you try and understand it, it’s so very simple.

public void delete(T value) {

	// We can delete a value only if the linked list is not empty.
    if (this.head != null) {
    	// Because we have the reference of only the head node, we'll assume that 
    	// both the currentNode and the previousNode is the head node.
        Node<T> currentNode = this.head;
        Node<T> previousNode = this.head;

        // We'll continue the loop until the currentNode becomes null,
        // which would mean that we've reached the end of the linked list.
        while (currentNode != null) {

        	// If the current node's value is the same as the value that we want to
        	// delete, it means that we have the node that we have to delete.
            if (currentNode.getData() == value) {
            	// In which case, we're linking the previous node's next() to the
            	// current node's next(). Doing this will by default delete the
            	// current node as we'll lose the reference to that node.
                previousNode.setNext(currentNode.getNext());

                System.out.println("Deleted first node with value " + value);

                // We'll break the while loop now as we don't need to traverse anymore.
                break;
            } else {
                previousNode = currentNode;
                currentNode = currentNode.getNext();
            }
        }
    }
}

We can add more functionality to this linked list class we have, such as add a node to the tail (end) of the linked list, add a node after a given index, delete a node at a given index, or delete a node after a given index. They are all pretty simple functions. I have the code for all these here.

Add a node to the tail

public void addToTail(T value) {

	// If the head is null, that means the linked list is empty.
	// So we just add one node and make it the head and tail.
    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);
    } else {

        Node<T> lastNode = this.head;

        // We assume that the last node in the linked list in the head.
        // We traverse the node untill the next node is null, which means 
        // we're at the last node. We'll add a new node now, and point the
        // current last node's 'next' to the new node.
        while (lastNode.getNext() != null) {
            lastNode = lastNode.getNext();
        }

        Node<T> newNode = new Node<T>();
        newNode.setData(value);

        lastNode.setNext(newNode);
    }
}

Add a node after a given index

public void addAfterIndex(T value, int index) {

    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);
    } else {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;

        while (index > nodeIndex) {
            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        if (nodeIndex == index) {
            Node<T> newNode = new Node<T>();
            newNode.setData(value);
            newNode.setNext(currentNode.getNext());

            currentNode.setNext(newNode);
        }
    }
}

Delete a node at a given index

public void deleteNodeAtIndex(int index) {

    if (this.head != null) {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;
        Node<T> previousNode = this.head;

        while (nodeIndex != index) {

            previousNode = currentNode;

            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        previousNode.setNext(currentNode.getNext());
    }
}

Delete a node after a given index

public void deleteNodeAfterIndex(int index) {

    if (this.head != null) {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;

        while (nodeIndex != index) {

            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        if (currentNode.getNext() != null) {
            currentNode.setNext(currentNode.getNext().getNext());
        } else {
            currentNode.setNext(null);
        }
    }
}

Creating a LinkedList

Now let’s see how we can create a LinkedList with the class we just wrote. In my main() method, I’m creating a new LinkedList object and calling a few methods on it:

public static void main(String[] args) {

    LinkedList<Integer> linkedList = new LinkedList<>();

    linkedList.push(1);
    linkedList.push(2);
    linkedList.push(3);

    linkedList.addToTail(4);

    linkedList.push(1);
    linkedList.push(2);
    linkedList.push(3);

    System.out.println("Traversing linked list");
    linkedList.traverse();

    System.out.println("Deleting first node with value 2");
    linkedList.delete(2);

    System.out.println("Traversing linked list after deletion");
    linkedList.traverse();

    System.out.println("Adding value 5 after the node with index 1");
    linkedList.addAfterIndex(5, 1);

    System.out.println("Traversing linked list after adding new node after index 1.");
    linkedList.traverse();

    System.out.println("Deleting node at index 2");
    linkedList.deleteNodeAtIndex(2);

    System.out.println("Traversing linked list after deleting node at index 2.");
    linkedList.traverse();

    System.out.println("Deleting node after index 3");
    linkedList.deleteNodeAfterIndex(3);

    System.out.println("Traversing linked list after deleting node after index 3.");
    linkedList.traverse();
}

The output of this code will be like this:

Traversing linked list
3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Deleting first node with value 2
Deleted first node with value 2
Traversing linked list after deletion
3 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Adding value 5 after the node with index 1
Traversing linked list after adding new node after index 1.
3 -> 1 -> 5 -> 3 -> 2 -> 1 -> 4 -> END
Deleting node at index 2
Traversing linked list after deleting node at index 2.
3 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Deleting node after index 3
Traversing linked list after deleting node after index 3.
3 -> 1 -> 3 -> 2 -> 4 -> END

I hope the explanation was clear. If not, as always, will be more than happy to help if you have any questions. Please leave them below in the comments. And if you want to look at a working project using this LinkedList, feel free to fork my project on Github.