Linked List - pointers

Question

I created a linked list and when I tried to print values of the nodes and used NULL as a bound, it didn't work. For example:

#include <iostream>

typedef struct Node;
typedef Node* Node_ptr;
struct Node
{
    int i;
    Node_ptr next;
};

int main()
{
    Node_ptr ptr, head;
    ptr = new Node;
    head = ptr;

    // load
    for(int j = 0; j < 4; j++)
    {
        ptr->next = new Node;
        ptr->i = j;
        ptr = ptr->next;
    }

    // print
    ptr = head;
    while(ptr->next != NULL)
    {
        std::cout << "print: " << ptr->i << std::endl;
        ptr = ptr->next;
    }
}

However, when I run this code, the code gets stuck in an endless loop in the while loop. It never understands that the linked list is only 5 nodes long, it just keeps on going. I can't understand why that happens.

That's not valid C or C++ code. There's missing semicolons, and a stray `typedef`, missing `}`... — Mooing Duck, Mar 30 '12 at 21:52
..and when you've fixed that, you need to do some debugging. — Martin James, Mar 30 '12 at 21:56
Not counting the missing quote after print. And `ptr = ptr->next` obviously causes an endless loop as `ptr` equals `ptr->next` so the while loop never moves any further... Please show us your real code. — Karel Petranek, Mar 30 '12 at 21:57
Now that the question has been answered, I have edited the code so that it is valid, and yet still illustrates the root cause of the problem — e.James, Mar 30 '12 at 22:12
@dark_charlie: `ptr = ptr->next` is a fairly standard way of looping through elements in a linked list. I don't see anything wrong with *that* part of the code. — e.James, Mar 30 '12 at 22:16

score 5 · Accepted Answer · answered Mar 30 '12 at 21:55

5

You probably just need to initialize your pointers (to NULL), otherwise they'll just contain garbage, and will thus also appear as being valid pointers.

For instance:

for(j = 0; j < 4; j++)
{
   ptr->next = new Node;
   (ptr->next)->next = NULL;
   ptr->i = j;
   ptr = ptr->next;
}

answered Mar 30 '12 at 21:55

sonicwave

5,952
2
33
49

+1 for identifying the cause of the problem. However, I would lean towards using a constructor rather than setting `(ptr->next)->next = NULL;` manually. – e.James Mar 30 '12 at 22:14
@e.James you don't need a constructor to initialize POD types. See my suggestion. – Luchian Grigore Mar 30 '12 at 22:18
@Luchian : I upvoted your answer, but to be fair, a constructor would certainly make things less error-prone (unless the OP needs his type to be a C++03 POD for some reason). – ildjarn Mar 30 '12 at 22:21
@LuchianGrigore: Point taken, and I upvoted your answer as well. Although, tecnically speaking, adding those parentheses is just invoking the default constructor, isn't it? – e.James Mar 30 '12 at 22:23
@e.James : `Node` is a POD type, so there is no default constructor; `new Node` uses _default-initialization_, which would already invoke the default constructor if there was one. Adding the parenthesis _value-initializes_ the object, which in turn effectively zero-initializes its data members. – ildjarn Mar 30 '12 at 22:24
@ildjarn: Cool. That makes sense. I'll stand by my initial position which was to prefer a constructor, because you never know when `Node` will stop being a POD class. – e.James Mar 30 '12 at 22:27
For reference: http://stackoverflow.com/questions/3102096/when-do-c-pod-types-get-zero-initialized – e.James Mar 30 '12 at 22:27
@e.James : Value-initialization works on non-POD types too. ;-] See §8.5 in the C++ standard for the full list of semantics. – ildjarn Mar 30 '12 at 22:30

score 4 · Answer 2 · answered Mar 30 '12 at 21:57

4

Try value initializing your Node:

ptr = new Node();

instead of

ptr = new Node;

Otherwise, you'll just have garbage in the members.

answered Mar 30 '12 at 21:57

Luchian Grigore

253,575
64
457
625

Oh, that's a much simpler solution then isn't it? – Mooing Duck Mar 30 '12 at 23:52

score 3 · Answer 3 · answered Mar 30 '12 at 21:56

while(ptr->next != NULL)

You clearly coded it to continue until ptr->next is NULL. Maybe you should set ptr->next to NULL for at least one item in the list? This is why it is common in C to memset(&object, 0, sizeof(object));, or in C++ to have a constructor.

typedef struct Node
{
  int i;
  Node* next;
  Node() : i(0), next(NULL) {} //prevents this problem
}

Linked List - pointers

3 Answers3