Add to Front, Remove from Front, Traverse

This is a discussion on Add to Front, Remove from Front, Traverse within the C Programming forums, part of the General Programming Boards category; I have a doubly linked, continuous list that I am having some troubles with. It seems as if my pointer ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    32

    Add to Front, Remove from Front, Traverse

    I have a doubly linked, continuous list that I am having some troubles with. It seems as if my pointer reassignments aren't working correctly, even though they appear to be logically accurate.

    My structure:
    Code:
    /* The node struct.  Has a prev pointer, next pointer, and data. */
    typedef struct _lnode {
        struct _lnode *prev;
        struct _lnode *next;
        void* data;
    } lnode;
    
    /* The linked list struct.  Has a head pointer. */
    typedef struct _llist {
        lnode *head;
    } llist;
    Adding to front:
    Code:
    void add_front(llist* list, void* data) {
        if(list->head == NULL){  // if no nodes exist
            lnode *n = make_node(data);
            list->head = n;
            n->next = n;
            n->prev = n;
            return;
        }
        lnode *n = make_node(data);
        lnode *old;
        old = list->head;
        n->next = list->head; // points new node at what head points at (old node)
        old->prev = n; // points old node to first node
        n->prev = old->prev;  // points new node to last node
        old->prev->next = n; // points last node to new first node
        list->head = n; // points head to new node
    }
    This is in-fact adding the node to the front of the list, however I am not sure that it is accurately linking to the next node or not, as traverse fails later on (read on).

    Remove Front:
    Code:
    void remove_front(llist* list) {
        lnode *old;
        old = list->head;
        old->next->prev = old->prev; // new first points to last
        old->prev->next = old->next; // last points to first
        list->head = old->next;
        remove_node(old);
    }
    This is not removing the node from the front of the list, as it is still there when printed via traverse, however my logic seems accurate.

    Traverse:
    Code:
    void traverse(llist* list,Func fnpointer){
        if(list->head == NULL){
            printf("EMPTY LIST");
            return;
        }
        lnode *head;
        head = list->head;
        while(1){
            fnpointer(head);
            head = head->next;
            if(head == list->head)
                return;
        }
    }
    My fnpointer is simply a function that prints out the data of each node, and can be ignored for purposes of trouble shooting. I know my loop is working, however it never advances on to the next node. head = head->next should be advancing it to the next node. This could be due to a previous linking error as I mentioned before, I am not sure.

    Any help here is extremely appreciated.

    In short:
    1. Traverse is failing to advance to next node, may be pointer error elsewhere (?)
    2. Remove from Front doesn't appear to actually be removing from the list (traverse still prints it).

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,458
    When you pass a pointer to list to your add and remove functions, you are getting a copy of the pointer to the start of the list. When you reassign list in your functions to point at the new node for add, or the second node after you remove the first, you are rassigning the copy of the list. Thus, after you return from your add/delete function, the original list hasn't changed. You need to do:
    Code:
    void add_front(llist **list, void *data)
    {
        ...
        (*list)->head = whatever
        ...
    }
    And similar for remove_front. Note the double pointer in the parameter list.

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Quote Originally Posted by anduril462 View Post
    When you pass a pointer to list to your add and remove functions, you are getting a copy of the pointer to the start of the list. When you reassign list in your functions to point at the new node for add, or the second node after you remove the first, you are rassigning the copy of the list. Thus, after you return from your add/delete function, the original list hasn't changed. You need to do:
    Code:
    void add_front(llist **list, void *data)
    {
        ...
        (*list)->head = whatever
        ...
    }
    And similar for remove_front. Note the double pointer in the parameter list.
    Thank you for your input, but this isn't necessarily correct. My lists are updating, the nodes are being added.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,458
    Duh, nevermind. llist is a struct that contains the head pointer. Don't know how I missed that.

    Could you provide the main function and print function you're using to test, so I don't have to recreate them?

  5. #5
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    This is the print function, called as a function pointer in traverse
    Code:
    void print_int(void* node){
        lnode *converted_node=(lnode*)node;
        int *p=(int *)converted_node->data;
        int a=*p;
        printf("data %d\n",a);
    }
    This is my main function, (runs through a bunch of different tests).
    Code:
    int main(void) {
        llist list={NULL};
        
        
      /* test case 1 - what does an empty list contain? */
      printf("TEST CASE 1\n");
      traverse(&list, print_int);
      printf("\n");
    
      /* test case 2 - what happens when you add a node to the
         front of an empty list? */
      printf("TEST CASE 2\n");
        int *p=malloc(sizeof(int));
        *p=10;
      add_front(&list, (void*)p);
      traverse(&list,print_int);
      printf("\n");
    
      /* test case 3 - what happens when you add a node to the front
         of a list with one node? */
      printf("TEST CASE 3\n");
        p=malloc(sizeof(int));
        *p=20;
      add_front(&list, (void*)p);
      traverse(&list, print_int);
      printf("\n");
    
      /* test case 4 - what happens when you add a node to the front
         of a list with more than one node? */
        printf("TEST CASE 4\n");
        p=malloc(sizeof(int));
        *p=30;
      add_front(&list, (void*)p);
      traverse(&list, print_int);
      printf("\n");
    
      /* test case 5 - what happens when you remove a node from the front
         of a list with more than one node? */
      printf("TEST CASE 5\n");
      remove_front(&list);
      traverse(&list, print_int);
      printf("\n");
    
      /* test case 6 - what happens when you remove a node from the front
         of a list with one node? */
      printf("TEST CASE 6\n");
      remove_front(&list);
      traverse(&list, print_int);
      printf("\n");
      
      return 0;
    }
    Not really sure what the issue is here, thanks for taking a look!

    EDIT: Just going to give you everything.
    Make New Node:
    Code:
    lnode* make_node(void* data) {
        lnode *tmp;
        tmp = malloc(sizeof(lnode));
        if(tmp ==NULL)
        {
            printf("make_node failed at line %d", __LINE__);
            exit(99);
        }
        tmp->data = data;
        return tmp;
    }
    Free List:
    Code:
    void free_list(llist* list) {
        if(!list->head){
            lnode *current = list->head;
            while(!current) {
                lnode *next = current->next;
                free(current);
                current = next;
            }
        }
        list->head = NULL;
    }
    Last edited by Brandon Smith; 04-10-2012 at 11:19 AM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,458
    Code:
    void add_front(llist* list, void* data) {
        lnode *n = make_node(data);
        lnode *old;
        old = list->head;
        n->next = list->head; // points new node at what head points at (old node)
        old->prev = n; // points old node to first node
        n->prev = old->prev;  // points new node to last node
        old->prev->next = n; // points last node to new first node
        list->head = n; // points head to new node
    }
    Aha!
    That line sets old->prev to the new node.
    That line sets the new node's prev pointer to old->prev (which is now n).

    When you do the red line, old->prev is no longer what you think it is. You don't even need the old pointer by the way:
    Code:
    n->next = list->head;
    n->prev = list->head->prev;
    n->next->prev = n;
    n->prev->next = n;
    EDIT: Fixed typo. The second line should be ->prev, not ->next as I originally had.
    Last edited by anduril462; 04-10-2012 at 11:44 AM.

  7. #7
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Thank you for your response, I would've never caught that it was pointing to the updated source. Whoops! However, something still doesn't seem right! My traverse function now loops forever and keeps printing the first node. ;/

    EDIT: I got rid of the "old" pointer as suggested and have everything hard coded. It now works beautifully. 1000 thanks.

    My output is now:
    Code:
    TEST CASE 1
    EMPTY LIST
    
    TEST CASE 2
    data 10
    
    TEST CASE 3
    data 10
    data 20
    
    TEST CASE 4
    data 10
    data 20
    data 30
    
    TEST CASE 5
    data 20
    data 30
    
    TEST CASE 6
    data 30
    Which is precicely the desired output.
    Last edited by Brandon Smith; 04-10-2012 at 12:27 PM.

  8. #8
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Just realized that this is actually "adding to tail".

    The output for case 3 should be "data 20; data 10"
    The output for case 4 should be "data 30; data 20; data 10"
    The output for case 5 should be "data 20; data 10"
    The output for case 6 should be "data 10"

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,458
    The code I gave you just fixed the linking the new node into the list, not updating list->head.

  10. #10
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Quote Originally Posted by anduril462 View Post
    The code I gave you just fixed the linking the new node into the list, not updating list->head.
    Doh! Got it, just missing a list->head = n; at the end of my add to front.

    Thanks so much anduril462, you've been so much help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. advice for gui front end
    By Trinity32244 in forum C Programming
    Replies: 18
    Last Post: 02-24-2011, 10:25 AM
  2. truncating front
    By jimmianlin in forum C Programming
    Replies: 2
    Last Post: 10-01-2009, 04:12 PM
  3. Window always in front
    By Magos in forum Windows Programming
    Replies: 2
    Last Post: 02-02-2003, 08:28 AM
  4. \B...No Front??
    By SavesTheDay in forum C Programming
    Replies: 4
    Last Post: 01-23-2002, 11:46 PM
  5. new look front page
    By iain in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 01-06-2002, 02:41 PM

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