Thread: Linked List - Still not understanding!

  1. #1
    Registered User
    Join Date
    Jul 2013
    Posts
    41

    Linked List - Still not understanding!

    Hi all. I'm trying to impliment a simple singly linked list, then allow a user to add a new node. I have mocked up a siimple example to illustrate my point using Linked Lists in C Tutorial - Cprogramming.com

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
            int x;
            struct node *next;
    };
    
    int main()
    {
            int x = 0;
            char input[1];
            /* print original linked list with first node(root) */
            print();
            /* get a users input of a single number */
            printf("\nEnter A Number: ");
            fgets(input,10,stdin);
            input[1] = '\0';
            x = atoi(input);
            /* use the input from user as the value of the next node */
            add(x);
            /* now print the current linked list in which I want to be root node, then new node */
            print();
            return 0;
    }
    
    int print()
    {
            struct node *root;
            struct node *node;
            /* gives root memory of size node */
            root = malloc(sizeof(struct node));
            /* says next node is node 0 */
            root->next = 0;
            /* assigns variable x of root with value 1 */
            root->x = 1;
            /* assigns node to be root */
    
            if(node != 0)
            {
                    while(node->next != 0)
                    {
                            printf("%d\n", node->x);
                            node = node->next;
                    }
                    printf("%d\n", node->x);
            }
    
            /* Creates a node at the end of the list */
            node->next = malloc(sizeof(struct node));
            node = node->next;
    
            if(node == 0)
            {
                    printf("Out of memory");
                    return 0;
            }
            return 0;
    }
    
    int add(int a)
    {
            struct node *node;
            node = malloc(sizeof(struct node));
    
            node->next = 0;
            node->x = a;
            return 0;
    }
    So I have done things similatr to this in C# and Java but not in C. There maybe some parts of this I'm sure some will disagree with in terms of buffers,overflow etc. but it's just the linked list part that I am interested in at the moment, I am only doing it like this because when it works, I will be extracting the working linked list stuff into another program that can deal with its I/O etc.

    I have tried to comment as best I can to demonstarte my intentions and understandings per line of code. The add function needs to add a node of value x that the user has input, and add that to the end of the list - I'm sure that the print function is not doing all its supposed to do - but as i've said my understanding of whats going on here is not exactly complete. Suggestions in terms of next step would be great.

    Cheers Guys and Gals.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,824
    Initialize your local variables!!!

    Change this line
    Code:
            struct node *root;
            struct node *node;
    To either
    Code:
            struct node *root = NULL;
            struct node *node  = NULL;
    or
    Code:
            struct node *root = 0;
            struct node *node  = 0;
    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Code:
    char input[1];
    
    ...
    
    printf("\nEnter A Number: ");
    fgets(input,10,stdin);
    input[1] = '\0';
    Character array input only has space for a single character. Your fgets statement allows up to 10 which invites a buffer overrun. Assuming a person only entered a 1 character number, the buffer would need to have enough for at least 2 characters, the last would be the newline which you'd then overwrite with the null character.

    Your print and add function work on local copies of variables. These local copies are destroyed when the function ends and know nothing of the variables with the same name in the other function... the node variable in function add has nothing to do with the node variable in function print. You need to create some sort of head node pointer in function main (initialized to null perhaps) and pass it into the various functions that will be working on it. Further, you leak memory when calling these functions because the pointers to the allocated memory are lost and you then have no way of accessing the memory after the functions end.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Think of a single linked list like a train. Each rail car is a node. You can couple or decouple, any car, (especially nice for adding an unknown number of nodes to your list). Each car has a coupler (the *next pointer), so it can attach to the next car in the list.

    To traverse your list, you will move from node to node as needed. Same with a train - you walk from car to car, you don't have any random node or car access abilities, unless you create one in the case of your list.

    As for your errors, hk_mp5kpdw has you covered - and I NEVER argue with Dexter!

  5. #5
    Registered User
    Join Date
    Jul 2013
    Posts
    41
    Yeah I mentioned about the memory leaks etc. that I don't car about those, this is a simple example which I will extract from when it works and put into my other robust code that doesn't have memory leaks...

    I get your point Adak and the example page I got this from reffered to linked lists in a similar fashion. But it's not the idea behind linked lists as I have said, I have created code around similar concepts before, just in other languages. I was working on it, and would post up a newer version of the code, but works has just got manic so I'm out of time right now, gimme a few hours to settle it down and see what I can come up with based on hk_mp5kpdw's help as well as yours.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help understanding linked list
    By progmateur in forum C Programming
    Replies: 4
    Last Post: 03-19-2013, 02:02 PM
  2. Doubly Linked List - Understanding...
    By hi-0ctane in forum C Programming
    Replies: 3
    Last Post: 05-31-2009, 05:27 PM
  3. understanding linked list
    By sara.stanley in forum C Programming
    Replies: 5
    Last Post: 04-14-2006, 04:32 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. Replies: 2
    Last Post: 11-28-2003, 11:50 AM