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".

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.