Linked List reversal

Question

Recursive version. The only interesting function:

 List& List::reverse()
 {
 if (empty())
 { return *this;
 }
 int val = head();
 //
 // The fun bit.
 // See if you can figure this bit out.
 return pop().reverse().append(val);
 }

The rest:

#include <iostream>
#include <memory>
struct List
{
 struct Node
 {
 int val;
 std::unique_ptr<Node> next;
 Node(){}
 Node(int v, Node* oldTail)
 : val(v)
 , next(nullptr)
 {
 oldTail->next.reset(this);
 }
 friend std::ostream& operator<<(std::ostream& s, Node const& data)
 {
 return s << data.val << " ";
 }
 };
 Node sentinal;
 Node* tail;
 public:
 List()
 : tail(&sentinal)
 {}
 bool empty() const
 {
 return &sentinal == tail;
 }
 int& head()
 {
 // Pre-Condition not empty
 return sentinal.next->val;
 }
 List& append(int val)
 {
 tail = new Node(val, tail);
 return *this;
 }
 List& pop()
 {
 // Pre-Condition not empty
 sentinal.next.reset(sentinal.next->next.release());
 tail = sentinal.next.get() ? tail : &sentinal;
 return *this;
 }
 List& reverse();
 friend std::ostream& operator<<(std::ostream& s, List const& data)
 {
 for(Node* loop = data.sentinal.next.get(); loop != nullptr; loop=loop->next.get())
 { s << *loop;
 }
 return s << "\n";
 }
};

Answer 1

See if you can figure this bit out.

Is this meant to be a Programming Puzzle?

You don't call append until after you finish calling reverse; reverse is recursive; so all the append calls will be called after all the reverse calls: and that explains why reverse will eventually terminate i.e. why the list will eventually be empty.

From a code-review point of view:

1. I fear that a recursive implementation might exceed your finite maximum stack size if the list is long.
2. You're deleting and creating new Node objects; you might instead be able to do it in a way that reuses existing Node instances.

Also, it should be spelled "sentinel".

• Loki Astari: Fixed everything but recursion. Because thats the bit that makes it "fun".
• Loki Astari: Not a puzzle. Valid code needs checking. Just fun code. Now the next time somebody posts a singly linked list implementation I have a reference to point them to. :-)
• Jamal: @LokiAstari: "Now the next time somebody posts a singly linked list implementation" Given the popularity of these implementations on this site, I hope you can keep up. ;-)
• Jamal: @LokiAstari: Also, it appears that you've made some changes based on this answer (at least pertaining to the spelling). Please reverse those individual changes as per site policy.

Answer 2

Some minor things:

• You could just leave out public since you're only dealing with structs. You could still maintain the following indentation to really keep it separate from the Node code.

• In C++11, you can now use default constructors if you still need your own:

  Node() = default;
  

• Consider making List a templated class if you'd like it to handle other types of values.