Posted on by Kalkicode
Code Single linked list

# Delete a node from linked list without head pointer

The problem at hand involves deleting a node from a singly linked list without having direct access to the head of the linked list. Linked lists are data structures that consist of nodes, where each node has a value and a reference to the next node in the sequence. Deleting a node typically requires updating the pointers of the previous node to bypass the node to be deleted and connect directly to the subsequent node. However, without a direct reference to the head node, this task becomes more challenging.

## Problem Description

Given a singly linked list and a node in that linked list, your goal is to delete the specified node without having direct access to the head of the linked list. The challenge here is that you cannot simply traverse the list from the beginning to find the previous node, as you don't have a direct reference to the head.

## Example

Let's take an example to better understand the problem:

Linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL

You want to delete the node with value 3 from the list.

## Idea to Solve

Since you don't have the head pointer, you cannot directly traverse the list from the beginning. However, you can copy the value of the next node into the node you want to delete, effectively making it seem like you have deleted the node. You can then bypass the next node by updating the pointers of the current node.

## Pseudocode

``````function deleteNode(ref, node):
if node is NULL:
return

if node.next is NULL:
// Cannot delete the last node
return
else:
// Copy value of next node into current node
node.data = node.next.data

// Get the node to be deleted
temp = node.next

// Bypass the next node
node.next = temp.next

// Free the memory of the deleted node
free(temp)

main:
create linked list sll
populate sll with values
display sll before deletion
call deleteNode(sll, node_to_delete)
display sll after deletion``````

## Algorithm Explanation

1. The `deleteNode` function takes a reference to the linked list (`ref`) and the node to be deleted (`node`) as input.
2. If the node is `NULL`, there's nothing to delete, so the function returns.
3. If the next node of the current node is `NULL`, it means the node to be deleted is the last node. In this case, you cannot delete it, so the function returns.
4. Otherwise, copy the value of the next node into the current node, effectively overwriting the value you want to delete.
5. Get the reference to the node you want to delete (which is the next node).
6. Update the pointers of the current node to bypass the next node.
7. Free the memory of the node to be deleted.

## Time Complexity

The time complexity of deleting a node from a linked list without having a direct reference to the head is O(1). This is because you're essentially copying a value and updating a few pointers, which takes constant time.

## 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