Question about linked lists/pointers in c++

Question

The nature of pointers being NULL in C++ seems to feel arbitrary. I'm sure there's a method to it that I'm missing, but the following makes sense to me, but doesn't seem to work. I have the following method for adding a node to a linked list:

LLNode *ll; // set to NULL in constructor. void addToLL(Elem *e) { LLNode *current = ll; while(true) { // edge case of an empty list. if (ll == NULL) { ll = new LLNode(e); break; } else if (current == NULL) { current = new LLNode(e); break; } else { current = current->next; } } }

When adding a 2nd node to the list, the case for current == NULL does not get caught, so it tries to call current = current->next and crashes do to accessing invalid memory. Why would this be the case? A LLNode has a pointer to an Elem, and a pointer called next to another LLNode.

Your insertion logic is incorrect: You change the current pointer, but you never change the next pointer of any node to point to a new element in the linked list. As written, your list can never have more than one node in it. — James McNellis
– James McNellis, Commented Feb 2, 2011 at 16:14
Since you say you're setting ll to NULL in a constructor, is it a member of a class? Is this addToLL function a method of a class? — tenpn
– tenpn, Commented Feb 2, 2011 at 16:14
Sorry, for brevity I cut it down. Both ll and the method are a member of the same class. — waterbo
– waterbo, Commented Feb 2, 2011 at 16:24

James McNellis · Accepted Answer · 2011-02-02 16:11:34Z

You probably didn't set the next pointer to NULL in the LLNode constructor.

Objects of the basic types in C++ (pointer types, numeric types, etc.) have indeterminate initial values: they don't get initialized by default. You need to explicitly initialize such objects before you use them.

tadman · Accepted Answer · 2011-02-02 16:15:59Z

For this sort of thing you need a pointer to a pointer in order to strip away a lot of the needless exceptions in your implementation:

LLNode *ll = NULL; void addToLL(Elem *e) { LLNode** current = &ll; // While the current pointer to pointer is mapped to something, // step through the linked list. while (*current) current = &(*current->next); // At this point current is pointing to a NULL pointer and can // be assigned to. *current = new LLNode(e); }

The reason pointers are NULL is because that evaluates to false and allows you to do simple checks such as while (*current) without a lot of overhead. In the CPU this usually ends up being implemented as a test-if-zero operation.

Pointers are only NULL if initialized as such. In C they are often undefined unless properly initialized and referencing an uninitialized pointer is recipe for disaster. You'll want to ensure any pointers you define are always initialized to something valid before using them.

Using a pointer to a pointer works, but I wouldn't say it's "needed". I prefer solutions that avoid double indirection, even if they are slightly more verbose.
The lower the number of branches, the lower the number of logical failures possible in your implementation, plus it simplifies testing. When you're manipulating pointers, it's perfectly reasonable to use pointer-pointers just as when manipulating data it's perfectly reasonable to use pointers. It's just one level removed.

Dan Breslau · Accepted Answer · 2011-02-02 16:38:56Z

1) You say that ll is set to NULL in the constructor. But what constructor? There's no class definition here. Is ll a global variable? And are you sure that the constructor for LLNode sets the next pointer to NULL?

2) The condition

 if (ll == NULL)

can and should be checked outside of the loop, as ll is not modified inside the loop.

3) current is a local stack variable, so assigning to it will have no effect once the function exits. In particular, current = new LLNode(e) is a memory leak.

4) To add a node to the linked list, you must find the last node of the existing list, and modify its next pointer. Something like this would work:

 // ll is a field representing the first node in your existing linked list. if (ll == NULL) { ll = new LLNode(e); } else { current = ll; while (current->next != NULL) { current = current->next; } current->next = new LLNode(e); }

EDIT: Modified the above based on your comment that ll is a class member.

Looks like you've got JavaScript or something similar on the mind to be using null instead of NULL.
@tadman: Thanks, fixed. (Java, more likely. But while NULL is the convention in C++, I've seen lowercase null used as well.)

CashCow · Accepted Answer · 2011-02-02 16:43:30Z

The first thing I see in your code is that current is local, gets allocated with new but is never actually attached to the list.

Surely your code should be

else if( current->next == NULL ) { current->next = new LLNode( e ); break; }

LLNode must of course initialise next to NULL in its constructor.

Of course your list has O(N) insertion time, and if this is anything other than an exercise you should be almost certainly be using standard library containers.

You should also probably move the edge case out of the loop.

Collectives™ on Stack Overflow

Question about linked lists/pointers in c++

4 Answers 4

Comments

2 Comments

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

2 Comments

Comments

Related