Thread: C Linked List - first attempt.

  1. #1
    Registered User (^Burt^)'s Avatar
    Join Date
    Sep 2013
    Posts
    26

    C Linked List - first attempt.

    Hello All

    I'm new to C and would appreciate any advice/comments on the linked list code I have created. It seems to work ok but I would like to learn the best methods, rather than just getting by.

    Thanks in advance

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
        int x;
        struct node *next;
    };
    
    struct node *createElement(int xIn)
    {
        struct node *element = malloc(sizeof(*element));
        element->x = xIn;
        element->next = 0; /*set to null and await further instruction*/
        return element;
    }
    
    struct node *findEndElement(struct node *startPoint, int display)
    {
        int endFlag = 0;
        struct node *lastElement = malloc(sizeof(struct node));
     
        /*Loop through all elements in order*/
        lastElement = startPoint;
        do
        {
            /*if the parameter to view is used: 1 is view other is not view*/
            if(display==1) 
            {
                printf("{addrs}[%d] {e}[%d] {n}[%d]\n",lastElement,lastElement->x,lastElement->next);
            }
             if(lastElement->next!=0) 
            {
                lastElement = lastElement->next;
            }
            else 
            {
                endFlag = 1;
            }
         }while(endFlag==0);
         return lastElement;
    }
    
    int main(int args, char *argv[])
    {
        struct node root;
        struct node *lastElement = malloc(sizeof(struct node));
        int x = 0;
     
        root.x = 0;
        root.next = 0;
        lastElement = findEndElement(&root,0);
        /*Add some elements just for fun*/
        for(x = 1 ; x < 11 ; x++)
       {
            lastElement->next = malloc(sizeof(struct node));
            lastElement->next = createElement(x);
            lastElement = findEndElement(&root,0);
       }
       findEndElement(&root,1); 
       return 0;
    }
    Last edited by (^Burt^); 09-16-2013 at 09:25 AM.

  2. #2
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    Always check the returned pointer from malloc to check for failed allocation.
    Also I would modify it so you can search for a particular value, rather than just showing the last element.
    Your findlastelement func is a bit odd. I wouldn't include any formatted displaying to that function as the caller should handle the display as he/she so chooses. The whole looping while endflag isn't set isn't necessary. Find a better way of ending the loop. i.e.

    Code:
    do{
    }while( lastelement->next != NULL )
    Use null instead of the number zero to be more obvious.

    All in all, a solid first attempt.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Lines 21, 47 and 56 are memory leaks.
    You don't initialise a pointer with malloc, if you immediately overwrite that pointer with some other value.

    findEndElement would be much better split into two functions.
    - appends a node to a list
    - print a list
    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.

  4. #4
    Registered User (^Burt^)'s Avatar
    Join Date
    Sep 2013
    Posts
    26
    Hey thanks guys some good pointers, pardon the pun . The memory leak advice is something i wouldn't ever have thought of, pointers and memory management bends my mind. I will post my updated efforts implementing the suggested changes for the sake of completeness.

  5. #5
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    Memory management is key to using C, so it shouldn't be shrugged off. Do research on the tool Valgrind, and use it.

    Don't forget; all dynamic memory allocated MUST be free'd by the programmer to avoid memory leaks.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    A couple more notes:

    Line 21: Use the name of the variable in the sizeof (like you did on line 12), not it's type. That way, if you change the type name, the sizeof expression will always be correct, no need to change it.
    Code:
    struct node *lastElement = malloc(sizeof(struct node));
    // change to
    struct node *lastElement = malloc(sizeof(*lastElement));
    Having a "fixed" node that is the head/root of a list is a bit atypical. Usually one creates a pointer to the node type, and initializes it to NULL to symbolize an empty list. This makes every node in the list uniform in nature, and helps you avoid mistakes like forgetting to skip the "first node" of the list, which is not a real node.
    Code:
    struct node *root = NULL;  // empty list
    root = list_append(root, x);  // creates a new node with data x, and appends it to the end, returning the new head of the list
    Note, I say "returning the new head of the list". In the case of an append (add to end) function, the head only changes when you insert the first node. The first node may also change if you have other functions like list_prepend or list_insert, that may add a new node to the beginning of the list. You can also pass in a double pointer, and modify the root that way, but I find returning the head from the function simpler.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    If you put the next pointer in a struct first, like this:
    Code:
    struct node
    {
        struct node *next;
        int x;
    }
    Then *node is the same as node->next, and **node is the same as (*node)->next. This is because the address of the first member of a structure is the same as the address of a structure in C or C++. This would allow a root pointer to a node to be treated similar to a node (with the proper casting if needed).
    Last edited by rcgldr; 09-16-2013 at 07:28 PM.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by rcgldr View Post
    If you put the next pointer in a struct first ...
    ... then you can use generic linked list functions that use a common (base) node structure (somewhat similar to using inherited classes in C++). Example:

    Code:
    #include <malloc.h>
    #include <stdio.h>
    
    typedef struct _NODE{                       /* base node struct */
        struct _NODE * next;
    }NODE;
    
    typedef struct _NODEINT{                    /* int node struct */
        struct _NODEINT * next;
        int value;
    }NODEINT;
    
    typedef struct _LIST{                       /* list struct */
        NODE * head;
        NODE * tail;
    }LIST;
    
    void AppendNode(LIST * list, NODE * pNode)  /* append node to list */
    {
        if(list == NULL || pNode == NULL)
            return;
        if(list->head == NULL)
            list->head = pNode;
        else
            list->tail->next = pNode;
        list->tail = pNode;
        pNode->next = NULL;
    }
    
    NODE * GetNode(LIST * list)                 /* get node from list */
    {
    NODE * pNode;
        if(list == NULL || list->head == NULL)
            return(NULL);
        pNode = list->head;
        list->head = list->head->next;
        if(list->head == NULL)
            list->tail = NULL;
        return(pNode);
    }
    
    int main()                                  /* main */
    {
    LIST list = {NULL, NULL};
    NODEINT * pNodeInt;
    int i;
    
        for(i = 0; i < 8; i++){                 /* test append */
            pNodeInt = malloc(sizeof(*pNodeInt));
            pNodeInt->value = i;
            AppendNode(&list, (NODE *)pNodeInt);
        }
    
        for(i = 0; i < 8; i++){                 /* test get */
            pNodeInt = (NODEINT *)GetNode(&list);
            printf("%d ", pNodeInt->value);
            free(pNodeInt);
        }
        printf("\n");
    
        return(0);
    }
    Last edited by rcgldr; 09-16-2013 at 09:09 PM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I note that <malloc.h> is non-standard; <stdlib.h> was probably intended.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by laserlight View Post
    I note that <malloc.h> is non-standard; <stdlib.h> was probably intended.
    The code example was based on very old code. I made the suggested fix of using stdlib.h instead of malloc.h. Should I repost the code with just this one line fix?

  11. #11
    Registered User (^Burt^)'s Avatar
    Join Date
    Sep 2013
    Posts
    26

    Changes

    Hello all thanks again for your input.

    I think I have implemented the suggested improvements, but I'm confused as to freeing up the dynamically assigned memory. Is there any chance of an example of how this should be done?

    Thanks


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
        struct node *next;
        int x;
    };
    
    struct node *createElement(int xIn)
    {
        struct node *element = malloc(sizeof(*element));
        if(!element) 
        { 
            printf("Out of memory\n"); 
            exit -1; 
        }
        element->next = NULL; /*set to null and await further instruction*/
        element->x = xIn;
        return element;
    }
    
    struct node *findEndElement(struct node *startPoint)
    {
        /*Loop through all elements in order*/
        do
        {
            if(startPoint->next!=NULL) 
            {
                startPoint = startPoint->next;
            }
        }while(startPoint->next);
     
        return startPoint;
    }
    
    struct node *displayList(struct node *startPoint)
    {
        do
        {
            printf("{addrs}[%d] {e}[%d] {n}[%d]\n",startPoint,startPoint->x,startPoint->next);
            if(startPoint->next!=NULL) 
            {
                startPoint = startPoint->next;
            }
        }while(startPoint->next);  /*continue until ->next is NULL*/
        return startPoint;
    }
    
    int main(int args, char *argv[])
    {
        int x = 0;
        struct node *lastElement;
        struct node *root = malloc(sizeof(root));
        if(!root)
        {
            printf("Out of memory\n");
            exit -1;
        }
        
        root->next = NULL;
        root->x = 0;
     
        lastElement = findEndElement(root);
        if(!lastElement)
        {
            printf("Could not find last element\n");
            exit -1;
        }
        
        /*Add some elements just for fun*/
        for(x = 1 ; x < 11 ; x++)
        {
            lastElement->next = malloc(sizeof(lastElement->next));
            /*Check memory allocation went to plan*/
            if(!lastElement->next) 
            { 
                printf("Out of memory\n"); 
                exit -1; 
            }
        
            lastElement->next = createElement(x);
            lastElement = findEndElement(root);
        }
        displayList(root); /*Display the list in all its glory*/
        free(root);
        free(lastElement);
        return 0;
    }
    Last edited by (^Burt^); 09-17-2013 at 01:56 AM.

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by )^^( View Post
    freeing up the dynamically assigned memory.
    Take a look at the /* test get */ loop in post #8. In addition to displaying the node values, it also frees the nodes.

  13. #13
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Code:
    struct node *root = malloc(sizeof(root));
    it should be
    Code:
    struct node *root = malloc(sizeof(*root));
    same for line 74

    line 82 makes memory leak of the chunk allocated on line 74
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  14. #14
    Registered User
    Join Date
    Sep 2013
    Posts
    2
    use free(<struct pointer>); to delete the node

  15. #15
    Registered User (^Burt^)'s Avatar
    Join Date
    Sep 2013
    Posts
    26

    Final Attempt

    Thanks for your help everyone. I see that C is going to challenge me a lot . I have implemented the suggested changes and think I now have a working solution. If nothing else I have learnt that I have much to learn.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /*the node structure*/
    struct node
    {
        struct node *next;
        int x;
    };
    
    /*Globol Variables*/
    struct node *lastNode = NULL;
    
    void createNewNode(int xIn, struct node *root)
    {
        /*create a pointer and gift it some memory for the new node*/
        struct node *element = malloc(sizeof(*element));
        
        if(!element) /*check the memory allocation took place*/
        {
            printf("Out of memory");
            exit(-1);   /*exit program showing error code -1*/
        }
        
        findLastNode(root); /*find last node in list*/
        
        if(!lastNode)   /*if last node is null*/
        {
            /*inform the user of an error - in theory this should never happen*/
            printf("The List needs a root or last node cannot be found");
            exit(-1);   
        }
        
        /*initialise the new node*/
        element->next = NULL;
        element->x = xIn;
        
        /*set the previous node to point at this node*/
        lastNode->next = element;
    }
    
    void findLastNode(struct node *startPoint)
    {
        /*loop until the next item is null i.e. this is the last node*/
        while(startPoint->next!=NULL)
        {
            startPoint = startPoint->next;        /*step forward*/
        }
        lastNode=startPoint;    /*keep the globol lastNode up to date*/
    }
    
    void displayList(struct node *root)
    {
        if(root) /*if the root element exists*/
        {
            /*show the root element*/
            printf("{addr}%d x[%d] n[%d]\n",root,root->x,root->next);
            
            /*continue to show remaining elements until no more left*/
            while(root->next!=NULL)
            {
                root = root->next; /*set the pointer to the next node in chain*/
                printf("{addr}%d x[%d] n[%d]\n",root,root->x,root->next);
            }
        }
        else
        {
            /*no root record so no list*/
            printf("Nothing to show");
        }
    }
    
    struct node *deleteList(struct node *startPoint)
    {
        struct node *tempNode;  /*create pointer to store pointer between operations*/
        
        do  /*loop until curent node is NULL i.e. no more left*/
        {
            tempNode = startPoint->next;    /*store current address before its deleted*/
            free(startPoint);               /*free up memory - delete node*/
            startPoint=tempNode;            /*reset the startPoint with backup before next iteration*/
        }while(startPoint!=NULL);
        tempNode=NULL;  /*clean up*/
        lastNode=NULL;  /*clean up*/
        return NULL;    /*kill the root node by sending NULL*/
    }
    
    int main(int args, char *argv[])
    {
        /*create a pointer to root node and gift it some memory*/
        struct node *root = malloc(sizeof(*root));
        int x = 0; /*counter variable*/
        
        /*test memory is assigned to root pointer*/
        if(!root)
        {
            printf("Memory Error");
            exit(-1);
        }
        
        /*initialise the root element*/
        root->next = NULL;
        root->x = 0;
        
        /*add some more elements to the list*/
        for(x = 1 ; x < 11 ; x++)
        {
            createNewNode(x,root);
        }
        /*display the total list*/
        displayList(root);
        
        /*delete the whole list*/
        root = deleteList(root);    /*delete list always returns NULL*/
        
        /*display the total list*/
        displayList(root);
        
        /*free up the memory used by the root pointer*/
        free(root);
        
        return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Declaring linked list inside linked list
    By blueboyz in forum C Programming
    Replies: 33
    Last Post: 04-20-2012, 10:13 AM
  2. Linked lists; My first attempt
    By relyt_123 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2007, 02:54 PM
  3. Problem with my first linked list attempt.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 11-09-2005, 04:33 AM
  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