Skip to main content

Insertion and Deletion of a Node in Linked List | Java | MyCodingNetwork

 


Insertion of a new node & Deletion of an existing node


After an exhilarating commencement of the Linked List series, in this post, we'll be exploring the artistry behind insertion and deletion operations in linked list. So let's now move on to the second problem statement of the series, i.e., write two functions for insertion and deletion of a node respectively, from linked list.

Algorithm for inserting a node at pos position:

  1. Create a function insert () which takes head of the node, pos and the new node as the parameter.
  2. Take a base case, if pos==1, means the new node is to be made the head of the linked list.
  3. If the above case is not true, traverse the linked list and reach to position, pos-1.
  4. Assign the new node with the address of the node at pos.
  5. Finally, assign the node at pos-1 with address of new node.

Algorithm for deleting a node at pos position:

  1. Create a function deletion () which takes pos and the head of the LinkedList as parameter.
  2. Base case, if pos ==1, then assign the second element as the head and return the new head.
  3. Traverse the linked list till the node at pos-1.
  4. Assign the node at pos-1 with the address of node with address of the node at pos+1.

Source Code with Explanation:


Insert() function: 




It is the function that inserts a new node `nn` into a linked list at a given position `pos`. The method takes three arguments: the head of the linked list `head`, the position `pos` where the new node `nn` should be inserted, and the new node `nn` itself.

The method first checks if the given position is 1. If it is, the method sets the next pointer of the new node to the current head of the list, calls a method named `traverse` with the new node as an argument, and returns the new node as the new head of the list.

If the given position is not 1, the method iterates through the list until it reaches the node before the desired position. It then sets the next pointer of the new node to the next node of the current node and sets the next pointer of the current node to the new node. Finally, it returns the head of the list.

Note: It's important to note that this code assumes that the given position is valid and within the bounds of the list.

Time Complexity: The time complexity of the insert() function is O(n). The for loop in the function runs for `pos-1` times where `pos` is the position at which the new node `nn` is to be inserted. In the worst-case scenario, `pos` can be equal to the length of the linked list, making the time complexity O(n).




Deletion() function:




It is a method for deleting a node from a linked list at a specified position. The method takes two arguments: `head`, which is the head of the linked list, and `pos`, which is the position of the node to be deleted.

First, the method creates a new `Node` object called `cur` and sets it equal to the `head` of the linked list. If the position to be deleted is 1 (i.e., the first node in the list), then the method sets the `head` of the list to be the next node in the list.

If the position to be deleted is not 1, then the method enters a `for` loop that iterates from 1 to `pos-1`. In each iteration of the loop, `cur` is set to be the next node in the list. After the loop completes, `cur` is pointing to the node immediately before the node to be deleted. The method then sets the `next` field of `cur` to be equal to the node after the node to be deleted.

Finally, after either deleting the first node or deleting a node at some other position in the list, the method calls a function named `traverse(head)` which traverses and prints out all elements of the linked list starting from its head.

Time Complexity: The time complexity of the deletion() function is O(n). The reason is somewhat similar to that of insert() function. In worst case scenario, the for loop will traverse the full length of the linked list, , making the time complexity O(n).

Full source code link: Source Code | Insertion and Deletion of Linked List | MyCodingNetwork

Output:



The first line is the original Linked List.
The second line is after insertion operation is performed, 50 is added at 3rd position.
The third line is after deletion operation is performed, first element is deleted.

Video References:





Hope you liked this explanation, for any feedback or doubt you can comment down in the comment section.

Labels:

Popular posts from this blog

YouTube Material 1| Hindi Video

Video Lecture- https://youtu.be/StCjnwfS0NQ Basic structure of a Java program public class xyz { public static void main(String args[]) { //Code //Code //Code //Code //Code }} public - access specifier/modifiers which makes the particular entity accessible throughout the program i.e., it can be accessed by other classes also. static - a keyword by which we don't have to create an object of that particular entity. void- return type keyword by which the function becomes non-returning type. main - name of the function String args[] - argument for main function Print Statement Syntax: System.out.println() ; Three types of Iteration statements are: for loop Example: for(int i=0; i<=5;i++) { //Code //Code //Code //Code //Code } The body of the above for loop will be executed 6 times. while loop( entry control loop) Syntax: while (condition) { //Code //Code //Code //Code //Code } The body of the above while loop will be executed continuously as long as the condition of the while is tr...
Discover More »

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...
Discover More »

Binary Search | The-Algorithm-Drive | MyCodingNetwork

Binary Search The next algorithm, we are going to study is Binary Search . As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced.  Time complexity of linear search is O(N) whereas that of binary search is O (log N). Source Code: Output Number Found at index =5 Working Let’s come on to the working of the algorithm, as you can see in the above program, we need a sorted array to perform binary search algorithm. 1.    Here, bin function in the above program it accepts 4 parameters, that is, the array arr , lower index low , higher index high and the searching number sn . 2.    Next, we have a do-while loop to check if high is greater than or equal to low (high>=low). If at any point of iteration this condition is not satisfied, it means the searching number sn does not exist in the array. Following is the algorithm for binary search: while ...
Discover More »