Posted on by Kalkicode
Code Single linked list

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

Consider the following linked list:

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

Linked List After Remove node position 5

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):
    temp = linkedList.head
    
    if linkedList.head is NULL:
        print "Empty linked list"
        return
    else if index < 1:
        print "Invalid position"
        return
    else if index = 1:
        if linkedList.tail = linkedList.head:
            linkedList.tail = NULL
        linkedList.head = linkedList.head.next
        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
            if n = linkedList.tail:
                linkedList.tail = temp
            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".

Code Solution

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.

New Comment