Printing Doubly Linked Lists

Question

I'm currently learning how to work with linked lists, specifically, doubly linked lists, and I have come across a problem with my program when I attempt to print it backwards.

Here is the portion of the code that I need help with:

#include <iostream>

using namespace std;

struct node
{
    int data; //int to store data in the list
    node *next; //pointer to next value in list
    node *prev; //pointer to previous value in list
};

node *appendList(node *current, int newData) //Function to create new nodes in the list
{
    node *newNode; //create a new node
    newNode = new node;
    newNode->data = newData; //Assign data to it
    newNode->next = NULL; //At end of list so it points to NULL
    newNode->prev = current; //Link new node to the previous value
    current->next = newNode; //Link current to the new node
    return newNode; //return the new node
}

node *createList(int maxLoop, node *begin, node *current, node *end) //Function to create list
{
    //Allocate the starting node
    current = new node;
    current -> data = 1; //First data value is 1
    current -> next = NULL; //next value is NULL
    current -> prev = NULL; //previous value is NULL
    begin = current; //This is the beginning of the list

    for (int count = 2; count <= maxLoop; count++) //Loop to fill the list
    {
        current = appendList(current, count*count); //Create new nodes and fill with square numbers
    }
    end = current; //Now we are at the end of the list
    return begin; //Return begin, this is the problem; I can't return end as well
}

void printForward (node *p) //Function to print the list forwards
{
    node *curr = p; //current is the beginning value of the list
    while (curr != NULL) //Continue while current is not at the end of the list
    {
        cout << curr->data << " "; //Print out the data of current
        curr = curr->next; //Move one value along in the list
    }
}

void printBackward (node *p) //Function to print the list backwards
{
    node *curr = p; //current is the end value of the list
    while (curr != NULL) //Continue while current is not at the beginning of the list
    {
        cout << curr->data << " "; //Print out the data of current
        curr = curr->prev; //Move one value back in the list
    }
}

int main()
{
    //Initialize current, begin, and end
    node *current = NULL; 
    node *begin = NULL;
    node *end = NULL;
    int maxLoop = 10; //The number of items in the list

    cout << "The list has now been created." << endl;
    begin = createList(maxLoop, begin, current, end); //function to create the list
    cout << "Printed forwards, this list is: ";
    printForward(begin); //Function to print the list forwards
    cout << endl;
    cout << "Printed backwards, this list is: ";
    printBackward(end); //Function to print the list backwards
    cout << endl;
    return 0;
}

The purpose of this program is to create a list, print it forwards, backwards, insert an element, erase an element, and then destroy the list. I have chopped it down to just the create, print forward, and print backward functions.

The issue I have is that in the createList function I am modifying both begin and end but I can only return one or the other. This means that whichever I don't return is still NULL in the main function and therefore does not point to anything. I've tried setting the begin/current/end to not equal NULL but createList won't work if I do that.

Does anyone have any ideas for how I could modify both? Just to be clear, the list HAS TO be created in a function, it would be very easy to just initialize it in the main.

Thanks, Tristan

Answer 1

Your problem is you're copying the pointers, when you should be passing them by reference, i.e., using a pointer-to-pointer or reference-to-pointer rather than just copying the value the pointer in main is originally pointing to. With what you're doing, you're unable to modify the original pointer variable that was declared in main ... passing-by-reference will allow you to-do that while also keeping all list setup code within your functions.

So for instance, change

node* createList(int maxLoop, node *begin, node *current, node *end)

to

void createList(int maxLoop, node** begin, node** current, node** end)

and then make sure to take the extra dereference into account in the body of your function

Finally, you would call it like:

createList(maxLoop, &begin, &current, &end);

And do the final assign to begin inside the body of the function of createList rather than in main.