9
\$\begingroup\$

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";
        }

};
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Fixed everything but recursion. Because thats the bit that makes it "fun". \$\endgroup\$ – Martin York Apr 3 '14 at 16:00
  • \$\begingroup\$ 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. :-) \$\endgroup\$ – Martin York Apr 3 '14 at 16:01
  • 2
    \$\begingroup\$ @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. ;-) \$\endgroup\$ – Jamal Apr 3 '14 at 19:56
  • \$\begingroup\$ @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. \$\endgroup\$ – Jamal Apr 3 '14 at 20:04
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.