Posted on by Kalkicode

# Delete a Linked List node at a given position

The problem at hand is to delete a node at a given position in a linked list. Given a singly linked list and a position index, the task is to remove the node at that position from the linked list.

## Problem Description

Given a singly linked list and a position index (starting from 1), the problem is to delete the node at that position from the linked list.

## Example

``10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80``

After deleting the node at position 5, the linked list becomes:

``10 -> 20 -> 30 -> 40 -> 60 -> 70 -> 80``

## Idea to Solve the Problem

To solve this problem, we need to traverse through the linked list until we reach the node just before the specified position. Then we update the links to skip the node at the given position.

## Pseudocode

``````deleteAtIndex(linkedList, index):

return
else if index < 1:
print "Invalid position"
return
else if index = 1:
free(temp)
else:
count = index - 1
while temp is not NULL and count > 1:
temp = temp.next
count -= 1
if count = 1 and temp.next is not NULL:
n = temp.next
temp.next = n.next
free(n)
else:
print "Index %d is not present" % index
return``````

## Algorithm Explanation

1. Start with the `temp` pointer pointing to the head of the linked list.
2. Handle special cases: a. If the linked list is empty, print "Empty linked list" and return. b. If the index is less than 1, print "Invalid position" and return. c. If the index is 1:
• If there's only one node in the linked list, update `linkedList.tail`.
• Update the `head` of the linked list to `head.next`.
• Free the memory occupied by the current node.
3. Traverse through the linked list until the node just before the specified index: a. Move the `temp` pointer by one step and decrement the `count` by 1.
4. If `count` is 1 and `temp.next` is not NULL: a. Get the node to be deleted, `n`. b. If `n` is the last node, update `linkedList.tail`. c. Update the link to skip the node `n`. d. Free the memory occupied by `n`.
5. If `count` is not 1 or `temp.next` is NULL, print "Index is not present".

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. In the worst case, we traverse through the entire linked list to find the node to be deleted.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post