C++Linked list non-member function to reverse print

368 views Asked by At

So I understood how to print a single linked list in reverse order using recursion. I'm having trouble with doing it non member functions. For example in int print_reverse(IntSLList & list)) function how do you print reverse in an iterative way?

************************  .h  file **************************
class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }
    IntSLLNode(int el, IntSLLNode *ptr = 0) {
        info = el; next = ptr;
    }
    int info;
    IntSLLNode *next;
};

class IntSLList {
public:
    IntSLList() {
        head = 0;
    }
    ~IntSLList();
    int isEmpty() {
        return head == 0;
    }
    void addToHead(int);
    void addToTail(int);
    int  deleteFromHead(); // delete the head and return its info;
    int  deleteFromTail(); // delete the tail and return its info;
    bool isInList(int) const;
    void printAll() const;
    
private:
    IntSLLNode *head;
};

and here is the main

************************ main **************************
#include <iostream>
using namespace std;

#include "intSLList.h"

int print_reverse(IntSLList & list){


  if (head == NULL)  
     return;  
  printReverse(head->next); 

  cout << head->data << " ";  

 //How to compelete this in an iterative(or recursive if iterative is too much work)way ?
 //like this?       
}


int main() {

    IntSLList list;
    
    list.print_reverse(list);

}

Added the functions

1

There are 1 answers

1
Kenny Ostrom On

The header gives literally no way to access the contents of the list, other than by destroying it. So ... that's what we're going to do.

int  deleteFromTail(); // delete the tail and return its info;

Except we need to go the extra step and rebuild it, because nobody expects printing the container to destory its contents. See https://en.wikipedia.org/wiki/Principle_of_least_astonishment

#include <iostream>
#include <stack>
#include <list>

class IntSLList {
public:
    int isEmpty() { return m_list.empty(); }
    void addToHead(int i) { m_list.push_front(i); }
    void addToTail(int i) { m_list.push_back(i); }
    int  deleteFromHead() {
        int temp = m_list.front();
        m_list.pop_front();
        return temp;
    }
    int  deleteFromTail() { 
        int temp = m_list.back();
        m_list.pop_back();
        return temp;
    }

private:
    // no implementation given so I'm using std::list internally.
    std::list<int> m_list;
};

int print_reverse(IntSLList& mylist) {
    // store the data we are destroying in temp
    IntSLList temp;

    // literally the only way we can access the contents of the container is destructive so ... guess we're going there
    while (!mylist.isEmpty()) {
        int back = mylist.deleteFromTail();
        std::cout << back << std::endl;
        temp.addToHead(back);
    }

    // now rebuild the original list. I told you this would be bad.
    while (!temp.isEmpty()) {
        mylist.addToHead(temp.deleteFromTail());
    }

    // maybe this was supposed to be length, but not documented so I can return whatever I want.
    return -1;
}

int main() {
    IntSLList mylist;
    mylist.addToTail(1);
    mylist.addToTail(2);
    mylist.addToTail(3);
    print_reverse(mylist);
}

3
2
1