delete doubly linked list

This is a discussion on delete doubly linked list within the C Programming forums, part of the General Programming Boards category; Hey guys i am having allot of trouble understanding how deletion works when trying to delete a node. Just wondering ...

  1. #1
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252

    delete doubly linked list

    Hey guys i am having allot of trouble understanding how deletion works when trying to delete a node. Just wondering if someone could explain how it works so i can build up from there, the code here is assignment start up code which we must convert to a doubly linked list

    Code:
              current = menu->headCategory;
            previous = NULL;
    
            /* Loop through category, checking it against the user's input. */
            while(current != NULL)
            {
               /* If a match is found, delete the category from the list */
               if(strcmp(current->categoryID, input) == 0)
               {
                  printf("Category '%s - %s' deleted from the system\n",
                          current->categoryID, current->categoryName);
    
                  /* Reduce the number of category variable when deleting an
                     category. */
                  menu->numCategories--;
    
                  /* If deleting at the head. */
                  if(current == menu->headCategory)
                  {
                     previous = current->nextCategory;
                     submenuCurrent = current->headItem;
                     while(submenuCurrent != NULL)
                     {
                        submenuNext = submenuCurrent->nextItem;
                        free(submenuCurrent);
                        submenuCurrent = submenuNext;
                     }
                     free(current);
                     current = NULL;
                     menu->headCategory = previous;
                     return;
                  }
    
                  /* If deleting the last category in the list. */
                  else if(current->nextCategory == NULL)
                  {
                     submenuCurrent = current->headItem;
                     while(submenuCurrent != NULL)
                     {
                        submenuNext = submenuCurrent->nextItem;
                        free(submenuCurrent);
                        submenuCurrent = submenuNext;
                     }
                     free(current);
                     current = NULL;
                     previous->nextCategory = NULL;
                     return;
                  }
    
                  /* If deleting in between the list. */
                  else
                  {
                     submenuCurrent = current->headItem;
                     tempCurrent = current;
    
                     while(submenuCurrent != NULL)
                     {
                        submenuNext = submenuCurrent->nextItem;
                        free(submenuCurrent);
                        submenuCurrent = submenuNext;
                     }
                     previous->nextCategory = tempCurrent->nextCategory;
                     free(current);
                     current = NULL;
    				
                        previous->nextCategory = tempCurrent->nextCategory; 
    				    Modified 23/April/2007 */
                     return;
                  }
               }
    
               previous = current;
               current = current->nextCategory;
    
               /* If a match was not found */
               if(current == NULL)
               {
                  printf("Category '%s' was not found in the system, "
                         "please re-enter!\n", input);
                  valid = FALSE;
               }
            }
          }

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Simple.

    1) You get the node before the node you wish to delete.
    2) You have that node's next pointer point to the node after the one which you wish to delete (instead of the one you are about to delete).
    3) You get the node after the node you wish to delete.
    4) You have it's before pointer point to the node before the one which you wish to delete (instead of the one you're about to delete).
    5) Finally, you delete your node.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252
    ok would you also know how to insert a node at the head and then later adding it to the middle then to the tail. If you could write some steps like that it would be much appreciated

  4. #4
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Wow you guys like to complicate matters.

    Where N is the node to delete:
    Code:
    if( N->prev )
        N->prev->next = N->next;
    if( N->next )
        N->next->prev = N->prev;
    free( N );
    The only thing you may want to add is a check to see if you're deleting the head of the list (and I suppose tail if for some odd reason you feel the need to track that.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM
  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