Printing my linked list in reverse order in C++

Question

So I'm fairly new to C++ and today I decided to sit down and understand how linked lists work. I'm having a lot of fun doing it so far, but I've encountered a problem when trying to print my linked list in reverse order (not reverse the order of the linked list!)

Also, I wanted to do this without having a double linked list:

#include <iostream>
#include <string>

using namespace std;

class LinkedList
{
    public:
        LinkedList()
        {
            head = NULL;
        }

        void addItem(string x)
        {
            if(head == NULL)
            {
                head = new node();
                head->next = NULL;
                head->data = x;
            } else {
                node* temp = head;
                while(temp->next != NULL)
                    temp = temp->next;

                node* newNode = new node();
                newNode->data = x;
                newNode->next = NULL;
                temp->next = newNode;
            }
        }
        void printList()
        {
            node *temp = head;
            while(temp->next != NULL)
            {
                cout << temp->data << endl;
                temp = temp->next;
            }
            cout << temp->data << endl;
        }

        void addToHead(string x)
        {
            node *temp = head;
            head = new node;
            head->next = temp;
            head->data = x;
        }

        int countItems()
        {
            int count = 1;
            for(node* temp = head; temp->next != NULL; temp = temp->next)
                ++count;
            return count;
        }

        void printReverse()
        {
            node* temp2;
            node* temp = head;
            while(temp->next != NULL)
                temp = temp->next;

            //Print last node before we enter loop
            cout << temp->data << endl;

            for(double count = countItems() / 2; count != 0; --count)
            {
                //Set temp2 before temp
                temp2 = head;
                while(temp2->next != temp)
                    temp2 = temp2->next;
                cout << temp2->data << endl;

                //Set temp before temp2
                temp = head;
                while(temp->next != temp2)
                    temp = temp->next;
                cout << temp->data << endl;
            }
            cout << "EXIT LOOP" << endl;
        }

    private:
        struct node
        {
            string data;
            node *next;
        }

    *head;
};

int main()
{
    LinkedList names;

    names.addItem("This");
    names.addItem("is");
    names.addItem("a");
    names.addItem("test");
    names.addItem("sentence");
    names.addItem("for");
    names.addItem("the");
    names.addItem("linked");
    names.addItem("list");

    names.printList();

    cout << endl;

    names.addToHead("insert");

    names.printList();

    cout << endl;

    cout << names.countItems() << endl;

    cout << "Print reverse: " << endl;
    names.printReverse();
    cout << endl;

    return 0;
}

Now I'm not sure exactly why my code crashes, any help is appreciated!

Thanks!

Manion

What do you mean your code crashes? How does it crash? What happens when you run it? – Cumings

Since the code works with an odd number of elements (without the "insert" element), but fails with an even number, that should give you a hint... – Hubble

@SethCarnegie: Why do you say that? – Headset

@JonPurdy oh I guess they do, somehow I was under the impression that only integral types had those operators. – Caskey

An O(n²) linked list printing utility. Impressive. – Pluri

Tomorrow you should decide if you want to sit down and write code that causes a stack overflow – Fley

+1 Just because you seem willing to learn stuff, which is (sadly) rarely seen in beginners questions on Stack Overflow. – Lowther

@DougRamsey Sorry for not providing more info about that. This was my first post here, I'll keep it in mind next time. – Manion

Answer 1

Within printList, you have to also check for head == NULL, otherwise you are acessing members of a pointer pointing to NULL. The following should work.

    void printList()
    {
        node *temp = head;
        while(temp != NULL) // don't access ->next
        {
            cout << temp->data << endl;
            temp = temp->next;
        }
    }

In printReverse() I really can't understand why you take half of the counts of the elements to print and print two elements in every iteration. However, you really don't need a for-loop here. You can simply stop as soon as temp == head after your loop, since then you just printed the head. And only print one element, the one whose next pointer points to the previously printed element.

Another, recursive, attempt to solve the problem looks like this:

    void printReverse()
    {
        printReverseRecursive(head);
    }
    void printReverseRecursive(node *n)
    {
        if(n) {
            printReverseRecursive(n->next);
            cout << n->data << endl;
        }
    }

Lowther

This is not the real problem. The problem is in the fact that count never reaches zero when countItems() is odd. – Pluri

@Pluri Nope. countItems() / 2 evaluates to an int. (Although the use of a double as a counter is totally WTF) – Byer

@AndreiTita: oops, true. Point taken. – Pluri

@Pluri Yeah you're right, however this was the first thing I've seen. Updated my answer. – Lowther

+1, i should have looked at yours before writing mine. But this is ridiculously easy (for us) – Fley

@acidzombie24 It happens often that people write almost the same answer. +1 back ;) – Lowther

@AndreiTita Oh God I can't believe I left that in there. It used to be an int, obviously, but while trying to figure out why it crashed I just changed it to see. I forgot to change it back. The shame... – Manion

@AndreiTita Maybe you didn't know: GLSL, the OpenGL shading language, used to have (in its first version) only floating point types (no integral types). So you wrote your for-loop with floats. This was because it's code running on the graphics card whose hardware focuses on floating point operations. (Doesn't having anything to do with the C++ double here, but it just reminded of that :D) – Lowther

@Lowther Good call about printList(), I'll fix that. About printReverse(), my train of thought was that I needed to set a second pointer before the first pointer, because my node doesn't contain a reference to the one it links to, only the next one after. I'll try to figure it out without using a recursive function (I haven't learned those yet) – Manion

@Marcan: DONT do it without recursion. Its... just wrong. Also you already know functions. Recursive functions are just what we call them when a function calls itself. – Fley

@acidzombie24 Would you mind elaborating on why it's just wrong? I'm genuinely curious. Is it only because whenever possible I should use recursive functions? Thanks. – Manion

@Marcan: Then learn it. It's a basic thing, I'd say even before classes, pointers, and data-structures. Write the Fibonacci function or factorial numbers using recursive functions, then try to convert them to an iterative function by yourself to get a feeling for it. – Lowther

@Marcan: Nevermind, I thought the only way to do it would be poorly implemented but I thought of a way that requires a few temp vars and its pretty ok to read. I was wrong. However the backwards printing in both this and my answer is pretty easy to understand. – Fley

Answer 2

You should consider re-writing your loop to start at the last element (as you have done) and have your loop condition stop when you reach the head. Having double the code inside your for loop, along with the odd count/2 logic is certainly confusing you (and us).

temp = [last element]

while not at head
    print temp
    temp = previous element

print head

Note that you already have the code for the temp = previous element part:

temp2 = head;
while(temp2->next != temp)
    temp2 = temp2->next;

Since I assume this is an assignment of some type, I'm intentionally not giving you the c++ code for this. Even if it isn't assignment, working through it with this in mind should be the learning experience you're after. However, if you give it a shot and still have a problem, feel free to update your question (or post a new one).

Hubble

Thanks for your answer. It isn't for an assignment, but still I much prefer not being spoon fed the answer like that. I'll see if I can figure it out by myself after your hint. – Manion

@Manion You have all of the basic elements in your code already, you just need to remove some code and modify your loop to be a while loop instead of a for loop. – Hubble

This isn't even right you can't loop backwards... Its a single link – Fley

@acid That's part of the challenge of his question. Note that I didn't say temp2 = temp2->previous our anything like that, because obviously that would require a doubly linked list. But that doesn't mean that there isn't a way to get the previous element. Other answers suggest using recursion, which is viable for small lists, but if the list can be large and you need to print it backwards rarely (hopefully), there are ways to get the previous element (e.g. walk the list again, keep a separate list, etc.). This seems to be for learning so I doubt performance is a concern anyway. – Hubble

@JaredC: After thinking about it, there is a way to implement a loop without it being crazy painful (like n*n). Ok thats good enough for me – Fley

+1 even though your hint confuses me too. I'm positive you cant do the solution if you are replacing temp2 as now you have no references to the current node (temp). Also its awkward to start at next, why wouldnt you check temp2 is null at the start. Also the temp makes no sense there. – Fley

Answer 3

void printReverse()
{
    printReverse(head) //kickstart the overload function below
}
void printReverse(node *n)
{
    if(n == 0) return;
    printReverse(n->next);   //print the next
    cout << n->data << endl; //before printing me
}

Fley

Answer 4

for(double count = countItems() / 2; count != 0; --count)
            {
                //Set temp2 before temp
                temp2 = head;
                while(temp2->next != temp)
                    temp2 = temp2->next;
                cout << temp2->data<< "   " << endl;

                //Set temp before temp2
                temp = head;
                while(temp->next != temp2)
                    temp = temp->next;
                cout << temp->data << "   "<< endl;
            }
            cout << "EXIT LOOP" << endl;

Your program crashes because of the second loop. Hint: Go through it with only two elements added to the list, e.g."Hello" -> "You" -> NULL. And look closer to your loop-predicate (temp->next != temp2).

Fruit

Answer 5

void ReversePrint(Node *head)
{    
    Node *curNode=head;

    if(curNode!=NULL){
        if(curNode->next!=NULL){
            ReversePrint(curNode->next);
        }
        cout << curNode->data << endl;
    }
}

Hollie

Answer 6

print statement should be in this manner:

void print() {
    node *temp;
    temp= head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

Lytton

Answer 7

Iterative version of reversePrint that won't overflow the stack on a large list. Note the undo code is the reverse (up down) and mirror (left right) of the reverse code.

        void reversePrint()
        {
            if(head == NULL)
                return;
            node *prev = NULL;          // reverse list
            node *curr = head;
            node *next;
            while(curr != NULL)
            {
                next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            while(prev != NULL)         // undo and print
            {
                next = curr;
                curr = prev;
                cout << curr->data << endl;
                prev = curr->next;
                curr->next = next;
            }
        }

or reverse could be a separate function, but this would make three passes over the list:

        void reverse()
        {
            if(head == NULL)
                return;
            node *prev = NULL;
            node *curr = head;
            node *next;
            while(curr != NULL)
            {
                next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            head = prev;
        }

        void reversePrint()
        {
            reverse();
            printList();
            reverse();
        }

---

printList() is not checking for an empty list. Fix:

        void printList()
        {
            if(head == NULL)
                return;
            // ...

Creaturely