Pointer to next Structure

Code:

---

struct list {
struct list *next_ptr;
int val;
};

---

I read that this pointer in the structure points to the next instance of the structure 'list'. I don't understand how this can do this when not implemented. So, if I do this:

Code:

---

struct list new_list;

---

How would having the pointer to another instance of 'list' aid my program? I don't really understand the relevance of this procedure. Can someone please explain this? Thanks.

A linked list starts off with the following declaration

struct list *new_list = NULL;

This represents an empty list (no elements).

To add an element to the list, you need to allocate (malloc) a list entry, like so (and fill it with data)
struct list *node = malloc( sizeof(struct list) );
node->val = 123;
node->next = NULL;

To attach this node to the (empty) list, we do this
new_list = node;

To add another node to the list, we go through the malloc process again...
struct list *node = malloc( sizeof(struct list) );
node->val = 456;
node->next = NULL;

Now things get a bit more complicated - our list is not empty. There are three cases to consider
- adding the new element to the start of the list
- adding the new element to the end of the list
- adding the new element to the middle of the list (to keep it sorted for example)

Adding to the start of the list is easy, it's just
node->next = new_list;
new_list = node;

Adding to the end of the list is only slightly more difficult, since you jump from next to next, to find the one which points to NULL.
for ( temp = new_list ; temp->next != NULL ; temp = temp->next );
temp->next = node;

Drawing this process out on paper helps a lot when you first try this.

I don't understand why you did this:
>struct list *node = malloc( sizeof(struct list) );
Why did you make node a pointer?

And I thought I understood what you were doing, but you lost me here:
>Now things get a bit more complicated - our list is not empty. >There are three cases to consider
>- adding the new element to the start of the list
>- adding the new element to the end of the list
>- adding the new element to the middle of the list (to keep it >sorted for example)
What does this mean? So, you can just keep creating more instances out of the previous instance. And then check with a loop until it is null. Is that all the structure's pointer does? Just make the next structure instance? Thanks.

Actually, you really lost me. Can you right out some code (for an instance) and then explain the linked list? Thanks. I really appreciate it.

Umm... the code shall set you free.

Code:

---

#define NODESIZE sizeof (struct identnode)

struct identnode
{
 int ident;
 struct identnode * next;
}

void addFirst (int ident); // Adds structure to beginning of list
void addLast (int ident); // Adds to end
void addAfter (int ident, int seek); // Adds after occourance
                                                      // of ident
int getNth (int nth);  // Returns the nth ident in list.. nth starts
                                // at 0, like an array

 struct identnode * list = NULL; // List points to the first node...
 // But the list is empty.  Global to make life easier.

int main ()
{
 
 addFirst (6); // list is {6}
 addFirst (4); // list is {4, 6}
 addLast (7); // list is {4, 6, 7}
 addAfter (2, 6); // list is {4, 6, 2, 7}
 return getNth (1); // returns 6
}

void addFirst (int ident)
{
 struct identnode * p = malloc (NODESIZE);
 p -> ident = ident;
 p -> next = list;
 list = p;
 return;
}

// WARNING, this code doesn't work on an empty list.
void addLast (int ident)
{
 struct identnode * p = malloc (NODESIZE);
 struct identnode * q;
 p -> ident = ident;
 p -> next = NULL; // NULL because it's the last element
  for (q = list; q -> next != NULL; q = q -> next);
 // Now q points to the last node.
 q -> next = p;
 return;
}

// WARNING, this doesn't work if seek is not in list.
void addAfter (int ident, int seek)
{
 struct identnode * p = malloc (NODESIZE);
 struct identnode * q;
 p -> ident = ident;
 for (q = list; q -> ident != seek; q = q -> next);
 // Now q points to node containing seek
 p -> next = q -> next;
 q -> next = p;
 return;
}

// WARNING, this doesn't work if nth is too big.
int getNth (int nth)
{
 struct identnode * q;
 for (q = list; n != 0; q = q -> next, n--);
 return q -> ident;
}

---

Haven't compiled the code, but it all looks kosher to me. A thing about linked lists is that you almost never have to allocate memory for one of the nodes by using "struct list new_list"; it's all pointers and malloc.

The point of lists is just to have a way to store information, in my example's case, integers, in a manner that allows you to insert information wherever you wish.

EDIT: Hope it doesn't mess up window anymore...

> Why did you make node a pointer?
Because that is all you have when you allocate memory at run time.

struct list new_list;
is allocated at compile time - so you're stuck with just one node of a list.

> So, you can just keep creating more instances out of the previous instance.
Well you use malloc to create the instance

> Is that all the structure's pointer does? Just make the next structure instance?
It doesn't make the next instance - it just points to it.

Code:

---

#include <stdio.h>
#include <stdlib.h>

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

// allocates a new list element and fills in the details
struct list *create_node ( int data ) {
    struct list *new_node = malloc( sizeof(struct list) );
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// prints a list
void print_list ( struct list *head ) {
    while ( head != NULL ) {
        printf( "%d ", head->data );
        head = head->next;
    }
    printf( "\n" );
}

struct list *add_to_tail ( struct list *head, int data ) {
    struct list *new_node = create_node( data );
    if ( head == NULL ) {
        // empty list, the new list will contain just this node
        head = new_node;
    } else {
        struct list *temp;
        // append to end of list
        // start by finding the last node in the list
        for ( temp = head ; temp->next != NULL ; temp = temp->next );
        temp->next = new_node;
    }
    return head;
}

struct list *add_to_head ( struct list *head, int data ) {
    struct list *new_node = create_node( data );
    new_node->next = head;
    return new_node;
}

int main ( ) {
    struct list *head_list = NULL, *tail_list = NULL;
    int i;
    for ( i = 0 ; i < 10 ; i++ ) {
        head_list = add_to_head( head_list, i );
        tail_list = add_to_tail( tail_list, i );
    }
    print_list( head_list );
    print_list( tail_list );
    return 0;
}

---

I'm still pretty confused. I'll just read over the code and explanations extensively and I will be sure to get it. Thanks.