Thread: help with linked lists

> Is this redundant or does it serve a dual purpose I dont see?
It's redundant.

You can just as easily do this,
append(&head, &a);

Then after each operation, you can add
printf("New head = %p\n", head );

head should change after the first call, after every prepend() call, and every delete() call which removes the first node of the list.

I don't see much point in using the double pointer in the example code, since list is passed by value, it could only be used to update head, but that would end up losing the starting point of a list.

It makes more sense to include the double pointer within a class or within a function (since you mentioned C, a C example):

Code:

node * head = NULL;                  // pointer to head of a list
node **pnext = &head;                // pointer to head or pointer to last node's next pointer
node * pnode;                        // pointer to a node
// ...

// append a node to the list

    pnode = malloc(sizeof(node));    // get a new node
    pnode->next = NULL;
    pnode->data = data;
    *pnext = pnode;                  // append it to the list
    pnext = &(pnode->next);          // advance pnext to the node's next pointer

This eliminates the need to check for head == NULL when appending to an empty list. After a series of nodes are appended to the list, head will always point to the first node of the list (or it's original NULL value), and pprev will be a pointer to the next pointer of the last node added to the list.

I also prefer to have the next pointer first:

Code:

struct node{
node * next;
int data;
};

You could have a base type of node that only has a next pointer, then other types of node with different types of data. This would allow usage of generic list functions, by casting specific types of nodes to the base node and back. This works because with C / C++, the address of the first member of a struct (or class) is the same as the address of the struct (or class).

Originally Posted by rcgldr

... and pprev will be a pointer to the next pointer of the last node added to the list.

Instead of pprev, that should have been pnext.

This example C code better demonstrates what I think the example code in the first post was trying to accomplish:

Code:

#include <stdio.h>

typedef struct node_{
struct node_ *next;
int data;
}node;

void append(node *** tail, node * pnode)
{
    **tail = pnode;
    *tail = &(pnode->next);
}

void prepend(node **head, node * pnode)
{
    pnode->next = *head;
    *head = pnode;
}

int main()
{
node * head = NULL;
node ** tail = &head;
node * pnode;
node a = {NULL, 1};
node b = {NULL, 2};
node c = {NULL, 3};
node d = {NULL, 0};
    append( &tail, &a);
    append( &tail, &b);
    append( &tail, &c);
    prepend(&head, &d);
    for(pnode = head; pnode != NULL; pnode = pnode->next)
        printf("%d\n", pnode->data);
    return(0);
}

Hey thank you that was helpful. So I asked him about changing the main and he said it was a big no. So here is what I came up with for append function:

Code:

void append(node **list, node *newNode){

node * current = *list;


if(&(current->next) != NULL){
current = &(current->next);
}


newNode = &(current->next);

}

I think this should work. However, I am not sure about prepend. I believe this add's to the front of the list rather than to the back right?

Edit: Is not working as planed for some reason it steps into the if statement at the beginning.

The way the main is written, you have to scan to find the end of the list, then assign the "end" of the list to the new node. Example code showing the append function. See if you can do the rest.

Code:

#include <stdlib.h>

typedef struct node_{
int data;
struct node_ *next;
}node;

void append(node **list, node *newNode)
{
    while(*list != NULL)
        list = &((*list)->next);
    *list = newNode;
}

int main(void)
{  
  // a reference to the head of our list
node *head = NULL;
node ** list = &head;
  
  // the nodes we will put in our list
    node a = {6,NULL};
    node b = {8,NULL};
    node c = {4,NULL};
    node d = {10,NULL};
    node e = {2,NULL};

  // build the list
    append(list, &a);
    append(list, &b);

    return 0;
}

The append function you wrote I think that *list starts off = to NULL doesn't it? So will it ever step into the while loop? I mean each time I set it to the new node it will still have a next value of NULL so it never makes the loop right?

Edit: Is this correct?:

Code:

void append(node **list, node *newNode){

node * current = *list;


if(current == NULL){
    //new list; make this node the head
    current = newNode;
}


 while(current != NULL){
    current = &((current)->next);
    current = newNode;
 }


current->next = newNode;
}

Your while loop looks wrong. The idea is to keep looping until the current node's next pointer is a null pointer. Once you have that node, you can then append the new node.

At the moment though, you're looping until the current node pointer becomes a null pointer, thus current->next dereferences a null pointer. Furthermore, within the loop itself your code does not make sense, e.g., this:

Code:

current = &((current)->next);

should have been:

Code:

current = current->next;

Originally Posted by Robert Murch

The append function you wrote I think that *list starts off = to NULL doesn't it?

Only on the first call to append. During the call to append, it sets *list = newNode, which sets head (in main) to point to 'a'.

Originally Posted by Robert Murch

So will it ever step into the while loop?

On any call after the first call to append (assuming you don't delete all the nodes). On the second call to append, head points to 'a', list points to head, so append advances it's local copy of list to a.next, and sets a.next to point to b.