# Print element in a linked list in reverse

I solved this problem in C++ and was looking for feedback on my code. I'm not sure if storing the data in an array and looping through it in reverse and printing was the right approach since this challenge was to use linked lists, but I didn't know how else to do it:

You are given the pointer to the head node of a linked list and you need to print all its elements in reverse order from tail to head, one element per line. The head pointer may be null meaning that the list is empty - in that case, do not print anything!

/*
Print elements of a linked list in reverse order as standard output
head pointer could be NULL as well for empty list
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
void ReversePrint(Node *head)
{
// creates nodes named current, prev, next
struct Node *current, *prev, *next;
// sets current and previous to their respective values. current is head because it is starting position while previous is where we want the head to be pointing, which is null, since we are reverse a linked list
current = head;
prev = NULL;
// allocate memory to an array and initialize i=0
int array[100], i=0;
while (current != NULL) {
// store data into an array to print out later
array[i] = current->data;
i+=1;
// updates next [current, link] -> [int, link] = next
next = current->next;
// updates link of current.next to value of previous
current->next = prev;
// updates previous value
prev = current;
// updates current value
current = next;
}
// at the end of list, sets head to the last value in linked list which is previous
head = prev;
// goes through array in reverse order and prints
for(int j=i-1; j>=0; j--) {
cout<<array[j]<<endl;
}
}

• the problem doesnt mention an upper limit on the list size, so this solution is invalid. Commented Jul 27, 2016 at 1:01
• It's possible to do this with O(1) memory requirements by reversing the linked list in place, printing it, then reversing it again. The best solution depends on how you're trying to optimize the code. Commented Jul 27, 2016 at 1:46

## 3 Answers

This approach is fine if you know the linked list will always be less than 100 elements. To fix this issue while still using the same method, you could iterate through the linked list first to count the number of elements needed in your array.

If I were doing this problem, I'd look at using a stack... just push all the elements onto the stack, then pop them all off again to print them. This way we avoid iterating through the linked list twice (once to count, once to store in an array), while still solving to problem.

I figured it out using a recursive function. What it does is it loops through the linked list until the end, creating a recursion tree, then executes the print in reverse, when going down the recursion tree.

    void ReversePrint(Node *head)
{
if (head == NULL) {
return;
}
// recursion tree. loops through until end of linked list
ReversePrint(head->next);
// once the recursive is done, then prints head->data going back down the recursion tree.
printf("%d\n", head->data);
}

• Since this is Code Review, you should also mention why you think this is a better solution. Commented Jul 27, 2016 at 0:05
• problem here is the the problem doesnt state an upper bound for the list size, recursion is gonna fail if you have thousands of objects. (Unless you have an awesome compiler that can optimize to tail recursion to chaining) Commented Jul 27, 2016 at 1:01
• @pm100 I doubt that any compiler would do that, since this function is not tail-recursive. Commented Jul 27, 2016 at 1:24
• I think this is a better solution because it is cleaner, but it is also recursive so as @pm100 mentioned, it will fail with thousands of objects because it will use up too much memory in the stack Commented Jul 27, 2016 at 3:49

In terms of making things cleaner, @Clefairy code does justice. Few things I could point out here is

• You want to make your ReversePrint more generic, so it wise to use STL Containers i.e vector<int> . Using an Array, the size has to be fixed and can not be dynamic.
• You need all these variables *current, *prev, *next as you don't have to track the nodes. All you need to do is keep changing head to head->next till head is null, just like I have done below.

void ReversePrint( Node *head ) {
std::vector<int> nodeList;
if ( head != NULL ) {

while ( head != NULL ) {
nodeList.push_back( head->data );
head = head->next;
}

for ( std::vector<int>::iterator it = nodeList.end() - 1; it != nodeList.begin() - 1; --it ) {
std::cout << *it << endl;
}
}
}

• To print from the last item, vector provides functions like begin , end that allows you change the location of the iterator as shown above

• Just to make your code look neater, separate each variable declaration e.g struct Node *current, *prev, *next

to

struct Node *current,
*prev,
*next;