Colorblind Transformer Colorblind Transformer - 2 months ago 10
C Question

printing a doubly linked list in reverse

I have a doubly linked list that I can print top to bottom, and now I'm trying to print it from bottom to top.

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

//defines the struct UserData
typedef struct
{
int importance;
char taskName[80];
}UserData, *UserDataPtr;

//Defines a node
typedef struct node {
UserData Data;
struct node *next;
struct node *prev;
} Node, *NodePtr;

NodePtr makeNode(UserData);

//Declare function printList
void printList(NodePtr);

void printListRev(NodePtr);

int main()
{
UserData info;
NodePtr top, ptr, last, temp;



top = NULL;

FILE *filein=fopen("Data.txt", "r");
if (filein == NULL) {
printf("Error opening file, exiting program.\n");
exit(0);
}

while(fscanf(filein, "%d%s",&info.importance, info.taskName)==2)
{
ptr=makeNode(info);
if (top == NULL) top = ptr;
else last -> next = ptr;
last = ptr;
}//end while loop

printList(top);


printListRev(last);
}//end Main


//printList is a function that prints each node as long as it isn't NULL. Once it reaches NULL it terminates, signifying the end of the list.
void printList(NodePtr ptr) {
while (ptr != NULL) { //as long as there's a node
printf("%d %s\n", ptr -> Data.importance, ptr -> Data.taskName);
ptr = ptr -> next; //go on to the next node

}
if (ptr == NULL) {

printf("Last node data printed moving forward.\n");
}

} //end printList


void printListRev(NodePtr ptr) {
while(ptr != NULL){
printf("%d %s\n", ptr -> Data.importance, ptr -> Data.taskName);
ptr = ptr -> prev;


}
}//end printListRev

//Define function makeNode. Allocates storage for node, stores integer given to it, and returns a pointer to the new node. Also sets next field to NULL
NodePtr makeNode(UserData info) {
NodePtr ptr = (NodePtr) malloc(sizeof (Node));
ptr -> Data = info;
ptr -> next = NULL;
ptr -> prev = NULL;
return ptr;
} //End makeNode


This is the output:

1 task1
2 task2A
3 task3A
2 task2B
4 task4A
4 task4B
3 task3B
Last node data printed moving forward.
3 task3B


And I have no clue why it won't print the full list in reverse. It only prints one item when printing in reverse.

Everything up until the "last node data printed" message is correct. And yes, it's a little bit messy, I'm new to C and I need to clean up my comments and such. Apologies.

Can anyone help?

Answer

During the read phase, you set last->next, but you never set any prev member to anything other than NULL.

You can see this if you revise the printList() code to print the prev and next members too — using the %p conversion specifier.

For example:

void printList(NodePtr ptr)
{
    while (ptr != NULL)
    {
        printf("%d %s (N = %p, P = %p)\n", ptr->Data.importance, ptr->Data.taskName,
               (void *)ptr->next, (void *)ptr->prev);
        ptr = ptr->next;
    }
    if (ptr == NULL)
    {
        printf("Last node data printed moving forward.\n");
    }
}

When run, this produces (for me, on my Mac):

1 task1 (N = 0x7ff6a94032e0, P = 0x0)
2 task2A (N = 0x7ff6a9403370, P = 0x0)
3 task3A (N = 0x7ff6a94033e0, P = 0x0)
2 task2B (N = 0x7ff6a9403450, P = 0x0)
4 task4A (N = 0x7ff6a94034c0, P = 0x0)
4 task4B (N = 0x7ff6a9403530, P = 0x0)
3 task3B (N = 0x0, P = 0x0)
Last node data printed moving forward.
3 task3B

As you can see, there is no linking in the reverse direction, so the reverse print stops after printing one element — whichever element you point to.

Note that when you write C, you should not use spaces around either the dot . or arrow -> operators. They bind extremely tightly, and white space should not be used (for all it is syntactically legitimate). Your code is much less readable if you use such unorthodox layout.

The fix in the scanning code is simple:

    while (fscanf(filein, "%d%s", &info.importance, info.taskName) == 2)
    {
        ptr = makeNode(info);
        if (top == NULL)
            top = ptr;
        else
            last->next = ptr;
        ptr->prev = last;
        last = ptr;
    }

I also initialized last = NULL; before the loop starts; that is crucial when you use it to set the previous pointer. You were able to omit it previously, although GCC whined about 'might be used uninitialized' with my default compilation options. It actually wasn't used uninitialized, but the compiler (GCC 6.2.0) was understandably concerned.

With this change, the output is:

1 task1 (N = 0x7fa4b1602a10, P = 0x0)
2 task2A (N = 0x7fa4b1602aa0, P = 0x7fa4b16029a0)
3 task3A (N = 0x7fa4b1602b10, P = 0x7fa4b1602a10)
2 task2B (N = 0x7fa4b1602b80, P = 0x7fa4b1602aa0)
4 task4A (N = 0x7fa4b1602bf0, P = 0x7fa4b1602b10)
4 task4B (N = 0x7fa4b1602c60, P = 0x7fa4b1602b80)
3 task3B (N = 0x0, P = 0x7fa4b1602bf0)
Last node data printed moving forward.
3 task3B
4 task4B
4 task4A
2 task2B
3 task3A
2 task2A
1 task1

You could also print the node's address; that would make it easier to track that each of the list pointers is pointing to the right place:

void printList(NodePtr ptr)
{
    while (ptr != NULL)
    {
        printf("%d %s (C = %p, N = %p, P = %p)\n", ptr->Data.importance, ptr->Data.taskName,
               (void *)ptr, (void *)ptr->next, (void *)ptr->prev);
        ptr = ptr->next;
    }
    printf("Last node data printed moving forward.\n");
}

void printListRev(NodePtr ptr)
{
    while (ptr != NULL)
    {
        printf("%d %s (C = %p, N = %p, P = %p)\n", ptr->Data.importance, ptr->Data.taskName,
               (void *)ptr, (void *)ptr->next, (void *)ptr->prev);
        ptr = ptr->prev;
    }
    printf("Last node data printed moving backward.\n");
}

producing:

1 task1 (C = 0x7fd301c03270, N = 0x7fd301c032e0, P = 0x0)
2 task2A (C = 0x7fd301c032e0, N = 0x7fd301c03370, P = 0x7fd301c03270)
3 task3A (C = 0x7fd301c03370, N = 0x7fd301c033e0, P = 0x7fd301c032e0)
2 task2B (C = 0x7fd301c033e0, N = 0x7fd301c03450, P = 0x7fd301c03370)
4 task4A (C = 0x7fd301c03450, N = 0x7fd301c034c0, P = 0x7fd301c033e0)
4 task4B (C = 0x7fd301c034c0, N = 0x7fd301c03530, P = 0x7fd301c03450)
3 task3B (C = 0x7fd301c03530, N = 0x0, P = 0x7fd301c034c0)
Last node data printed moving forward.
3 task3B (C = 0x7fd301c03530, N = 0x0, P = 0x7fd301c034c0)
4 task4B (C = 0x7fd301c034c0, N = 0x7fd301c03530, P = 0x7fd301c03450)
4 task4A (C = 0x7fd301c03450, N = 0x7fd301c034c0, P = 0x7fd301c033e0)
2 task2B (C = 0x7fd301c033e0, N = 0x7fd301c03450, P = 0x7fd301c03370)
3 task3A (C = 0x7fd301c03370, N = 0x7fd301c033e0, P = 0x7fd301c032e0)
2 task2A (C = 0x7fd301c032e0, N = 0x7fd301c03370, P = 0x7fd301c03270)
1 task1 (C = 0x7fd301c03270, N = 0x7fd301c032e0, P = 0x0)
Last node data printed moving backward.
Comments