Thread: Pointer to next Structure

  1. #1
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584

    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.
    1978 Silver Anniversary Corvette

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    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.
    1978 Silver Anniversary Corvette

  4. #4
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    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.
    1978 Silver Anniversary Corvette

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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...
    Last edited by QuestionC; 09-16-2001 at 03:13 PM.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    I'm still pretty confused. I'll just read over the code and explanations extensively and I will be sure to get it. Thanks.
    1978 Silver Anniversary Corvette

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. method returning a pointer to a structure
    By nacho4d in forum C++ Programming
    Replies: 3
    Last Post: 05-25-2009, 10:01 PM
  2. Direct3D problem
    By cboard_member in forum Game Programming
    Replies: 10
    Last Post: 04-09-2006, 03:36 AM
  3. how to cast a char *mystring to a structure pointer ??
    By hanhao in forum C++ Programming
    Replies: 1
    Last Post: 03-29-2004, 08:59 AM
  4. Pointer to a structure
    By frenchfry164 in forum C Programming
    Replies: 5
    Last Post: 03-16-2002, 06:35 PM
  5. Pointer to structure problem
    By unregistered in forum C Programming
    Replies: 3
    Last Post: 12-24-2001, 07:54 AM