Print a doubly linked list in reverse order?

Question

My minimal reproducible example:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
    /** Pointer to the first node on the list (or NULL ). */
    Node *head;
    Node *last;
} List;

List *list;

List *makeList();
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {
    //Create an empty list for you to start.
    list = (List *)makeList();

    addRecord(list, 1);
    addRecord(list, 2);
    addRecord(list, 3);
    addRecord(list, 4);
    addRecord(list, 15);
    printReverse(list);
    return 0;
}

List *makeList() {
    List *list = (List *)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

Input:

1 -> 2 -> 3 -> 4 -> 15

Expected output:

15 -> 4 -> 3 -> 2 -> 1

Actual output:

segmentation fault

EDIT: Set the prev node in the linked list:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
    /** Pointer to the first node on the list (or NULL ). */
    Node *head;
    Node *last;
} List;

List *list;

List *makeList();
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {
    // Create an empty list for you to start.
    list = (List *)makeList();

    addRecord(list, 1);
    addRecord(list, 2);
    addRecord(list, 3);
    addRecord(list, 4);
    addRecord(list, 15);
    printReverse(list);
    return 0;
}

List *makeList() {
    List *list = (List *)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 
    new->prev = NULL;

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;
    list->last = new;
    new->prev = *next_p;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

With this edit made to addRecord, I keep getting an infinite loop that prints Item ID: 15 over and over again.

shouldn't it be tail = &(*tail)->prev? And why are you using pointers to pointers?Regardless, please provide a reproducible example, it can be that you are not setting to NULL some pointers or some other issue. — CuriouslyRecurringThoughts, Jul 27 '19 at 13:57

gsamaras · Accepted Answer · 2019-07-27T17:44:30.527

1) You add (append to be exact, you add it to end) your first node, with a value of 1, and you set head to it. But what about last? Isn't the last node also the first node in your list? Yes it is! Moreover, you set the next pointer to NULL, correct... But what about the prev pointer? Shouldn't it be set to NULL too, since their so no previous node? Yes again.

2) list does not need to be global, and to be honest, it shouldn't be.

3) When you do:

*next_p = new;
new->prev = *next_p;

then you say that the previous node of the newly appended node is the new node. It should be the last, which we know apriori, so we can do:

new->prev = list->last;

just after constructing the node.

4) Furthermore, when you create the empty list, the status should be that both head and last pointers are set to NULL.

5) Finally, you could simplify your print function to not use a double pointer, but just a pointer.

Putting everything together, we get:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *makeList();
static void *addRecordAtEnd(List *list, int newID);
void print(List *list);
void printReverse(List *list);

int main() 
{
  // Create an empty list for you to start.
  List* list = makeList();

  addRecordAtEnd(list, 1);
  addRecordAtEnd(list, 2);
  addRecordAtEnd(list, 3);
  addRecordAtEnd(list, 4);
  addRecordAtEnd(list, 15);
  print(list);
  printReverse(list);
  return 0;
}

List *makeList()
{
  List *list = malloc( sizeof( List ) );
  if(list != NULL)
  {
    list->head = NULL;
    list->last = NULL;
  }
  return list;
}

static void *addRecordAtEnd(List *list, int newID) 
{
  //Allocate memory for the node
  Node *new = malloc(sizeof(Node)); 

  //Add in data
  new->id = newID; 

  new->prev = list->last;
  new->next = NULL;

  list->last = new;

  // if list is empty
  if(!list->head)
  {
    list->head = new;
    return EXIT_SUCCESS;
  }

  Node **next_p = &list->head;
  while (*next_p) {
    next_p = &(*next_p)->next;
  }
  *next_p = new;

  return EXIT_SUCCESS;
}


void print(List *list)
{
  Node *current_node = list->head;
  while (current_node) {
    printf("Item ID: %d\n", current_node->id);
    current_node = current_node->next;
  }
}

void printReverse(List *list)
{
  Node *current_node = list->last;
  printf("LIST IN REVERSE ORDER:\n");

  //Traversing until tail end of linked list
  while (current_node) {
    printf("Item ID: %d\n", current_node->id);
    current_node = current_node->prev;
  }
}

Output (to also check that the next pointers are correctly set):

Item ID: 1
Item ID: 2
Item ID: 3
Item ID: 4
Item ID: 15
LIST IN REVERSE ORDER:
Item ID: 15
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1

PS: Do I cast the result of malloc? No!

I just did this, and my only output seems to be `LIST IN REVERSE ORDER:`, and none of my data is printing. I am possibly thinking there is something wrong with how my node and list are constructed? — Pomegranate Society, Jul 27 '19 at 14:02
@PomegranateSociety definitely. Please create an [MCVE](https://stackoverflow.com/help/minimal-reproducible-example), a minimal reproducible example, so that we can see.. :) — gsamaras, Jul 27 '19 at 14:04
Hi there! I just posted one, I am working through debugging it now! — Pomegranate Society, Jul 27 '19 at 14:10
Hi again gmsamaras, I made another edit to my code. Could you give me feedback? Also, I used the cast with malloc simply because that is how I was taught to do with linked list creations! — Pomegranate Society, Jul 27 '19 at 14:32
Hey @PomegranateSociety, nice attempt, and nice MCVE! I updated my answer with the solution, hope you like it! — gsamaras, Jul 27 '19 at 14:55
Why iterate to locate the last node? `list->last` already points to it. New elements can be appended to a doubly links list in constant time. — chqrlie, Jul 27 '19 at 15:05
`printList()` and `printReverse()` should **not** modify the list! Use a local variable instead of `list->head` or `list->last` to iterate from the end. These functions only work once and make the list unusable. — chqrlie, Jul 27 '19 at 15:06
@chqrlie good catch, *fixed*! You don't iterate the list to locate the last node! It just that the OP put it there I think, but I agree, it can be moved.. ;) — gsamaras, Jul 27 '19 at 15:13
Another question: why do you return `list` from `addRecordAtEnd()`? The OP had this function return a success indicator. `list` is not reallocated. — chqrlie, Jul 27 '19 at 15:17
Thank you @chqrlie for helping me improving my solution, I rolledback to OP's approach. :) — gsamaras, Jul 27 '19 at 15:21

chqrlie · Answer 2 · 2019-07-27T15:23:39.453

The problem is in function addRecord(): new->prev = *next_p;

next_p is not a pointer to the last node, it is a pointer to the next member of the last node. In this particular case, *next_p has been set to new just before.

It is simpler to not use the double pointer trick for doubly linked lists and just special case the empty list:

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new_node = (Node *)malloc(sizeof(Node)); 

    if (new_node == NULL)
        return EXIT_FAILURE;

    //Add in data
    new_node->id = newID; 
    new_node->next = NULL;
    if (list->head == NULL) {
        new_node->prev = NULL;
        list->head = new_node;
    } else {
        new_node->prev = list->last;
        list->last->next = new_node;
    }
    list->last = new_node;
    return EXIT_SUCCESS;
}

Similarly, the print function can be written without a double pointer:

static void printReverse(List *list) {
    // Traversing until tail end of linked list
    printf("LIST IN REVERSE ORDER:\n");
    for (Node *node = list->last; node; node = node->prev) {
        printf("Item ID: %d\n", node->id);
    }
}

Note that the initialization function must initialize last too for printReverse to handle empty lists correctly:

List *makeList() {
    List *list = (List *)malloc(sizeof(List));
    if (list != NULL) {
        list->head = list->last = NULL;
    }
    return list;
}

Nice answer as well, +1 for the check of whether the list is NULL or not in the `makeList()`. — gsamaras, Jul 27 '19 at 15:22

Print a doubly linked list in reverse order?

2 Answers2

Linked