Thread: Deleting node in Double linked list?

A doubly linked list you say? That makes it even easier .
This piece of code deletes a node and updates the pointers of the surrounding nodes (no need for special cases either):

Code:

void Delete(NODE* Node)
{
   //Rearrange the previous node's NextNode pointer
   if(Node->PrevNode != NULL)
   {
      Node->PrevNode->NextNode = Node->NextNode;
   }
   //No previous node exists, update the FirstNode pointer instead
   else
   {
      FirstNode = Node->NextNode;
   }

   //Rearrange the next node's PrevNode pointer
   if(Node->NextNode != NULL)
   {
      Node->NextNode->PrevNode = Node->PrevNode;
   }
   //No next node exists, update the LastNode pointer instead (if you have one)
   else
   {
      LastNode = Node->PrevNode;
   }

   //Delete the node
   free(Node);
}

<EDIT>
Of course, I wrote it in C++ instead of C...
</EDIT>

As posted, deleting a node from a double linked list is the easiest list to delete from. Way easier than single linked lists. All you have to do is pass it the node to delete.

1) Point the previous node's next node to the current node's next node.

Code:

if( current->prev )
{
    current->prev->next = current->next;
}

2) Point the next node's previous node to the current node's prev node.

Code:

if( current->next )
{
    current->next->prev = current->prev;
}

3) Cut it free:

Code:

current->prev = current->next = NULL;
free( current );

It doesn't get any easier than that. And actually, you don't even have to set the pointers to null. I just actually make my function a "cut" function, which cuts a node from a list, and then have something else free it. But then I tend to make my lists use more general utility based functions.

Quzah.

Here's a generic approach:

Code:

void repoint_neighbors(Node * self, Node * p, Node * n){
 if(self->next) self->next->prev = p;
 if(self->prev) self->prev->next = n;
}

void repoint_self(Node * self, Node * p, Node * n){
 self->next = n;
 self->prev = p;
}

Node * insert_node(Node * self, Node * p, Node * n){
 repoint_self(self, p, n);
 repoint_neighbors(self, self, self);
 return self;
}

Node * extract_node(Node * self){
 repoint_neighbors(self, self->prev, self->next);
 repoint_self(self, 0, 0);
 return self;
}

Node * insert_new_node(Node * p, Node * n){
 Node * self = malloc(sizeof(Node));
 if(self != NULL) insert_node(self, p, n);
 return self;
}

void delete_node(Node * self){
 free( extract_node(self) );
}

Thus, there is really not much code behind linked lists. It's merely an issue of making sure you do things in the correct order, nothing else. You should always seek to create generic solutions too, easier to debug and alter, and arguably more readable.

addition comment . to make the things easier, you may two pointer to control for the double linked list. for eg: previousPtr and currentPtr.