Linked List Insertion and Deletion in Java (All Programs)

Singly Linked List Insertion and Deletion in Java

In this post, we will look at all possible ways of insertion and deletion of a node in a Single Linked List in Java.

What is a Linked List

A linked list is a chained sequence of data structures holding some data value and connected to one another sequentially. 

Each node contains the following –

  • Data value
  • Next – Holds address to the next node
Linked List insertion and Deletion in Java

Possible positions to insert/delete in a Linked List

Both insertions and deletion in a Linked List can happen at the following positions-

  • At Front
  • At End
  • In the Middle (After a certain position)

We will look at the program with all three above functions, however, do note that the default nature of a Linked List is to always insert at the front.q

Structure of a Linked List in Java

// Node Class
class Node{
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

Insertion in Singly Linked List in Java

Let us have a look at the programs below –

This method uses class instances to call functions.
Run
import java.lang.*;

class LinkedList {
    Node head;
    // not using parameterized constructor would by default
    // force head instance to become null
    // Node head = null;  // can also do this, but not required

    // Node Class
    class Node{
        int data;
        Node next;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
        }
    }
    public Node insertStart(int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);
        // assigning this newNode's next as current head node
        newNode.next = head;

        // re-assigning head to this newNode
        head = newNode;

        return head;
    }

    public void insertLast(int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // if Linked List was empty, entering first node
        if(head==null)
        {
            head = newNode;
            return;
        }

        // required to traverse the Linked List
        Node temp = head;

        // traverse till the last node in Linked List
        while(temp.next!=null)
            temp = temp.next;

        // assigning the current last node's next to this newNode
        // thus newNode becomes the last node in Linked List
        temp.next = newNode;

    }

    public void insertPosition(int n,int data)
    {
        int size = calcSize(head);

        // Can only insert after 1st position
        // Can't insert if position to insert is greater than size of Linked List
        if(n < 1 || n > size)
        {
            System.out.println("Can't insert\n");

        }
        else
        {
            Node newNode = new Node(data);
            // required to traverse
            Node temp = head;

            // traverse to the nth node
            while(--n > 0)
                temp=temp.next;

            // assigning this newNode's next to nth node's next
            newNode.next= temp.next;
            // assigning the nth node's next to this newNode
            temp.next = newNode;
            // newNode added after nth node
        }
    }

    public void display()
    {
        Node node = head;
        //as linked list will end when Node reaches Null
        while(node!=null)
        {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }
    // required for insertPosition() method
    public int calcSize(Node node){
        int size = 0;
        // traverse to the last node each time incrementing the size
        while(node!=null){
            node = node.next;
            size++;
        }
        return size;
    }
}

public class Main
{
    public static void main(String args[])
    {
        LinkedList ll = new LinkedList();

        ll.insertStart(3);
        ll.insertStart(2);
        ll.insertStart(1);

        ll.display();

        ll.insertLast(5);
        ll.insertLast(6);
        ll.insertLast(7);
        ll.insertLast(8);

        ll.display();

        //Inserts after 3rd position
        ll.insertPosition(3,25);

        ll.display();
    }
}

This method uses static methods to call functions.

import java.lang.*;

// Node Class
class Node {
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

class Main
{
    static Node insertStart(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // assigning this newNode's next as current head node
        newNode.next = head;
        // re-assigning head to this newNode
        head = newNode;

        return head;
    }

    static Node insertLast(Node head, int data) {

        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // if Linked List was empty, entering first node
        if(head==null) {
            head = newNode;
            return head;
        }

        // required to traverse the Linked List
        Node temp = head;

        // traverse till the last node in Linked List
        while(temp.next!=null)
            temp = temp.next;

        // assigning the current last node's next to this newNode
        // thus newNode becomes the last node in Linked List
        temp.next = newNode;
        return head;
    }

    static Node insertPosition(int pos, int data, Node head) {
        int size = calcSize(head);

        // Can only insert after 1st position
        // Can't insert if position to insert is greater than size of Linked List
        if(pos < 1 || size < pos) 
{
System.out.println("Can't insert," + pos + " is not a valid position\n");
}
else
{
Node newNode = new Node(data);
// required to traverse Node
Node temp = head;

// traverse to the nth node
while (--pos > 0) temp = temp.next; // assigning this newNode's next to nth node's next newNode.next= temp.next; // assigning the nth node's next to this newNode temp.next = newNode; // newNode added after nth node } return head; } static void display(Node node) { //as linked list will end when Node is Null while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } // required for insertPosition() method static int calcSize(Node node){ int size=0; // traverse to the last node each time incrementing the size while(node!=null) { node = node.next; size++; } return size; } public static void main(String args[]) { Node head = null; head = insertStart(head,3); head = insertStart(head,2); head = insertStart(head,1); display(head); head = insertLast(head,5); head = insertLast(head,6); head = insertLast(head,7); head = insertLast(head,8); display(head); //Inserts after 3rd position head = insertPosition(3,25,head); display(head); } }

Output

1 2 3 
1 2 3 5 6 7 8
1 2 3 25 5 6 7 8

Deletion in a Linked List in Java

Let us have a look at the programs below –

This method uses class instances to call functions.

import java.lang.*;

class LinkedList {
    Node head;
    // not using parameterized constructor would by default
    // force head instance to become null
    // Node head = null;  // can also do this, but not required

    // Node Class
    class Node{
        int data;
        Node next;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
        }
    }
    public void deleteStart()
    {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return;
        }

        System.out.println("Deleted: " + head.data);
        // move head to next node
        head = head.next;
    }

    public void deleteLast()
    {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return;
        }

        // if LL has only one node
        if(head.next == null)
        {
            System.out.println("Deleted: " + head.data);
            head = head.next;
        }
        Node previous = null;
        Node temp = head;
        // else traverse to the last node
        while (temp.next != null)
        {
            // store previous link node as we need to change its next val
            previous = temp;
            temp = temp.next;
        }
        // Curr assign 2nd last node's next to Null
        System.out.println("Deleted: " + temp.data);
        previous.next = null;
        // 2nd last now becomes the last node

    }

    public void deletePosition(int n)
    {
        int size = calcSize(head);

        // Can only insert after 1st position
        // Can't insert if position to insert is greater than size of Linked List
        if(n < 1 || n > size)
        {
            System.out.println("Can't delete\n");

        }
        else
        {
            if(n == 1)
            {
                // head has to be deleted
                System.out.println("Deleted: " + head.data);
                deleteStart();
            }
            // required to traverse
            Node temp = head;
            Node previous = null;

            // traverse to the nth node
            while(--n > 0) {
                previous = temp;
                temp = temp.next;
            }
            // assigned next node of the previous node to nth node's next
            previous.next = temp.next;
            System.out.println("Deleted: " + temp.data);
        }
    }
    public Node insert(int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);
        // assigning this newNode's next as current head node
        newNode.next = head;

        // re-assigning head to this newNode
        head = newNode;

        return head;
    }

    public void display()
    {
        Node node = head;
        //as linked list will end when Node reaches Null
        while(node!=null)
        {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println("\n");
    }
    // required for insertPosition() method
    public int calcSize(Node node){
        int size = 0;
        // traverse to the last node each time incrementing the size
        while(node!=null){
            node = node.next;
            size++;
        }
        return size;
    }

    public static void main(String args[])
    {
        LinkedList ll = new LinkedList();

        ll.insert(6);
        ll.insert(5);
        ll.insert(4);
        ll.insert(3);
        ll.insert(2);
        ll.insert(1);

        ll.display();

        ll.deleteStart();
        ll.display();

        ll.deleteLast();
        ll.display();

        // deletes 3rd node
        ll.deletePosition(3);
        ll.display();
    }
}
This method uses static methods to call functions.
import java.lang.*;

// Node Class
class Node {
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

class Main
{
    public static Node deleteStart(Node head)
    {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return head;
        }

        System.out.println("Deleted: " + head.data);
        // move head to next node
        head = head.next;

        return head;
    }
    static Node deleteLast(Node head) {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return head;
        }

        // if LL has only one node
        if(head.next == null)
        {
            System.out.println("Deleted: " + head.data);
            head = head.next;
            return head;
        }
        Node previous = null;
        Node temp = head;
        // else traverse to the last node
        while (temp.next != null)
        {
            // store previous link node as we need to change its next val
            previous = temp;
            temp = temp.next;
        }
        // Curr assign 2nd last node's next to Null
        System.out.println("Deleted: " + temp.data);
        previous.next = null;
        // 2nd last now becomes the last node

        return head;
}

    static Node deletePosition(int n, Node head) {
        int size = calcSize(head);

        // Can only insert after 1st position
        // Can't insert if position to insert is greater than size of Linked List
        if(n < 1 || n > size)
            System.out.println("Can't delete\n");

        else
        {
            if(n == 1)
            {
                // head has to be deleted
                System.out.println("Deleted: " + head.data);
                head = deleteStart(head);
                return head;
            }
            // required to traverse
            Node temp = head;
            Node previous = null;

            // traverse to the nth node
            while(--n > 0) {
                previous = temp;
                temp = temp.next;
            }
            // assigned next node of the previous node to nth node's next
            previous.next = temp.next;
            System.out.println("Deleted: " + temp.data);
            }
        return head;
    }
    public static Node insert(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);
        // assigning this newNode's next as current head node
        newNode.next = head;

        // re-assigning head to this newNode
        head = newNode;

        return head;
    }
    static void display(Node node) {

        //as linked list will end when Node is Null
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println("\n");
    }

    // required for insertPosition() method
    static int calcSize(Node node){
        int size=0;

        // traverse to the last node each time incrementing the size
        while(node!=null)
        {
            node = node.next;
            size++;
        }
        return size;
    }

    public static void main(String args[])
    {
        Node head = null;

        head = insert(head, 6);
        head = insert(head, 5);
        head = insert(head, 4);
        head = insert(head, 3);
        head = insert(head, 2);
        head = insert(head, 1);
        display(head);

        head = deleteStart(head);
        display(head);

        head = deleteLast(head);
        display(head);

        // deletes 3rd node
        head = deletePosition( 3, head);
        display(head);

    }
}

Output

1 2 3 4 5 6

Deleted: 1
2 3 4 5 6

Deleted: 6
2 3 4 5

Deleted: 4
2 3 5