Doubly linked list in C (printing)

Question

I've created doubly linked list and I managed to print it going forward from head to tail, however I`m having trouble in doing it backwards. I get segmentation fault in line "current = current->prev", I don't understand why.

current = head;

while (current) {
  printf("%p\t%s\t%d\n", current, current->name, current->age); 
  current = current->next;
}

current = current->prev;

while (current) {
  printf("%p\t%s\t%d\n", current, current->name, current->age); 
  current = current->prev;
}

I have found how to fix this problem:

current = head;

while (current) {
  printf("%p\t%s\t%d\n", current, current->name, current->age); 
  current = current->next;
}

current = head;
while (current->next) current = current->next;

while (current) {
  printf("%p\t%s\t%d\n", current, current->name, current->age); 
  current = current->prev;
}

However, I still don't understand why my method didn't work. I would thankful if somebody could explain this.

Hint: prefer for(current = head; current; current = current->next) {...} loops. It saves you more than two lines. /style — wildplasser

paxdiablo paxdiablo · Accepted Answer · 2015-01-28T22:32:25

When you finish the loop traversing in a forward direction, current will be set to NULL, so using the line:

current = current->prev;

is not going to end well. You are not allowed to dereference NULL.

The reason your second code snippet works is because of this:

current = head;
while (current->next) current = current->next;

It leaves current pointing to the last item in the list rather than NULL.

Most doubly linked lists tend to have both a head and a tail and you would use the latter for a reverse scan.

If you don't have a tail, that second code snippet may seem like an acceptable way to find the end, though less efficiently than it would be with a tail.

However, it has one fatal flaw, which is that it will probably misbehave if the list is empty:

current = head;                 // current <- NULL
while (current->next)           // cannot dereference NULL
    current = current->next;

You would be better off with something like:

current = head;
if (current != NULL)
    while (current->next != NULL)
        current = current->next;

That will leave current set to NULL if the list is empty, or set to the address of the last item if it's not. That means your reverse loop will then work correctly:

while (current != NULL) {
    doSomethingWith (current);
    current = current->prev;
}

Doubly linked list in C (printing)

2 Answers