Implementing a Linked List in Java Using Class

Introduction

Linked list is a hot-selling topic in terms of interview preparation and to have a solid grip on such a topic makes you the upper hand during an interview. Linked lists can be implemented using languages like C++ and Java.

So, let us look at some crucial operations that are performed while implementing a linked list in Java using class.

See, Advantages and Limitations of Linked Lists and Rabin Karp Algorithm

Creating a node

A linked list consists of a node, which contains 2 parts:

Data → Contains data to be stored in that particular node.
Pointer to the next node → Contains address to the next node.

A linked list is a collection of such nodes. The first node is termed the HEAD node, and the last node is called the TAIL node of the linked list.

In Java, a node can be represented as a separate class as shown below:

// Linked list Node.
class Node {
    public int data;
    public Node next;

    // Constructor to create a new node.
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Insertion

There are three options for insertion in a linked list. They have been discussed below:

Insertion at the beginning of the list

Algorithm

First, create a new node, NEW_NODE that needs to be inserted at the beginning of the linked list.
Then, we will make NEXT of NEW_NODE to point to the HEAD node.
Since the new node will now become the first node, we will make HEAD point to the NEW_NODE.

Program

// Java program to insert a node at the end of the linked list.
// Linked list node.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Linked List Class.
public class LinkedList {
    public Node head = null;
    public Node tail = null;

    // Function for inserting a new node at the end of the linked list.
    public void insertAtBeginning(int data) {
        System.out.println("Inserting a new node having value " + data + " at the beginning of the linked list.");
       
        // Creation of a new node.
        Node newNode = new Node(data);

        // If this is the first node, set it as 'TAIL' node.
        if (head == null) {
            tail = newNode;
        }

        // Changing 'NEXT' of 'NEW_NODE' to point to 'HEAD'.
        newNode.next = head;

        // Updating 'HEAD'.
        head = newNode;
    }

    // Function to print the linked list.
    public void printList() {

        Node current = head;
        if (current == null) {
            System.out.println("Linked List is empty");
            return;
        }
        while (current != null) {
            // Pointer will be incremented subsequently.
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        // Creating a linked list (20 -> 60 -> 10 -> 80).
        LinkedList list = new LinkedList();

        // Adding element 50 at the beginning of the list.
        list.insertAtBeginning(50);
        list.printList();
 
        // Adding element 40 at the beginning of the list.
        list.insertAtBeginning(40);
        list.printList();
 
        // Adding element 30 at the beginning of the list.
        list.insertAtBeginning(30);
        list.printList();
 
        // Adding element 20 at the beginning of the list.
        list.insertAtBeginning(20);
        list.printList();
    }
}

Output

Inserting a new node having value 50 at the beginning of the linked list.
50 
Inserting a new node having value 40 at the beginning of the linked list.
40 50
Inserting a new node having value 30 at the beginning of the linked list.
30 40 50
Inserting a new node having value 20 at the beginning of the linked list.
20 30 40 50

Time Complexity

O(1)

Insertion at the end of the list

Algorithm

We will keep track of the last node with the help of a pointer, say TAIL, for inserting a node at the end of a linked list.
First, create a new node that needs to be inserted at the end of the linked list.
Then, we will check if the linked list is already empty or not by checking if HEAD points to NULL or not.
In case the linked list is empty, the new node will become the first node of our linked list.
Otherwise, the tail node that initially points to NULL will now point to this newly created node which will now point to NULL.

Program

// Java program to insert a node at the end of the linked list.
// Linked list node.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Linked List Class.
public class LinkedList {
    public Node head = null;
    public Node tail = null;

    // Function for inserting a new node at the end of the linked list.
    public void insertAtEnd(int data) {
        System.out.println("Inserting a new node having value " + data + " at the end of the linked list.");
       
        // Creation of a new node.
        Node newNode = new Node(data);

        // Checking whether this list is empty or not.
        if (head == null) {
            // In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
            head = newNode;
            tail = newNode;
        } else {
            // The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
            tail.next = newNode;

            // This 'NEW_NODE' will become the 'TAIL' of the linked list.
            tail = newNode;
        }
    }

    // Function to print the linked list.
    public void printList() {

        Node current = head;
        if (current == null) {
            System.out.println("Linked List is empty");
            return;
        }
        while (current != null) {
            // Pointer will be incremented subsequently.
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        // Creating a Linked List object.
        LinkedList list = new LinkedList();
 
        // Adding element 50 at the end of the list.
        list.insertAtEnd(50);
        list.printList();
 
        // Adding element 40 at the end of the list.
        list.insertAtEnd(40);
        list.printList();
 
        // Adding element 30 at the end of the list.
        list.insertAtEnd(30);
        list.printList();
 
        // Adding element 20 at the end of the list.
        list.insertAtEnd(20);
        list.printList();
    }
}

Output

Inserting a new node having value 50 at the end of the linked list.
50 
Inserting a new node having value 40 at the end of the linked list.
50 40 
Inserting a new node having value 30 at the end of the linked list.
50 40 30 
Inserting a new node having value 20 at the end of the linked list.
50 40 30 20

Time Complexity

O(N), where N is the number of nodes in the linked list.

Insertion at a specific position

Algorithm

First, create a node that needs to be inserted in the linked list.
If the specified position of insertion is 1, this new node is added before the HEAD node.
Otherwise, iterate up to the specified position and insert this new node at that position.

Program

// Java program to insert a node at the end of the linked list.

// Linked list node.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Linked List Class.
public class LinkedList {
    public Node head = null;
    public Node tail = null;

    // Function for inserting a new node at the end of the linked list.
    public void insertAtEnd(int data) {
        // Creation of a new node.
        Node newNode = new Node(data);

        // Checking whether this list is empty or not.
        if (head == null) {
            // In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
            head = newNode;
            tail = newNode;
        } else {
            // The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
            tail.next = newNode;

            // This 'NEW_NODE' will become the 'TAIL' of the linked list.
            tail = newNode;
        }
    }

    // To insert a node at a given position.
    void insertAtPos(int data, int pos) {
        Node current = head;
        if (pos < 1) {
            System.out.print("Invalid position");
            return;
        }

        if (pos == 1) {
            Node newNode = new Node(data);
            newNode.next = head;
            head = newNode;
        } else {
            while (pos-- != 0) {
                if (pos == 1) {
                    Node newNode = new Node(data);
                    newNode.next = current.next;
                    current.next = newNode;
                    return;
                }
                current = current.next;
            }
            if (pos != 1)
                System.out.print("Position out of bound");
        }
    }

    // Function to print the linked list.
    public void printList() {

        Node current = head;
        if (current == null) {
            System.out.println("Linked List is empty");
            return;
        }
        while (current != null) {
            // Pointer will be incremented subsequently.
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Creating a linked list (10 -> 20 -> 30 -> 40).
        LinkedList list = new LinkedList();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);

        System.out.print("Linked List before operations: ");
        list.printList();

        // Insert a new node at the fifth position.
        int data = 48, pos = 5;
        list.insertAtPos(data, pos);
        System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
        list.printList();

        // Inserting a new node at the third position.
        data = 29;
        pos = 3;
        list.insertAtPos(data, pos);
        System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
        list.printList();

        // Insert a new node at the sixth position.
        data = 44;
        pos = 6;
        list.insertAtPos(data, pos);
        System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
        list.printList();
    }
}

Output

Linked List before operations: 10 20 30 40 

Linked list after adding a new node having value 48 at the position 5 is: 10 20 30 40 48

Linked list after adding a new node having value 29 at the position 3 is: 10 20 29 30 40 48 

Linked list after adding a new node having value 44 at the position 6 is: 10 20 29 30 40 44 48

Time Complexity

O(N), where N is the number of nodes in the linked list.

Deletion

Algorithm

First, we will find the node for the key which has to be deleted.
There can be 3 conditions for this node:
HEAD node - In this case, the HEAD node will be deleted, and the next node will become the HEAD node.
Any other node - The previous node of the node to be deleted, will now point to the next node of the deleted node.
Key is not present in this linked list.

See, Deletion In Linked Lists

Program

// Java program to insert a node at the end of the linked list.

// Linked list node.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Linked List Class.
public class LinkedList {
    public Node head = null;
    public Node tail = null;

    // Function for inserting a new node at the end of the linked list.
    public void insertAtEnd(int data) {
        // Creation of a new node.
        Node newNode = new Node(data);

        // Checking whether this list is empty or not.
        if (head == null) {
            // In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
            head = newNode;
            tail = newNode;
        } else {
            // The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
            tail.next = newNode;

            // This 'NEW_NODE' will become the 'TAIL' of the linked list.
            tail = newNode;
        }
    }

    // Method to delete the node according to the given key.
    void deleteNode(int key)
    {
        // If list is empty.
        if (head == null) {
            System.out.println(key + " not found");
        }

        // If the key is found at the 'HEAD' of the list.
        if (head != null && head.data == key)
        {
            head = head.next;
            System.out.println(key + " is deleted");
            return;
        }

        Node current = head, prev = null;

        // If the key is not found at the head node.
        while (current != null && current.data != key)
        {
            prev = current;
            current = current.next;
        }

        // If the linked list does not contain the key.
        if (current == null)
        {
            System.out.println(key + " not found");
        }

        // If the linked list contains the key.
        if (current != null)
        {
            prev.next = current.next;
            System.out.println(key + " is deleted");
        }
    }

    // Function to print the linked list.
    public void printList() {

        Node current = head;
        if (current == null) {
            System.out.println("Linked List is empty");
            return;
        }
        while (current != null) {
            // Pointer will be incremented subsequently.
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        // Creating a linked list (20 -> 60 -> 10 -> 80 -> 90 -> 0 -> 30 -> 50).
        LinkedList list = new LinkedList();

        // Inserting values into an empty list.
        list.insertAtEnd(20);
        list.insertAtEnd(60);
        list.insertAtEnd(10);
        list.insertAtEnd(80);
        list.insertAtEnd(90);
        list.insertAtEnd(0);
        list.insertAtEnd(30);
        list.insertAtEnd(50);

        // Printing linked list before deletion.
        System.out.print("Linked list before deletion: ");
        list.printList();
        System.out.println();

        // Deleting some keys and printing the list accordingly.
        System.out.print("Linked list after deleting element 20: ");
        list.deleteNode(20);
        list.printList();
        System.out.println();

        System.out.print("Linked list after deleting element 80: ");
        list.deleteNode(80);
        list.printList();
        System.out.println();

        System.out.print("Linked list after deleting element 20: ");
        list.deleteNode(20);
        list.printList();
        System.out.println();
    }
}

Output

Linked list before deletion: 20 60 10 80 90 0 30 50 

Linked list after deleting element 20: 20 is deleted

60 10 80 90 0 30 50

Linked list after deleting element 80: 80 is deleted

60 10 90 0 30 50

Linked list after deleting element 20: 20 not found

60 10 90 0 30 50

Time Complexity

O(N), where N is the number of nodes in the linked list.

Must Read: Java System Out Println

Frequently Asked Questions

What is a linked list in C++?

A linked list is a linear data structure that instead of storing data at contiguous memory locations, stores data at random locations, and each node is linked to the other by the use of pointers.

What are the applications of a linked list?

1. A linked list is used to implement Stack and Queues.
2. A linked list is used to implement hashing(open chain hashing).
3. A linked list is used to implement graphs(Adjacency list representation of graphs)

How do you delete a node in a linked list?

To delete a node from a linked list, we need to do the following steps.

Find the previous node of the node to be deleted.
Change the next pointer of the previous node.
Free memory for the node to be deleted.

Conclusion

So, this blog discussed the implementation of a linked list in Java using class. To learn more, head over to Coding Ninjas Studio to practice problems on topics like Linked List, and Graphs, and crack your interviews like a Ninja!