Deleting node in Double linked list?

This is a discussion on Deleting node in Double linked list? within the C Programming forums, part of the General Programming Boards category; Hello- I have a double link list which builds in sorted order. It works fine and dont think there are ...

  1. #1
    Registered User
    Join Date
    Dec 2002
    Posts
    8

    Deleting node in Double linked list?

    Hello-
    I have a double link list which builds in sorted order.
    It works fine and dont think there are bugs.
    But, I am really struggling with code to delete a node.
    I am particularly having difficulty with deleting the 2nd node if there are 3 or more nodes present.
    I have tried this code below, which also appeared in a C Reference text, but it wont work
    I can post the code for the whole program if that will help.

    Appreciate any enlightenment,

    Thank you,

    Bozz

    Code:
    void deleteDLStudent(void)
    {
     DL_STUDENT* info = NULL;
    
     info = search(start); //info is pointer(record) to delete
         //start->prev = NULL;
      if(info)
      {
        if(info == start) //deleting first link
        {
         start = info->next;
         if(start)        // if at least 1 link
          start->prev = NULL;
         else            // else 'info' was the only link
           end = NULL;
        }
        else
        {
          if(info->prev)
          info->prev->next = info->next;
          if(info != end)
              info->next->prev = info->prev;
          else
            end = info->prev;
        }
       free(info);
      }
      print(start, end);
     return;
    }

    Code tags added by Hammer

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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>
    Last edited by Magos; 12-10-2002 at 04:07 PM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Dec 2002
    Posts
    8
    Thanks, Magos-

    I have tried your code, but this isn't working either.
    In the code i had originally, this part works ok. i.e the code to remove the first node.

    if(info == start) //deleting first link
    {
    start = info->next;
    if(start) // if at least 1 link
    start->prev = NULL;
    else // else 'info' was the only link
    end = NULL;
    }

    its the rest that's not working.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,659
    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.



    ITSA
    Socket Library!

  6. #6
    Registered User
    Join Date
    Dec 2002
    Posts
    8

    double link list, deleting node

    Thanks everyone-
    With your help I found a bug somewhere -my original code for deleting a node was OK - i think

    It I really helps to see new ways of doing things.

    bozz

  7. #7
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291
    addition comment . to make the things easier, you may two pointer to control for the double linked list. for eg: previousPtr and currentPtr.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help me debug this linked list !
    By Dark Angel in forum C Programming
    Replies: 6
    Last Post: 04-18-2008, 02:10 PM
  2. Deleting node from linked list, need explanation
    By prihod in forum C Programming
    Replies: 5
    Last Post: 04-07-2008, 01:06 AM
  3. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  4. Help here with qsort!
    By xxxrugby in forum C Programming
    Replies: 11
    Last Post: 02-09-2005, 07:52 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21