/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

## 12.25.2012

### Deleting a Node from a Singly Linked List

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Deletion of a Node from a Singly Linked List
Similar to insertion we have three cases for deleting a Node from a Singly Linked List.

• Deleting First Node in Singly Linked List

To complete deletion of firstNode in the list we have to change Head pointing to Next of firstNode.

Pseudocode:
firstNode = Head

free firstNode
Complexity:
Time Complexity: O(1)
Space Complexity: O(1)

Sourcecode:
 int delNodeData(int num)
{
struct Node *prev_ptr, *cur_ptr;

while(cur_ptr != NULL)
{
if(cur_ptr->Data == num)
{
{
free(cur_ptr);
return 0;
}
else
{
prev_ptr->Next=cur_ptr->Next;
free(cur_ptr);
return 0;
}
}
else
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}
}

return 1;
}
• Deleting Last Node in the Singly Linked List

Traverse to Last Node in the List using two pointers namely prevNode and curNode. Once curNode reaches the last Node in the list point Next in prevNode to NULL and free the curNode.

Pseudocode:
curNode = head

forever:

if curNode->Next == NULL
break

prevNode = curNode
curNode = curNode->Next

prevNode->Next = NULL

free curNode
Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

• Deleting Node from position 'p' in the List

To delete a Node at the position 'p' we have to first traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to curNode Next and free curNode.

Pseudocode:
curNode = head
curPos = 1

forever:

if curPos == P || curNode == NULL
break

prevNode = curNode
curNode = curNode->Next
curPos++

if curNode != NULL:

prevNode->Next = curNode->Next
free curNode
Complexity:
Time Complexity: O(n) worst case
Space Complexity: O(3)

Sourcecode:
int delNodeLoc(int loc)
{
struct Node *prev_ptr, *cur_ptr;
int i;

if(loc > (length()) || loc <= 0)
{
printf("\nDeletion of Node at given location is not possible\n ");
}
else
{
// If the location is starting of the list
if (loc == 1)
{
free(cur_ptr);
return 0;
}
else
{
for(i=1;i<loc;i++)
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}

prev_ptr->Next=cur_ptr->Next;
free(cur_ptr);
}
}
return 1;
}

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List