CODEWITHSUNDEEP
c++pointerslinked-list
q.Then
q.Then

Reputation: 2751

Segmentation fault in traversing a LinkedList

I'm new to C++ and pointers in general, but I can't seem to explain as to why I get segmentation fault in one of my two nearly identical code. I am doing a trivial task of traversing a LinkedList, here is the first way I do it:

Node * curNode = head; //Head is the pointer to the head of the LinkedList
while(curNode) {
    curNode = curNode->next;
}

This produces the desired result and traverses the entire LinkedList successfully. However, this raises a Segmentation fault error:

Node * curNode = head;
while(curNode->next != NULL) {
    curNode = curNode->next;
}

Changing the conditional to a casted boolean value or != nullptr does nothing, so it isn't the case that the conditional is raising true on null pointers. And yet, I can't seem to figure out why I get a Segmentation fault, it seems like the appropriate loop condition ensures I don't access any null pointers.

Upvotes: 0

Views: 1505

Answers (5)

Kaz
Kaz

Reputation: 58627

The rewrite:

Node * curNode = head;

// presumably, head is initialized somehow in omitted code

while(curNode->next != NULL) {
    curNode = curNode->next;
}

has two serious things wrong with it. One is the comparatively trivial problem that it doesn't consider the case when head is null. This causes a crash.

The second problem is that it's still algorithmically incorrect even if the first problem is addressed. It neglects to traverse the last node of the list.

If curNode is a non-null pointer, but curNode->next is null, this means "we have a valid node, which has no successor: curNode is the last node".

Thus the loop guard condition while (curNode->next != NULL) means "while curNode is not the last node". It is not equivalent to the first loop, which traverses the entire list, including the last node.

If traversing all but the last node is what you want, then it is correct, and we can understand why the head test is needed: if head is null, then the list is empty, and therefore it has no last node. Since it has no last node, an empty list cannot be partitioned into "last node" and "everything else". That is why it is a special case, and why the extra null check exists just for the sake of the special case. We can write it like this:

Node * curNode = head;

if (head) {  // list is not empty: visit all but the last node
    while (curNode->next != NULL) {
        curNode = curNode->next;
    }
} else { // special case: list has no last node
   // do nothing? Or maybe some special behavior.
}

If we don't need any special behavior for the special case (it is okay to do nothing), then we can write it like this:

while (head && curNode->next != NULL) { // fold the if test into the while
    curNode = curNode->next;
}

We are wastefully testing head on each iteration of the loop; however, the compiler can easily optimize that away since head isn't modified in the loop body. This is also possible:

while (curNode && curNode->next != NULL) {
    curNode = curNode->next;
}

However, it wastefully tests curNode on each iteration of the loop. We know curNode can never be null except just before the first iteration. On subsequent iterations, the value of curNode is obtained from curNode->next, and we know that curNode->next isn't null, because that was the condition on entry into the iteration. Maybe your compiler can figure this out also, though it requires a deeper analysis than optimizing away the access to head. The compiler has to follow the same data flow reasoning, that curNode is obtained from curNode->next, which is not null, but that this is only true in the second and subsequent iterations.

Upvotes: 0

Danny_ds
Danny_ds

Reputation: 11406

Well, they are not identical:

while(curNode->next != NULL) {
    curNode = curNode->next;
}

There is no initial check on curNode in this second version.

So, you need to check for curNode too:

while(curNode && curNode->next) {
    curNode = curNode->next;
}

Or start with an exta check outside the loop:

if(curNode) // This will also check for the case where `head` would be `NULL`
    while(curNode->next) {
        curNode = curNode->next;
    }
}

But this would skip the last item in the list. So your first version is preferred:

while(curNode) {
    curNode = curNode->next;
}

Upvotes: 1

Marcin Zdunek
Marcin Zdunek

Reputation: 1011

Your second code snippet is fine, so Segmentation fault error may occur only if head is NULL.

Upvotes: 0

Hatted Rooster
Hatted Rooster

Reputation: 36513

You should check if curNode is NULL too :

Node * curNode = head;
while(curNode && curNode->next != NULL) {
    curNode = curNode->next;
}

Upvotes: 1

aspiring_sarge
aspiring_sarge

Reputation: 2485

The only case where I can see this throwing a segfault is if the head pointer itself is NULL.

To ensure that head is not NULL, the following should work and prevent the segfault:

Node * curNode = head;
if (head) {
    while(curNode->next != NULL) {
        curNode = curNode->next;
    }
}

Upvotes: 5

Related Questions