remove entry from doubly linked list

This is a discussion on remove entry from doubly linked list within the C Programming forums, part of the General Programming Boards category; Hello, I am trying to delete an entry from a doubly linked list, where the function takes a pointer to ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    49

    remove entry from doubly linked list

    Hello, I am trying to delete an entry from a doubly linked list, where the function takes a pointer to the entry to be removed as its argument. I have tried various different things, and I can get the insertEntry function to work, but I am at a loss for what to put for the remove Entry.

    I can get it if I put that it will receive the entry before the entry to be removed as the argument but not when it receives the entry to be removed as the argument. Can you guys help me? This is not homework, I am learning on my own. Here is the code I have so far.

    Code:
    /* 6. Develop insertEntry and removeEntry functions for a doubly linked list that are
    similar in function to those developed in previous exercises for a singly linked list.
    Why can your removeEntry function now take as its argument a direct pointer to
    the entry to be removed from the list?
    
    
     */
    
    
    #include <stdio.h>
    
        struct entry
        {
            int value;
            struct entry *next;
            struct entry *previous;
        };
        
        struct entry n2, n3, n4, insert;
    
    int main (void)
    {
        
        void insertEntry (struct entry *here, struct entry *insert);
        void removeEntry (struct entry *remove);
        
        struct entry *list_pointer = &n2;
    
        n2.value = 200;
        n2.next = &n3;
        n2.previous = (struct entry *) 0;
        
        n3.value = 300;
        n3.next = &n4;
        n3.previous = &n2;
        
        n4.value = 400;
        n4.next = (struct entry *) 0;
        n4.previous = &n3;
        
        insert.value = 250;
        
        
        
        while ( list_pointer != (struct entry *) 0 ) 
            {
            printf ("%i\n", list_pointer->value);
            list_pointer = list_pointer->next;
            }
     
        
        list_pointer = &n2;
        
        insertEntry(&n2, &insert);
        removeEntry(&n4);
        
        while ( list_pointer != (struct entry *) 0 ) 
            {
            printf ("%i\n", list_pointer->value);
            list_pointer = list_pointer->next;
            }
    
    }
    
    void insertEntry (struct entry *here, struct entry *insert)
    {
        insert->next = here->next;
        here->next = insert; 
    }
    
    void removeEntry (struct entry *remove)
    {
        remove->previous = remove->next;
    }
    Last edited by sdbuilt; 10-19-2012 at 07:54 PM.

  2. #2
    Registered User
    Join Date
    Sep 2012
    Posts
    49
    I understand that my remove function just changes the pointer to the previous entry, and not the actual entry itself. How can I actually change the previous entry though so that its .next is the same as the entry to be removed's .next?

  3. #3
    Registered User
    Join Date
    Sep 2012
    Posts
    49
    Well I solved it .. no thanks to you guys! Lol j/k. Here is what I put.

    Code:
    void removeEntry (struct entry *remove)
    {
        remove->previous->next = remove->next;
    }
    I will give you guys another chance, though. Any alternate solutions or simpler ways to solve this?

  4. #4
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by sdbuilt View Post
    Code:
    void removeEntry (struct entry *remove)
    {
        remove->previous->next = remove->next;
    }
    What happens when you try to remove the first entry in the list?

    What about the previous pointer of the next entry in the list? Make sure you don't trip there too, like you do if you try to remove the first entry in the list.

    Besides, it's a frigging Saturday morning here, you - you morning-person you!

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Your list isn't doubly-linked yet. You haven't set any of the previous members to anything useful. What you just added would simply crash due to writing through a NULL pointer.

    This is also a somewhat longer alternative to just writing NULL: (struct entry *) 0
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Sep 2012
    Posts
    49
    Quote Originally Posted by iMalc View Post
    Your list isn't doubly-linked yet. You haven't set any of the previous members to anything useful. What you just added would simply crash due to writing through a NULL pointer.

    This is also a somewhat longer alternative to just writing NULL: (struct entry *) 0
    Huh? My program doesn't crash.. It removes the desired entry from the list as long as it isn't the first entry. I am not worried about that corner case I am just trying to understand the concepts. I went ahead and updated the function to update the previous pointer of the next entry of the list by using
    Code:
    remove->next->previous = remove->previous;
    Also I have no idea what you mean when you say to just write "NULL: (struct entry *) 0". Write that where? What do you mean?

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Quote Originally Posted by sdbuilt View Post
    Huh? My program doesn't crash.. It removes the desired entry from the list as long as it isn't the first entry. I am not worried about that corner case I am just trying to understand the concepts. I went ahead and updated the function to update the previous pointer of the next entry of the list by using
    Code:
    remove->next->previous = remove->previous;
    Also I have no idea what you mean when you say to just write "NULL: (struct entry *) 0". Write that where? What do you mean?
    Oh, you've set up the pointers in some of the static instances of the struct you have made. This needs to happen from your insertEntry function, otherwise it is broken in terms of every real-world scenario.

    I mean, you stop using "(struct entry *) 0". Just use "NULL" instead like everyone else. How much clearer can I be?
    Last edited by iMalc; 10-20-2012 at 11:03 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Sep 2012
    Posts
    49
    Oh I see what you mean. You mean the insertFunction should insert the first member of the list and then the second etc instead of having those things already set up in main. Got ya. Yeah that makes sense for a real world scenario.

    Yeah I was not understanding the way you worded that last part. The colon symbol through me off.. But when you worded it differently I understood. Replace the extra code with NULL like everybody else does gosh dang it!
    Last edited by sdbuilt; 10-21-2012 at 12:05 AM.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Ah nice. I hope it works well for you once you start using dynamic memory allocation.

    Just remember, it never hurts to use pen an paper for to draw diagrams if you run into trouble. Speaking from experience, doubly-linked lists are one of the things where it is most beneficial. Many things you can do with them are much harder than anyone ever realises at first.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list
    By BEN10 in forum C Programming
    Replies: 4
    Last Post: 07-21-2009, 09:32 AM
  2. Help with doubly linked list
    By Furbiesandbeans in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2008, 10:41 AM
  3. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 01:31 PM
  4. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 01:39 PM
  5. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM

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