Recursive method to reverse Linked List

Question

I want to optimise this code and improve it using advanced C++.

#include <iostream>
template <class T>
class LinkedList
{
 struct Node
 {
 T data;
 Node * next;
 Node(T value) : data(value), next(nullptr) {}
 };
 Node *head;
public:
 LinkedList() : head(nullptr) {}
 ~LinkedList();
 void insert(T);
 void printList();
 void recursiveReverse()
 {
 Node *temp = head;
 head = recursiveReverse(temp);
 }
private:
 Node* recursiveReverse(Node* head)
 {
 if(head == nullptr)
 return nullptr;
 if(head->next == nullptr)
 return head;
 Node *firstElement = head;
 Node *secondElement = firstElement->next;
 head = firstElement->next;
 firstElement->next = nullptr; //unlink first node
 Node *remainingList = recursiveReverse(head);
 secondElement->next = firstElement;
 return remainingList;
 }
};
template <class T>
void LinkedList<T>::insert(T data)
{
 Node *node = new Node(data);
 Node *tmp = head;
 if(tmp == nullptr)
 {
 head = node;
 }
 else
 {
 while(tmp->next != nullptr)
 {
 tmp = tmp->next;
 }
 tmp->next = node;
 }
}
template <class T>
void LinkedList<T>::printList()
{
 Node *node = head;
 while(node)
 {
 std::cout << node->data << " ";
 node = node->next;
 }
 std::cout<<"\n";
}
template <class T>
LinkedList<T>::~LinkedList()
{
 Node *tmp = nullptr;
 while(head)
 {
 tmp = head;
 head = head->next;
 delete tmp;
 }
 head = nullptr;
}
int main()
{
 LinkedList<int> ll1;
 ll1.insert(2);
 ll1.insert(3);
 ll1.insert(4);
 ll1.insert(5);
 ll1.insert(6);
 ll1.printList();
 ll1.recursiveReverse();
 ll1.printList();
}

• Cris Luengo: This code, if I understand correctly, puts all nose pointers on the stack and then builds the list. What happens if your list is longer than what fits on the stack? There is a trivial loop that you can write that doesn't need any intermediate copy of the list. Seems to me that is the better solution.
• coder: Sorry I don't understand what you are saying. Can you tell what should I do to make it a better solution?
• Jerry Coffin: From the sound of things, he's recommending something like this.
• coder: Means Iterative reversal method?
• Cris Luengo: Sorry for the short comment, I'll write up an answer explaining my thoughts on the algorithm.

Answer 1

No warnings with very pedantic clang flags, good job!

1. You have this in the destructor:

   tmp = head;
   head = head->next;
   delete tmp;
   

   You can replace this with a call to std::exchange:

   delete std::exchange(head, head->next);
   

2. Use move semantics. Node::Node unnecessarily copies value into data. It should be data(std::move(value)) so that no copy is made. Same goes for LinkedList::insert and so on.

3. Single characters should be in single quotes, not double quotes. I won't claim it's more efficient, because any compiler worth its salt is going to optimize the call to std::strlen.

4. In LinkedList::recursiveReverse the first overload, you don't need to copy head because the other overload you're calling isn't modifying its arguments (no pass by reference). You should also be able to merge both functions.

5. It might be "better" to keep a pointer to the last node in your linked list. That way, insertion is O(1) instead of O(n).

6. Mark functions that do not throw noexcept, if you compile with exceptions.

7. Mark classes that one shouldn't inherit from with final.

8. You could provide a constructor taking an std::initializer_list, so you could specify the elements of the list directly on construction.

9. Sometimes you use the implicit conversion to bool for pointers and sometimes not. It might be better to be consistent.

10. You can use in-class initializers for example for Node::next.

11. You can provide an iterator interface, so that your container works with the range for loop. For example, you can provide a public iterator, const_iterator alias to basically pointers to the individual elements inside nodes and provide begin and end as functions.

12. Please provide a copy and move constructor and assignment operator. This is known as the Rule of 5. If I copy your list, then I will probably get a double delete error at runtime, but this is not guaranteed.

• coder: How do I know which functions does not throw exceptions and I do not understand your statement in 12th point "If I copy your list, then I will probably get a double delete error at runtime, but this is not guaranteed."
• Rakete1111: @coder Well, that is a bit tricky to get right. See this q. If I copy your list, then head will get copied, but only the pointer itself, not the data. This means that now I have two instances of the list modifying the same linked list, and in the destructor of both, they will try to delete the linked list, but because they are the same, you have a problem.
• coder: You have suggested Rule of 5, so can I use these statements? LinkedList(const LinkedList& ll) = delete; //copy constructor LinkedList(const LinkedList&& ll) = delete; //move constructor LinkedList& operator=(const LinkedList& ll) = delete; //copy assignment LinkedList& operator=(const LinkedList&& ll) = delete; //move assignment ~LinkedList();
• Rakete1111: @coder Yes, that's better. But I think it would be better if you actually implement them :) Having a non-copyable and non-moveable class is not that great IMO.

Answer 2

Recursion makes some algorithms really elegant and short, and it is the natural way to implement some algorithms, such as tree traversal. Reversing a linked list is not one of those. Here I'll try to explain why.

When traversing a tree, the recursion depth is limited by the tree depth. If you have a balanced binary tree with as many elements as will fit in your memory, you have as much memory as you can address with a 64-bit pointer, and each tree element takes up only one byte (impossible because you need to store pointers, but for argument sake), your tree will have 2^64 elements (18 quintillion in US-english), but the tree will only be 64 elements deep. Using a recursive algorithm to traverse such a tree, your call stack will never have more than 64 calls on it.

In the case of your list reversal algorithm, the call stack will have as many calls on it as elements are in your list. If your list has 1 million elements, then you need 1 million recursive function calls, and your stack will contain 1 million copies of the function's variables. I don't know how well the compiler can optimize your function, but this is many megabytes of memory. You'll run out of stack space pretty quickly.

Your function recursiveReverse places a pointer to the top list element on the stack, and recursively calls itself to place a pointer to the next item on the stack, until all items are on the stack. Now the call stack will unwind, building a new tree out of the pointers on the stack. The following code does (in spirit at least) what your recursiveReverse does:

Node* stack[100000]; // however much space your stack has
Node* p = head;
int n = 0;
while(p) {
 stack[n] = p;
 p = p->next;
 ++n;
}
head = nullptr;
while(n>0) {
 --n;
 stack[n]->next = head;
 head = stack[n];
}

The code above doesn't test for out-of-bounds writing in stack. That's on purpose. Your recursive function doesn't either. If recursion depth exceeds your stack size, your program will crash. The main difference with your function is that the code above doesn't need all the function calls, which take time as well.

(Also: I haven't even tried compiling any of the code here, it's for illustration purposes only, there probably are bugs.)

If LinkedList has a swap, a push_front, a front and a pop_front method, then you can write list reversal in a trivial way:

void LinkedList::reverse() {
 LinkedList new_list;
 while(head) {
 new_list.push_front( front() );
 pop_front();
 }
 swap(new_list);
}

The above would be somewhat more efficient if one were to move elements from the one list to the other, but push_front still requires allocating a new Node for each node. So it's better of course to just move the nodes themselves, instead of the contents:

void LinkedList::reverse() {
 Node* new_head = nullptr;
 while(head) {
 Node* tmp = new_head;
 new_head = head;
 head = head->next;
 new_head->next = tmp;
 }
 head = new_head;
}

Note that this is both sorter and much more efficient than your recursive function, and probably somewhat easier to read too.

In short: If your function will ever reach a recursion depth of more than a few hundred, you need to design a non-recursive algorithm.