Add to Front, Remove from Front, Traverse

**Brandon Smith** · 04-10-2012

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).

**anduril462** · 04-10-2012

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.

**Brandon Smith** · 04-10-2012

Originally Posted by anduril462

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.

**anduril462** · 04-10-2012

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?

**Brandon Smith** · 04-10-2012

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;
}

**anduril462** · 04-10-2012

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.

**Brandon Smith** · 04-10-2012

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.

**Brandon Smith** · 04-10-2012

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"

**anduril462** · 04-10-2012

The code I gave you just fixed the linking the new node into the list, not updating list->head.

**Brandon Smith** · 04-10-2012

Originally Posted by anduril462

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.

Thread: Add to Front, Remove from Front, Traverse

Thread Tools

Search Thread

Display

Add to Front, Remove from Front, Traverse

Similar Threads

advice for gui front end

truncating front

Window always in front

\B...No Front??

new look front page