CODEWITHSUNDEEP
c++linked-list
aj983
aj983

Reputation: 293

Given A pointer to a node, Delete that particular node

I have a pointer to a node, I want to delete that particular node from linked list. The below logic works fine, But it fails if node to be deleted is Last node. How to delete the last node?

void deleteNodWhosePointerIsGivene(node *pointerNode)
{
  node *temp=pointerNode->next;
  pointerNode->id=temp->id;
  pointerNode->next=temp->next;
  free(temp);
}

Upvotes: 2

Views: 1403

Answers (6)

João Augusto
João Augusto

Reputation: 2305

If you are able to have a reference to the previous node.

void deleteNodWhosePointerIsGivene(structNode* pCurrentNode, structNode* pPreviousNode)
{
    // Not the Last Node ?
    if(pCurrentNode->pNext) 
        pPreviousNode->pNext = pCurrentNode->pNext);                    
    else
        pPreviousNode->pNext = NULL;

    delete pCurrentNode;
    pCurrentNode = NULL;
}

Otherwise you will need to have a reference to the First Node of the List, and search for the previous.

Upvotes: 0

Rafał Dowgird
Rafał Dowgird

Reputation: 45081

If you really need to delete the item associated with the node whose pointer you've got, then you have two options when it comes to the last node:

  • Iterate from the beginning of the list to find its predecessor (the next-to-last node), delete the last node and set it's predecessor's next to NULL.

  • Take the lazy approach - do not actually delete the node and only mark it as dead (e.g by setting its data to an impossible value.) Delete it later when you reach it from the predecessor (then also NULL-ing predecessor's next).

Both approaches have obvious drawbacks. This is why it is best to always have the predecessor when deleting a node from a linked list.

Upvotes: 0

rushman
rushman

Reputation: 31

Here's the code which should work for a singularly linked list. Bear in mind this will be quite slow for large lists and I would second Andrew Norman's suggestion of using a doubly linked list.

Anyway.. here goes. In order for this to work you need to pass the root node of the list and beware that the address of this node may get changed if you try to delete it, hence I pass it as a pointer to a pointer.

void DeleteNode (Node **rootNode,Node *pointerNode)
{
    Node *prevNode;

    if (pointerNode == *rootNode) {

       // Head node is being removed

       *rootNode = pointerNode->Next;

    } else {

       // Find the previous node

       for (prevNode = *rootNode; prevNode->Next != pointerNode;
            prevNode = prevNode->Next) ;

       prevNode->Next = pointerNode->Next;
    }

    // Free the node

    free (pointerNode);
}

Upvotes: 0

rushman
rushman

Reputation: 31

You aren't deleting pointerNode in your code, You are deleting pointerNode->next.

Looking at your example of a single linked list. Let's say we have:

1->2->3->4->5

You pass in a pointerNode of "3". Your code then does the following:

1) Assigns pointerNode->Next to temp i.e. "4"

2) pointerNode->Next will be assigned temp->Next i.e. "5"

3) temp is freed i.e. "4"

so your list after this would be 1->2->3->5.

When you get to node "5" then you will get an access violation

1) pointerNode->next is assigned to temp i.e. NULL

2) pointerNode->Next will be assigned temp->Next i.e. access violation as you reference a NULL pointer.

A doubly linked list would be a better solution as to delete pointerNode you need to change the Next pointer of the previous node. Otherwise you'd have to scan the list first to find the node prior to pointerNode.

Upvotes: 0

Andrew Norman
Andrew Norman

Reputation: 128

Think about what you are trying to do.

You are trying to delete the next object in the list.

You are at the end of the list, therefore the temp pointer will be null.

You are then trying to get the next from null and also trying to free null.

Normally I would do something along the lines of.

DeleteObject(*obj)
 Get Next Object
 Get Prev Object
 Set Prev->next = Next 
 Set Next->prev = Prev
 Delete obj;

If I am understanding you comments above you are wanting to do a copy then your code should look like.

 DeleteObject
 Get Next Object
 if (Next Object is not null)
    This.Id == Next.Id
    Free Next
 else 
    Throw exception "Cannot delete last object in list"

There is no way to set the pointer in the second to last object in the list if you want to delete the last object in the list. The only way to do this is to either use a double-linked list, or iterate down the list looking for the pointer you wish to delete and keep track of the last object in the list.

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409166

First of all you are not removing pointerNode from the list, you are removing the next node in the list. Secondly you are not checking if there is a next node or not.

Upvotes: 1

Related Questions