6
\$\begingroup\$

After watching Herb Sutter describe single-linked lists in terms of unique_ptr I decided to implement my own. In particular I want to know if my move semantics are correct and if any unnecessary copies are made. It passes my simple cases with int and I plan to add insertion/deleting later.

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node {
public:
  Node(const Type& data) : data {data} {}
  std::unique_ptr<Node<Type>> next = nullptr;
  Type data;
};

template<typename Type>
class LinkedList {
public:
  void push_back(const Type& data) {
    if (!head) {
      head = std::make_unique<Node<Type>>(data);
      return;
    }

    Node<Type>* end = head.get();

    while (end->next) {
      end = end->next.get();
    }

    end->next = std::make_unique<Node<Type>>(data);
  }

  Type pop_back() {
    if (!head) {
      throw;
    }

    Node<Type>* end = head.get();
    Node<Type>* previous = nullptr;

    while (end->next) {
      previous = end;
      end = end->next.get();
    }

    const Type data = end->data;

    if (previous) {
      previous->next = nullptr;
    }

    return data;
  }

  void push_front(const Type& data) {
    if (!head) {
      head = std::make_unique<Node<Type>>(data);
      return;
    }

    std::unique_ptr<Node<Type>> new_head = std::make_unique<Node<Type>>(data);
    new_head->next = std::move(head);
    head = std::move(new_head);
  }

  Type pop_front() {
    if (!head) {
      throw;
    }

    const Type data = head->data;
    head = std::move(head->next);
    return data;
  }

  std::size_t size() const {
    if (!head) {
      return 0;
    }

    std::size_t size = 1;
    Node<Type>* traverse = head.get();

    while (traverse->next) {
      traverse = traverse->next.get();
      size++;
    }

    return size;
  }

  /* iterative destroy to avoid recursive deletes */
  void destroy() {
    if (!head) {
      return;
    }

    while (head->next) {
      head = std::move(head->next);
    }

    head = nullptr;
  }

private:
  std::unique_ptr<Node<Type>> head = nullptr;
};

Edit: With Deduplicator's response I ended up with this code

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node {
public:
  Node(const Type& data) : data {data} {}
  std::unique_ptr<Node<Type>> next = nullptr;
  Type data;
};

template<typename Type>
class LinkedList {
public:
  void push_back(const Type& data) {
    auto end = &head;

    while (*end) {
      end = &(*end)->next;
    }

    *end = std::make_unique<Node<Type>>(data);
  }

  Type pop_back() {
    auto end = &head;
    auto previous = &head;

    while (*end) {
      previous = end;
      end = &(*end)->next;
    }

    const Type data = (*previous)->data;
    *previous = nullptr;
    return data;
  }

  void push_front(const Type& data) {
    auto new_head = std::make_unique<Node<Type>>(data);
    new_head->next = std::move(head);
    head = std::move(new_head);
  }

  Type pop_front() {
    const Type data = head->data;
    head = std::move(head->next);
    return data;
  }

  ~LinkedList() {
    auto end = &head;

    while (*end) {
      *end = std::move((*end)->next);
    }
  }

private:
  std::unique_ptr<Node<Type>> head = nullptr;
};
\$\endgroup\$
  • \$\begingroup\$ You have a tendency to regard the empty list as a special case. Try for more uniformity! \$\endgroup\$ – Deduplicator Feb 24 '18 at 19:24
  • \$\begingroup\$ What do you mean? \$\endgroup\$ – Brady Dean Feb 25 '18 at 13:46
3
\$\begingroup\$

Almost always auto. Only write down the specific type when you have to, it's shorter, clearer, and less error-prone.

You currently handle an empty list as a special case. Don't, it's neither efficient nor elegant.
Instead, use a pointer to pointer, and everything is simplified. As an example:

void push_back(const Type& data) {
    auto p = &head;
    while (*p)
        p = &(*p)->next;
    *p = std::make_unique<Node<Type>>(data);
}

Good of you to avoid recursive descent in the dtor. But, you know that's not spelled destroy()?

\$\endgroup\$
  • \$\begingroup\$ Thanks for showing me that. I updated my functions with that pattern \$\endgroup\$ – Brady Dean Feb 26 '18 at 2:54
  • \$\begingroup\$ The alternative is to maintain a "dummy head" that never has data, but just serves to point to the first real node (when there is one). Works well with doubly-linked lists, too. \$\endgroup\$ – Toby Speight Feb 26 '18 at 17:22
  • \$\begingroup\$ auto is good, but shouldn't be over-used. I have seen it used for function arguments, that scared the hell out of me (turns out it's a proposed feature that turns the function into a template). \$\endgroup\$ – Cris Luengo Feb 27 '18 at 3:18
2
\$\begingroup\$

While this is somewhat unrelated to what you want from this review, here is something I don't like:

std::size_t size() const {
  if (!head) {
    return 0;
  }

  std::size_t size = 1;
  Node<Type>* traverse = head.get();

  while (traverse->next) {
    traverse = traverse->next.get();
    size++;
  } 

  return size;
}

This function is currently very complex, in terms of readability and performance. If the client had a loop that repeatedly needed the size of the linked list after modifying it, this would slow the code down. Instead, I suggest that you keep a private member variable called size in your class. Every time you add an element to your list, you increment this variable. Similarly, you decrement this variable when you delete something. Thus this function would then become O(1):

std::size_t size() const {
  return size;
}

This matches the behavior of the STL. However, adding such a member could bloat your class, as @Frank pointed out. If you want to really follow the STL, then I would remove the size function altogether, as std::forward_list does for these reasons.

\$\endgroup\$
  • 2
    \$\begingroup\$ I disagree. If you are regularly asking the size of a linked list, then you are doing something very wrong in the first place. So bloating the sizeof() and making the class invariant more complex just to accommodate what should be a code smell is pretty iffy on my book. \$\endgroup\$ – Frank Feb 24 '18 at 18:33
  • \$\begingroup\$ @Frank I mean, most STL containers have a size() function that returns its size in constant time (from C++11), so I'm trying to maintain that. The only exception is std::forward_list, but that removes the size function itself for the reason you said. The choice is between keeping a size function in constant time, or removing the function itself. Since OP is keeping it, I recommend changing it to perform in constant time. \$\endgroup\$ – Arnav Borborah Feb 24 '18 at 18:41
  • \$\begingroup\$ To illustrate my point, OP's move semantics are currently correct, but adding a size member would require adding a move constructor and = operator. \$\endgroup\$ – Frank Feb 24 '18 at 18:41
  • \$\begingroup\$ @ArnavBorborah fair enough, matching STL behavior is definitely a strong argument in of itself. \$\endgroup\$ – Frank Feb 24 '18 at 18:43
  • 3
    \$\begingroup\$ @Rakete1111 when moving the list, you need to reset the size of the original list to 0 since it will be empty after the move. \$\endgroup\$ – Frank Feb 25 '18 at 18:25

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.