A Whole Slew of problems with Linked Lists in C

Discussion in 'Programmer's Corner' started by jakegwood, Apr 28, 2012.

  1. jakegwood

    Thread Starter New Member

    Apr 13, 2011
    29
    0
    #include <stdio.h>

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

    struct List
    {
    struct Node* head;
    int size;
    };

    struct Node initNode(struct Node* nextNode, int x)
    {
    struct Node newNode;
    newNode.next = nextNode;
    newNode.data = x;
    return newNode;
    }

    struct List initList()
    {
    struct List newList;
    newList.head = NULL;
    newList.size = 0;
    return newList;
    }

    void insert(struct List* list, int x)
    {
    struct Node newNode = initNode(list->head, x);
    list->head = &newNode;
    list->size++;
    }

    void printList(struct List* list)
    {
    int k = 0;
    struct Node *current = (*list).head;
    while(current != NULL)
    {
    k++;
    printf("%d\n", current->data);
    current = (*current).next;
    if(k>50)
    {
    break;
    }
    }
    printf("The size of the list is %d",list->size);
    }



    int main()
    {
    struct List myList = initList();
    insert(&myList, 5);
    printList(&myList);
    printf("The size is %d\n", myList.size);
    int i;
    for( i = 0; i < 10; i++)
    {
    insert(&myList, i);
    }
    printf("The size is %d\n", myList.size);
    printf("%d\n", (myList.head)->data);
    printf("%d\n", myList.head);
    printList(&myList);
    }

    So here's my code. I am trying to implement a linked list. The main problem I have is with the printList. It only prints memory locations (as well as the other printf's in main that I added as tests). I've tried (*current).data which still only prints memory locations and I've tried *(current->data) which returns an error when I compile. After inserting the five, the printlist runs once, printing one memory location as expected, but then when I insert 10 more values in the for loop, then print again, I get an infinite loop and it ends up printing the same address infinitely. I tried adding that k so the printList will print a maximum of 50 times to prevent the infinite loop and that compiles fine, but when I run, the program prints one memory location (presumably the first printList) and then I get a Bus Error.

    I am already a java programmer, but C is really giving me a hell of a time.
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    Please repost your code placing it between code tags like this:

    [code=rich]
    Your code goes here.
    [/code]

    I have an errand to run, but I'll be happy to look over your code when I get back in an hour or so.
     
  3. AsmCoder8088

    New Member

    Apr 17, 2010
    15
    1
    jake,

    The problem lies in your insert function. You are storing the address of a variable that is defined in local scope. Consequently, once the function returns, that address is meaningless and will just point to garbage.

    If you change your insert function to the following:

    Code ( (Unknown Language)):
    1.  
    2. void insert(struct List* list, int x)
    3. {
    4.     //struct Node newNode = initNode(list->head, x);
    5.  
    6.     //list->head = &newNode;// using address of local variable
    7.     //list->size++;
    8.  
    9.  
    10.     struct Node *newNode = initNode(list->head, x);
    11.  
    12.     list->head = newNode;
    13.     list->size++;
    14. }
    15.  
    and then change your initNode function so that it returns a pointer to a Node:

    Code ( (Unknown Language)):
    1.  
    2. struct Node* initNode(struct Node* nextNode, int x)
    3. {
    4.     struct Node *newNode;
    5.  
    6.     newNode = (struct Node *)malloc(sizeof(struct Node));
    7.  
    8.     newNode->next = nextNode;
    9.     newNode->data = x;
    10.  
    11.     return newNode;
    12. }
    13.  
    Then your code will work. Here is the complete new code:

    Code ( (Unknown Language)):
    1.  
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4.  
    5. struct Node
    6. {
    7.     struct Node* next;
    8.     int data;
    9. };
    10.  
    11. struct List
    12. {
    13.     struct Node* head;
    14.     int size;
    15. };
    16.  
    17. struct Node* initNode(struct Node* nextNode, int x)
    18. {
    19.     struct Node *newNode;
    20.  
    21.     newNode = (struct Node *)malloc(sizeof(struct Node));
    22.  
    23.     newNode->next = nextNode;
    24.     newNode->data = x;
    25.  
    26.     return newNode;
    27. }
    28.  
    29. struct List initList()
    30. {
    31.     struct List newList;
    32.  
    33.     newList.head = NULL;
    34.     newList.size = 0;
    35.  
    36.     return newList;
    37. }
    38.  
    39. void insert(struct List* list, int x)
    40. {
    41.     //struct Node newNode = initNode(list->head, x);
    42.  
    43.     //list->head = &newNode;// using address of local variable
    44.     //list->size++;
    45.  
    46.  
    47.     struct Node *newNode = initNode(list->head, x);
    48.  
    49.     list->head = newNode;
    50.     list->size++;
    51. }
    52.  
    53. void printList(struct List* list)
    54. {
    55.     int k = 0;
    56.     struct Node *current = (*list).head;
    57.  
    58.     while (current != NULL)
    59.     {
    60.         k++;
    61.         printf("%d\n", current->data);
    62.         current = (*current).next;
    63.  
    64.         if (k>50)
    65.         {
    66.             break;
    67.         }
    68.     }
    69. }
    70.  
    71.  
    72. int main(int argc, char *szArgv[])
    73. {
    74.     struct List myList = initList();
    75.     int i;
    76.  
    77.     insert(&myList, 5);
    78.  
    79.     printList(&myList);
    80.     printf("The size is %d\n", myList.size);
    81.  
    82.    
    83.     for( i = 0; i < 10; i++)
    84.     {
    85.         insert(&myList, i);
    86.     }
    87.  
    88.     printList(&myList);
    89.     printf("The size is %d\n", myList.size);
    90.    
    91.  
    92.     return 0;
    93. }
    94.  
    The output of which looks like this:

    Code ( (Unknown Language)):
    1.  
    2. 5
    3. The size is 1
    4. 9
    5. 8
    6. 7
    7. 6
    8. 5
    9. 4
    10. 3
    11. 2
    12. 1
    13. 0
    14. 5
    15. The size is 11
    16.  
    I will add that most implementations of linked-lists tend to insert elements such that they follow a first-in, first-out (FIFO) order. But yours works as well.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    Let's examine your code piece by piece:

    Code ( (Unknown Language)):
    1.  
    2. // From main()
    3. struct List myList = initList();
    4.  
    5. // Function called
    6. struct List initList()
    7. {
    8.    struct List newList;
    9.  
    10.    newList.head = NULL;
    11.    newList.size = 0;
    12.    return newList;
    13. }
    14.  
    Here you are playing with fire because newList is an automatic variable in the function and it goes away when the function returns. However, whether by deliberation or by happenstance, you are okay because structures are returned by value and copied into the target structure just like regular variables. So what you've done is legitimate and does what you want, but it's important that you understand why both of those are true.

    Code ( (Unknown Language)):
    1.  
    2. // From main()
    3. insert(&myList, 5);
    4.  
    5. // Function called
    6. void insert(struct List* list, int x)
    7. {
    8.    struct Node newNode = initNode(list->head, x);
    9.    list->head = &newNode;
    10.    list->size++;
    11. }
    12.  
    13.  

    Here's the fire of which I spoke.

    newNode is an automatic variable that is stored on the stack. It goes away when the function returns. Now, by 'go away', I mean that it is no longer valid to assume that the information stored at that address will remain unchanged because it becomes available to other functions automatically as they are called.

    But, you store the address of this automatic variable in your structure and, hence, your linked list is expecting the information stored at that address to continue representing that data even after the function returns.

    A big point to remember is that whenever you want to create new variables that stick around, you have to allocate memory for those variables using malloc() or one of the other handful of memory allocation functions. Otherwise, you are trying to store more and more data in a conceptually fixed amount of space and something has to give.
     
  5. jakegwood

    Thread Starter New Member

    Apr 13, 2011
    29
    0
    Thanks. I was reading up on malloc some more and that helps.
     
  6. MrChips

    Moderator

    Oct 2, 2009
    12,415
    3,354
    Interesting, didn't know about , thanks for this.
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    I ran across that while looking for how to do something else.

    In your reply, you should have escaped the [plain] text by entering it as [plain][plain][/plain]. What happens if you don't is that if someone quotes the text, as I did above, the parse sees the [plain] tag and it then stops parsing and doesn't parse again until it sees the [/plain] tag (if it ever sees one). As a result, none of the tags that weren't closed out before the [plain] was encountered, including the original [QUOTE] get executed.

    But what if you want to display the [/plain] tag itself? You can't put it between a pair of noparse tags because the [/plain] tag is the one tag that the interpretter is sensitive to following a [plain] tag. It turns out that this isn't a problem because the interpretter doesn't interpret closing tags if there isn't a matching open tag that is active.

    Other links that are very useful:

    BB Code

    Smilies

    I found this list of Special Characters on Bill Marsden's blog, but I haven't figured out how to actually enter them. If I try holding down the 'Alt' key, as soon as I type anything else it is interpretted as a browser command to jump somewhere else on the page. So up until now I have been limited to finding the character I want and doing a copy-paste.

    A bit of playing around has let me figure it out. You HAVE to use the numbers on the number pad and NOT the numbers in the top row of the regular keys. I assume this is the same for a laptop keyboard, which would be a royal pain in the ass. Also, the leading 0 is significant in that it must either be there or it must be absent.

    For instance, if you use alt-0181 you get µ, but if you use alt-181 you get ╡. You alse get µ using alt-230, but I don't know if these are truly the same character in the character set. At first I assumed that the leading 0 marked the value as being octal and that, without it, the value was assumed to be decimal. But that doesn't seem to be the case since 0181 clearly isn't octal. So I don't know why the leading zero is significant.

    One thing I wish the moderators would do would be to create a single Tex reference page and then consolidate all of the various stickies on this topic there and either have a single link at the top of the page or have a sticky in each forum (that is relevant) point to it. It gets frustrating having to hunt through several in order to find the useful tidbit that you previously found.

    Tex sticky posts from:
    General Electronics Chat
    Homework Help

    Actually, it appears that there are only these two, so it's not as bad as I had thought. I guess the fact that there are multiple, even if just two, creates the impression that there is a sea of them, especially when you try to look for things that you've seen before but aren't in either one of them, you start assuming it must be in yet another one that you can't find any more. I think this is what happened to me because I was trying to track down how to do a table like one I had seen in a post and I had assumed it was Tex, but I later discovered that it was BB Code.
     
Loading...