Linked List: Program to delete a node at specific position from linked list


Write a program to delete a node from a given position in a linked list

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list.

 
Deleting a node from a given position
  1. Create two pointers say current and previous
  2. If position is 1 (i.e deleting the first node), make head as head.next and return
  3. Set current pointer on head node and previous as NULL
  4. Else run for loop position-1 times and
    • make previous point to current
    • increment current pointer to current.next
  5. Make previous.next as current.next and then current.next as NULL
 
Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

 
Java Code
  import java.util.*;
 
    class Node {
        // initialising data field and next pointer of node
        int data;
        Node next;
     
        Node(int d) {
            this.data = d;
            this.next = null;
        }
    }
     
    class LinkedList {
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int startingNodeArray[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(startingNodeArray[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(startingNodeArray[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
     
        // function for deleting node with given position
        public void deleteAtPosition(int position) {
            if(head == null) {
                return;
            }
            Node current = head;
            Node previous = null;
            if (position == 1) {
                head = head.next;
                return;
            } else {
                for (int i = 0; i < position - 1; i++) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
                current.next = null;
            }
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 10, 30, 50, 40, 70, 90 };
            int numberOfNodes = 6;
            // initialising object of linkedlist class
            LinkedList ll = new LinkedList();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            System.out.println("After deleting node with position 4");
            ll.deleteAtPosition(4);
            ll.printLinkedlist();
     
        }
   }
Output

Given Linked List
10 -> 30 -> 50 -> 40 -> 70 -> 90
After deleting node with position 4
10 -> 30 -> 50 -> 70 -> 90



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node from linked list
Detect if cycle is present in a linked list