Java Linked list

Implementing a Linked List in Java using Class

PrepBytes

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

A Linked List is a linear data structure. Unlike arrays, the elements are not stored at contiguous locations. The linked list nodes are linked using pointers.

Linked List Creation

Structure of a node:
Each linked list node consists of 2 parts:

  • Data: The Data which is stored at a particular address.
  • Reference: Contains the address of the next node of the linked list.

Creating class Node:

class Node {
    int data;
    Node next;

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

A linked List can be created by linking together the nodes.

  • The first node of the list is called a head, and the last node of the list is called a tail.
  • Each and every node in the list can be accessed by traversing through the list from head to tail.

In this article, we will be explaining how to add a new node in the linked list at the end or at any specified position. We will also explain how to delete any existing node in the Linked List.

Insertion Operations

Inserting at the end of the linked list

In this, we will insert a new node at the end of the Linked List.

For example, if we have a Linked List 2→4→6→8→10, and we want to insert 12 at the end of the linked list.

  • After inserting 12 at the end of the given linked list, our updated linked list will be: 2→4→6→8→10→12.

Algorithm

  • As a Linked List is represented by the head pointer, so to insert a new node at the end of the linked list, we will use another pointer tail which will always point to the last node of the list.
  • First, we will create a new node to be inserted, let’s say new_node, with given data.
  • Then we will check if the head is null or not.
    • If the head is null, then make:
    • head = new_node
    • tail = new_node
    • Else, if the head is not null, then make:
    • tail.next = new_node
    • tail = new_node

Code Implementation

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

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

    public Node head = null;
    public Node tail = null;

    // addNode() it will add a new node at the end of the linked list
    public void addNode(int data) {
        // Creating a new node
        System.out.println("Adding a new node with value "+data+" at the end of the linked list ");
        Node new_Node = new Node(data);

        // it will check if the list is empty or not
        if (head == null) {
            // when list is empty,head and tail point to new node
            head = new_Node;
            tail = new_Node;
        } else {
            // new_Node will be added after tail such that tail's next will point to newNode
            tail.next = new_Node;
            // new_Node will become new tail of the list
            tail = new_Node;
        }
    }

    // PrintData() will display all the nodes present in the list
    public void PrintData() {

        Node current = head;
        if (head == null) {
            System.out.println("Linked List is empty");
            return;
        }
        while (current != null) {
            // It will print each node by incrementing pointer
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        InsertNode List = new InsertNode();

        // Add 5 to the end of the list
        List.addNode(5);
        List.PrintData();

        // Add 4 to the end of the list
        List.addNode(4);
        List.PrintData();

        // Add 3 to the end of the list
        List.addNode(3);
        List.PrintData();

        // Add 2 to the end of the list
        List.addNode(2);
        List.PrintData();
    }
}
Output

Adding a new node with value 5 at the end of the linked list
5
Adding a new node with value 4 at the end of the linked list
5 4
Adding a new node with value 3 at the end of the linked list
5 4 3
Adding a new node with value 2 at the end of the linked list
5 4 3 2

Inserting at specific position in the linked list

In this method, we will traverse up to n elements, where n is equal to given position and add the node at that position.

For example, if we have a Linked List 1→2→3→4, and we want to insert a node with data = 5 at the 2nd position in the linked list.

  • After inserting a new node with data = 5 at 2nd position in our linked list, our resultant linked list will look like: 1→2→5→3→4.
  • Note: Take 0 based indexing while finding positions.

Algorithm

  • If the position is equal to 1, add the new_node before the head node.
    • new_node.nextNode = headNode;
    • head = new_node;
  • Otherwise, iterate up to the specified position using headNode and then do the following steps:
    • new_node.nextNode = headNode.nextNode;
    • headNode.nextNode = new_node;

Note: Variables names in the algorithm are the same as that in code, so for better understanding, go through code and algorithm at the same time.

Code Implementation

public class InsertNode {
    // Linked list node structure
    static class Node {
        public int data;
        public Node nextNode;

        // Constructor
        public Node(int data) {
            this.data = data;

        }
    }

    // Method to insert a node at position pos.
    static Node Insert(Node headNode, int pos, int data) {
        Node head = headNode;
        if (pos < 1)
            System.out.print("Invalid pos");

        if (pos == 1) {
            Node new_node = new Node(data);
            new_node.nextNode = headNode;
            head = new_node;
        } else {
            while (pos-- != 0) {
                if (pos == 1) {

                    Node new_node = new Node(data);

                    new_node.nextNode = headNode.nextNode;
                    headNode.nextNode = new_node;
                    break;
                }
                headNode = headNode.nextNode;
            }
            if (pos != 1)
                System.out.print("Position out of bound");
        }
        return head;
    }
    // PrintData() will display all the nodes present in the list
    static void PrintData(Node node) {
        while (node != null) {
            System.out.print(node.data);
            node = node.nextNode;
            if (node != null)
                System.out.print("->");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.nextNode = new Node(2);
        head.nextNode.nextNode = new Node(3);
        head.nextNode.nextNode.nextNode = new Node(4);

        System.out.print("Original Linked List: ");
        PrintData(head);

        // Insert a node at any position
        int data = 24, pos = 5;
        head = Insert(head, pos, data);
        System.out.print("Linked list after adding a node with data "+data+" at position "+pos+": ");
        PrintData(head);

        // Inserting a node at first position
        data = 39;
        pos = 1;
        head = Insert(head, pos, data);
        System.out.print("Linked list after adding a node with data "+data+" at position "+pos+": ");
        PrintData(head);

        data = 18;
        pos = 7;
        head = Insert(head, pos, data);
        System.out.print("Linked list after adding a node with data "+data+" at position "+pos+": ");
        PrintData(head);
    }
}
Output

Original Linked List: 1->2->3->4
Linked list after adding a node with data 24 at position 5: 1->2->3->4->24
Linked list after adding a node with data 39 at position 1: 39->1->2->3->4->24
Linked list after adding a node with data 18 at position 7: 39->1->2->3->4->24->18

Deletion Operations

In this section, we will see how to delete the first occurrence of the specified node from the linked list, i.e., deleting the first occurrence of a given key from the linked list.

For example, if we have a Linked List 2→4→6→4→10, and we want to delete the first occurrence of node with value 4 (key = 4) from the linked list.

  • After deleting the first occurrence of node with value 4 from the linked list, our resultant linked list will be: 2→6→4→10.

Algorithm

  • Condition1: If the key is at the head.

    • Change the head node to the next node of the current head.
    • list.head = current_Node.next;

  • Condition 2: The key is either in the middle or last, except at the head.

    • In this condition, find the previous node of the node to be deleted.

    • prev = current_Node;

    • current_Node = current_Node.next;

    • Make the previous node of the node to be deleted point to the next node of the current node.

    • prev.next = current_Node.next;

  • Condition 3: The key is not in the list.

    • Print key not found.

Note: Variables names in the algorithm are the same as that in code, so for better understanding, go through code and algorithm at the same time.

Code Implementation

public class LinkedList {

    Node head;
    // Linked list node structure
    static class Node {

        int data;
        Node next;

        // Constructor
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public static LinkedList value(LinkedList list, int data)
    {
        
        Node new_node = new Node(data);
        new_node.next = null;

        if (list.head == null) {
            list.head = new_node;
        }
        else {
            Node last = list.head;
            while (last.next != null) {
                last = last.next;
            }

            last.next = new_node;
        }

        return list;
    }

    public static void printData(LinkedList list)
    {
        Node current_Node = list.head;
    
        System.out.print("Linked List :- ");

        while (current_Node != null) {
            System.out.print(current_Node.data + " ");
            current_Node = current_Node.next;
        }
        System.out.println();
    }
 
    // Method to delete the node with data equal to specified key
    public static LinkedList deleteNode(LinkedList list,int key)
    {
        
        Node current_Node = list.head, prev = null;
 
        // Condition 1: Key is  at head
        if (current_Node != null && current_Node.data == key) {
            list.head = current_Node.next;
            System.out.println(key + " is found and deleted");

            return list;
        }
        
        // Condition 2
        while (current_Node != null && current_Node.data != key) {
            prev = current_Node;
            current_Node = current_Node.next;
        }

        if (current_Node != null) {
            prev.next = current_Node.next;
            System.out.println(key + " is found and deleted");
        }
 
        // Condition 3: The key is not  in the list
        if (current_Node == null) {
            System.out.println(key + " not found");
        }

        return list;
    }
 
    
    // Driver code
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        
        list = value(list, 2);
        list = value(list, 6);
        list = value(list, 1);
        list = value(list, 8);
        list = value(list, 9);
        list = value(list, 0);
        list = value(list, 3);
        list = value(list, 5);

        printData(list);
        deleteNode(list, 2);
        printData(list);

        deleteNode(list, 8);
        printData(list);

        deleteNode(list, 20);
        printData(list);
    }
}

Output

Linked List :- 2 6 1 8 9 0 3 5
2 is found and deleted
Linked List :- 6 1 8 9 0 3 5
8 is found and deleted
Linked List :- 6 1 9 0 3 5
20 not found
Linked List :- 6 1 9 0 3 5

This article explains how you can add a new node in the linked list at the end or at any specified position. It also explains how you can delete any existing node from the Linked List. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post