Linked list

This is a discussion on Linked list within the C Programming forums, part of the General Programming Boards category; Hi guys, I'm a guy learning C, and I have a problems doing something simple like traversing a linked list. ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    1

    Linked list

    Hi guys, I'm a guy learning C, and I have a problems doing something simple like traversing a linked list.

    The list is defined by these files: (no need to read all of that really, the problem is at the end of the post)

    Code:
    #include <stdio.h>#include <stdlib.h>
    #include "list.h"
    
    
    
    
    /*
     * List implementation
     */
     
    typedef struct listnode node_t;
    struct listnode {
        node_t    *next;
        void        *item;
    };
    
    
    struct list {
        node_t     *head;
        int     numitems;
    };
    
    
    
    
    // Create new list
    list_t *list_create(void)
    {
        list_t *list;
    
    
        list = (list_t*)malloc(sizeof(list_t));
        if (list == NULL)
            goto error;
        list->head = NULL;
        list->numitems = 0;
    
    
        return list;
     error:
        return NULL;
    }
    
    
    // Free list. items not freed.
    void list_destroy(list_t *list)
    {
        node_t *node, *tmp;
    
    
        node = list->head;
        while (node != NULL) {
            tmp = node->next;
            free(node);
            node = tmp;
        }
        free(list);
    }
    
    
    
    
    // Create new list node.  Function declared static => only visible within this file
    static node_t *list_newnode(void *item)
    { 
        node_t *node;
    
    
        node = (node_t*)malloc(sizeof(node_t));
        if (node == NULL)
            goto error;
        node->next = NULL;
        node->item = item;
    
    
        return node;
     error:
        return NULL;
    }
    
    
    // Free list node. Return node item
    static void *list_destroynode(node_t *node)
    {
        void *item;
        
        item = node->item;
        free(node);
        return item;
    }
    
    
    // Insert item first in list
    int list_addfirst(list_t *list, void *item)
    {
        node_t *node;
    
    
        node = list_newnode(item);
        if (node == NULL)
            goto error;
    
    
        if (list->head != NULL)
            node->next = list->head;
        list->head = node;
        list->numitems++;
    
    
        return 0;
     error:
        return -1;
    }
    
    
    
    
    // Insert item last in list.
    int list_addlast(list_t *list, void *item)
    {
        node_t *node, *current;
    
    
        node = list_newnode(item);
        if (node == NULL)
            goto error;
    
    
        current = list->head;
        if (current == NULL) {
        // Empty list, insert first
            list->head = node;
        } else if (current->next == NULL) {
        // List contains one item, insert after head
            current->next = node;
        } else {
        // Traverse until current points to node before last node
            while (current->next->next != NULL) {
                current = current->next;
        }
            current->next->next = node;
        }
        list->numitems++;
    
    
        return 0;
     error:
        return -1;
    }
    
    
    
    
    void *list_removefirst(list_t *list)
    {
        node_t    *node;
    
    
        if (list->head == NULL)
            return NULL;
        node = list->head;
        list->head = node->next;
        list->numitems--;
        return list_destroynode(node);
    }
    
    
    
    
    
    
    // Remove item from list
    int list_remove(list_t *list, void *item)
    {
        node_t *current;
        node_t *node;
    
    
        node = NULL;
        if (list->head == NULL) {
        // Empty list
            goto error;
        } else if (list->head->item == item) {
        // Remove head
        node = list->head;
            list->head = node->next;
        } else {
        // Search for item
        // NOTE: AND conditions (&&) inside for/while/if are evaluated from left to right. 
        //     If one fails, the remaining conditions are not evaluated.
        current = list->head;
            while (current->next != NULL && current->next->item != item)
          current = current->next;
        if (current->next == NULL)
          goto error;
        node = current->next;
        current->next = node->next;
        }
        
        list_destroynode(node);
        list->numitems--;
        return 0;
    error:
        return -1;
    }
    
    
    
    
    
    
    
    
    // Return # of items in list
    int list_size(list_t *list)
    {
        return list->numitems;   
    }
    
    
    
    
    
    
    /*
     * Iterator implementation
     */
     
    
    
    struct list_iterator {
        node_t *next;
        list_t *list;
    };
    
    
    
    
    // Create new list iterator
    list_iterator_t *list_createiterator(list_t *list)
    {
        list_iterator_t *iter;
    
    
        iter = (list_iterator_t*)malloc(sizeof(list_iterator_t));
        if (iter == NULL)
            goto error;
        iter->list = list;
        iter->next = list->head;
    
    
        return iter;
     error:
        return NULL;
    }
    
    
    
    
    // Free iterator
    void list_destroyiterator(list_iterator_t *iter)
    {
        free(iter);
    }
    
    
    
    
    // Move iterator to next item in list and return current.
    void *list_next(list_iterator_t *iter)
    {
        void *item;
    
    
        item = NULL;
        if (iter->next != NULL) {
            item = iter->next->item;
            iter->next = iter->next->next;
        }
    
    
        return item;
    }
    
    
    
    
    // Let iterator point to first item in list again
    void list_resetiterator(list_iterator_t *iter)
    {
        iter->next = iter->list->head;   
    }
    Code:
    #ifndef LIST_H_#define LIST_H_
    
    
    /*
     * List interface
     */
    
    
    struct list;
    typedef struct list list_t;
    
    
    // Create new list
    list_t *list_create(void);
    
    
    // Free list. All nodes are freed, but not items pointed to by nodes.
    void list_destroy(list_t *list);
    
    
    // Insert item first in list
    int list_addfirst(list_t *list, void *item);
    
    
    // Insert item last in list
    int list_addlast(list_t *list, void *item);
    
    
    // Remove first item in list
    void *list_removefirst(list_t *list);
    
    
    // Remove item from list
    int list_remove(list_t *list, void *item);
    
    
    // Return # of items in list
    int list_size(list_t *list);
    
    
    
    
    
    
    /*
     * List iterator interface
     */
     
    struct list_iterator;
    typedef struct list_iterator list_iterator_t;
    
    
    // Create new list iterator
    list_iterator_t *list_createiterator(list_t *list);
    
    
    // Free iterator
    void list_destroyiterator(list_iterator_t *iter);
    
    
    // Move iterator to next item and return current
    void *list_next(list_iterator_t *iter);
    
    
    // Let iterator point to first item in list
    void list_resetiterator(list_iterator_t *iter);
    
    
    #endif /*LIST_H_*/


    Now in my main.c, I have this bunch of objects, which are just geometrical data. (triangles and stuff). They are defined through object_t.

    My plan is that each of these objects should be placed in the linked list, and then I could loop through the list and send each object to a function called DrawObject().

    Code:
    //It calls a function CreateObject that basically initializes some of it's values. The parameters are just (SDL_surface, model, number of  triangles in the model)
    object_t *testobject1 = CreateObject(screen, triangle_model, 3);
    object_t *testobject2 = CreateObject(screen, triangle_model, 3);
    object_t *testobject3 = CreateObject(screen, triangle_model, 3);
    
    list_t *geoList = list_create();
    list_addfirst(geoList, testobject1);
    list_addlast(geoList, testobject2);
    list_addlast(geoList, testobject3);
    
    list_iterator_t *iterator = list_createiterator(geoList);
    
    int j = 0; 
    while (j < list_size(geoList))
    {
                DrawObject(geoList);
                geoList = list_next(iterator)
                j++; 
    }
    SDL_UpdateRect(screen, 0, 0, screen->w, screen->h);
    The program hangs and nothing is drawn, and I get the following error message: warning: passing arg 1 of `DrawObject' from incompatible pointer type.

    The drawobject function is supposed to recieve a parameter or type DrawObject(object_t *object);.
    So I assume it's something wrong with the way I try to pass the list elements to it. Any suggestions are appreciated.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Of course you're getting that error. You pass geoList to DrawObject, but geoList is a pointer to list_t, not a pointer to object_t or a void pointer, so the types are incompatible. list_next returns the item, which is of void * type (but actually contains an object_t pointer since that's what you added). You assign that to geoList, which is of type list_t pointer. Then, you call list_size(geoList) on the next iteration of the loop, but geoList no longer points to a valid list_t object, it points to an object_t, so list_size is operating on bogus data. This also trashes geoList, so you can't free it when you're done. You need another pointer to hold the return value from list_next:
    Code:
    list_iterator_t *iterator = list_createiterator(geoList);
    void *item;
    
    for (j = 0; j < list_size(geoList); j++) {
        item = list_next(iterator);
        // do something with item
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 11:19 PM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  3. linked list and damn on linked list
    By St0rM-MaN in forum C Programming
    Replies: 13
    Last Post: 07-03-2007, 05:08 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 02:45 AM

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