Remove Nth Node from Linked List

Remove 3rd node from below list
Input

Anbu -> Arul -> Arasu-> Bharath-> Catherine -> Davidson

Output

Anbu -> Arul -> Bharath-> Catherine -> Davidson

Idea: Traverse to the Kth Position and point the reference of temp to one next to it. We need to handle one edge case which is when the Kth position is first node then in such case the head should be changed to point temp next position.

public class RemoveNthNodeFromLL {
    public static void main(String[] args) {
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();

        simpleLinkedList.insertNodeAtEnd("Anbu");
        simpleLinkedList.insertNodeAtEnd("Arul");
        simpleLinkedList.insertNodeAtEnd("Arasu");
        simpleLinkedList.insertNodeAtEnd("Bharath");
        simpleLinkedList.insertNodeAtEnd("Catherine");
        simpleLinkedList.insertNodeAtEnd("Davidson");

        simpleLinkedList.printLinkedList();

        System.out.println("--------------After Removing 3rd Node--------------");

        removeNthNode(simpleLinkedList, 3);

        simpleLinkedList.printLinkedList();
    }


     public static void removeNthNode(SimpleLinkedList simpleLinkedList, Integer indexOfNodeToBeRemoved){
        Node temp = simpleLinkedList.head;

        //Edgecase1 : If Kth index is 1
        if(indexOfNodeToBeRemoved == 1){
            simpleLinkedList.head = temp.next;
            return;
        }

        for(int idx=1;idx<indexOfNodeToBeRemoved-1;idx++){
            temp = temp.next;
        }

        temp.next = temp.next.next;
    }
}

Output

Anbu
Arul
Arasu
Bharath
Catherine
Davidson
--------------After Removing 3rd Node--------------
Anbu
Arul
Bharath
Catherine
Davidson

Reverse a Linked List
Input

1 -> 2 -> 3 -> 4 -> 5 -> NULL 

Output

5 -> 4 -> 3 -> 2 -> 1 -> NULL 

Idea1: Using bruteforce copy the list in to Array and traverse the array backward and create new node
Idea2:

1. Use 3 Variables. Prev, Curr, Temp and traverse through list items
2. Start with Curr in Head and Prev as null
3. Move forward by making Temp to Curr.next, Curr.next to Prev
4. Prev should be set to Curr and Curr should be set to Temp

Refer Adv DSA 3 Note 5 Page 9

Previous -> Current -> Temp

Node.java

package com.mugil.org;
class Node{
	String content;
	Node next;
	Node head;
    public Node(String content){
	 this.content = content;
	}	
}

SimpleLinkedList.java

package com.mugil.org;

public class SimpleLinkedList {
    Node head;

    public void printLinkedList() {
        Node current = head;
        while (current != null) {
            System.out.println(current.content);
            current = current.next;
        }
    }
}

ReverseLinkedList.java

public class ReverseLinkedList {
    public static void main(String[] args) {
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();

        simpleLinkedList.insertNodeAtEnd("Anbu");
        simpleLinkedList.insertNodeAtEnd("Arul");
        simpleLinkedList.insertNodeAtEnd("Arasu");
        simpleLinkedList.insertNodeAtEnd("Bharath");
        simpleLinkedList.insertNodeAtEnd("Catherine");
        simpleLinkedList.insertNodeAtEnd("Davidson");

        simpleLinkedList.printLinkedList();

        reverseLinkedList(simpleLinkedList);
    }

    public static void reverseLinkedList(SimpleLinkedList simpleLinkedList){
        Node temp = simpleLinkedList.head;
        Node curr = temp;
        Node prev = null;


        while(temp != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        simpleLinkedList.head = prev;

        System.out.println("-----------------------------------");
        simpleLinkedList.printLinkedList();
    }
}

Output

Anbu
Arul
Arasu
Bharath
Catherine
Davidson
-----------------------------------
Davidson
Catherine
Bharath
Arasu
Arul
Anbu

1. Linked List is made of combination of Node
2. The smallest unit of linked list is Node
3. Node contains two things the content of the node And reference to next node
4. If a linked list has only one element then it would have only one node

Node.java

class Node{
	String content;
	Node next;

        public Node(String content){
 	 this.content = content;
	}	
}

1. To traverse linked list we should always start at the head
2. After printing the content we should move to next node as mentioned in next variable in current node

Traversing a LL
LL node next always points to reference of next node if any or else would be null if only one element is present. While Traversing we always start with head position

public class Main{
	public static void main(String args[]){
		Node node1 = new Node("Anbu");
				
		Node node2 = new Node("Arul");
		node1.next = node2;

		Node node3 = new Node("Arasu");
		node2.next = node3;

		printLinkedList(node1);
	}

	public static void printLinkedList(Node startingNode){
		while(startingNode.next !=null){
			System.out.println(startingNode.content);
			startingNode = startingNode.next;
		}

		if(startingNode.next == null){
			System.out.println(startingNode.content);
		}
	}
}

The above code can be refactored as below using recursion calling same function again and again

public class Main{
	public static void main(String args[]){
		Node node1 = new Node("Anbu");
				
		Node node2 = new Node("Arul");
		node1.next = node2;

		Node node3 = new Node("Arasu");
		node2.next = node3;

		printLinkedList(node1.head);
	}
        
        public static void printLinkedList(Node startingNode){
		//Note: We are traversing to next null node before exit without this last element wont be printed
		if(startingNode == null){ 			
		  return;
		}

		System.out.println(startingNode.content);
		printLinkedList(startingNode.next);
	}
}

Output

Anbu
Arul
Arasu

Now let’s move the linked list methods to a separate class called SimpleLinkedList.java

SimpleLinkedList.java

public class SimpleLinkedList {
    Node head;

    public static void traverseLinkedList(Node startingNode){
        //Note: We are traversing to next null node before exit without this last element wont be printed
        if(startingNode == null){
            return;
        }

        System.out.println(startingNode.content);
        printLinkedList(startingNode.next);
    }
}

Why LinkedList is Faster than ArrayList?
Adding Element in middle of ArrayList requires reshuffling of other elements.Whereas in Linked list only two nodes(Nodes between which the element is added) needs to be changed.

Types of LinkedList?

1. singly linked list
2. doubly-linked list
3. Circular linked list

singly linked list	doubly-linked list
Pros:Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster.	Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous’ pointer.
Cons:Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you’re deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time	Relatively complex to implement, requires more memory for storage (1 ‘.previous’ pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous’ pointer for neighbor nodes)

Time complexity of a linked list

Operation	Metrics
Indexing	O(n)
Inserting / Deleting at end	O(1) or O(n)
Inserting / Deleting in middle	O(1) with iterator O(n) with out

The time complexity for the Inserting at the end depends if you have the location of the last node, if you do, it would be O(1) other wise you will have to search through the linked list and the time complexity would jump to O(n).