Implementing a linked list in C++

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
10
down vote

favorite
4












I am an experienced C# developer and started with C++ a few days ago. I implemented a simple linked list to play around with templates, iterators, pointers, references and stuff.



What would experienced C++ developers do differently?



Thread-safety and performance were not a priority in this implementation. I wanted it to work and to be written C++-style, not C#-style.



#include <stdint.h>
#include <iostream>

template<class T>
class LinkedList final

public:
LinkedList();

LinkedList(const LinkedList<T> &src);

LinkedList(const LinkedList<T> &&src);

LinkedList &operator=(const LinkedList &src);

LinkedList &operator=(const LinkedList &&src);

void Add(const T &value);

void Remove(std::uint32_t index);

T Get(std::uint32_t index) const;

void Print() const;

std::uint32_t GetCount() const;

private:
struct ListNode

ListNode(const T value) : value_(value), next_(nullptr)


~ListNode()


ListNode* next_;
T value_;
;

std::uint32_t count_;
ListNode* start_;
ListNode* end_;

public:
struct iterator
typedef std::forward_iterator_tag iterator_category;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;

iterator(ListNode* init = nullptr) : current_(init)

T& operator*()
return current_->value_;


const T& operator*() const
return current_->value_;


iterator& operator++() // prefix
if (current_ != nullptr)
current_ = current_->next_;
return *this;


iterator operator++(int) // postfix
iterator temp = *this;
++*this;
return temp;


bool operator==(const iterator& x) const
return current_ == x.current_;


bool operator!=(const iterator& x) const
return current_ != x.current_;


private:
ListNode * current_;
;

iterator begin()
return iterator(start_);


iterator end()
return iterator();

;

template<class T>
inline LinkedList<T>::LinkedList(): start_(nullptr), end_(nullptr), count_(0)


template<class T>
inline LinkedList<T>::LinkedList(const LinkedList<T>& src)
: start_(nullptr), end_(nullptr), count_(0)
for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

Add(node_iter->value_);



template<class T>
inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
auto delete_iter = start_;

while (delete_iter != nullptr)
start_ = start_->next_;
delete delete_iter;
delete_iter = start_;


for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

Add(node_iter->value_);


return *this;


template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)
count_ = src.count_;
start_ = src.start_;
end_ = src.end_;

return *this;


template<class T>
inline void LinkedList<T>::Add(const T &value)
if (start_ == nullptr)
start_ = new ListNode(value);
end_ = start_;

else
end_->next_ = new ListNode(value);
end_ = end_->next_;


count_++;


template<class T>
inline void LinkedList<T>::Remove(std::uint32_t index)
if (index >= count_)
throw std::out_of_range("Index was larger than list length.");


count_--;

if (index == 0)
auto old_start = start_;
start_ = start_->next_;
if (count_ == 1)
end_ = nullptr;

delete old_start;
return;


auto current = start_;
while (--index > 0)

current = current->next_;


auto next = current->next_;
current->next_ = next->next_;

if (end_ == next)
end_ = current;


delete next;


template<class T>
inline T LinkedList<T>::Get(std::uint32_t index) const
if (index >= count_)
throw std::out_of_range("Index was larger than list length.");


auto current = start_;
while (index-- > 0)
current = current->next_;


return current->value_;


template<class T>
inline void LinkedList<T>::Print() const
if (start_ == nullptr)
std::cout << "[empty]" << std::endl;
return;


auto current = start_;
while (current->next_ != nullptr)

std::cout << current->value_ << " - ";
current = current->next_;


std::cout << current->value_ << std::endl;


template<class T>
inline std::uint32_t LinkedList<T>::GetCount() const
return count_;







share|improve this question



























    up vote
    10
    down vote

    favorite
    4












    I am an experienced C# developer and started with C++ a few days ago. I implemented a simple linked list to play around with templates, iterators, pointers, references and stuff.



    What would experienced C++ developers do differently?



    Thread-safety and performance were not a priority in this implementation. I wanted it to work and to be written C++-style, not C#-style.



    #include <stdint.h>
    #include <iostream>

    template<class T>
    class LinkedList final

    public:
    LinkedList();

    LinkedList(const LinkedList<T> &src);

    LinkedList(const LinkedList<T> &&src);

    LinkedList &operator=(const LinkedList &src);

    LinkedList &operator=(const LinkedList &&src);

    void Add(const T &value);

    void Remove(std::uint32_t index);

    T Get(std::uint32_t index) const;

    void Print() const;

    std::uint32_t GetCount() const;

    private:
    struct ListNode

    ListNode(const T value) : value_(value), next_(nullptr)


    ~ListNode()


    ListNode* next_;
    T value_;
    ;

    std::uint32_t count_;
    ListNode* start_;
    ListNode* end_;

    public:
    struct iterator
    typedef std::forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    iterator(ListNode* init = nullptr) : current_(init)

    T& operator*()
    return current_->value_;


    const T& operator*() const
    return current_->value_;


    iterator& operator++() // prefix
    if (current_ != nullptr)
    current_ = current_->next_;
    return *this;


    iterator operator++(int) // postfix
    iterator temp = *this;
    ++*this;
    return temp;


    bool operator==(const iterator& x) const
    return current_ == x.current_;


    bool operator!=(const iterator& x) const
    return current_ != x.current_;


    private:
    ListNode * current_;
    ;

    iterator begin()
    return iterator(start_);


    iterator end()
    return iterator();

    ;

    template<class T>
    inline LinkedList<T>::LinkedList(): start_(nullptr), end_(nullptr), count_(0)


    template<class T>
    inline LinkedList<T>::LinkedList(const LinkedList<T>& src)
    : start_(nullptr), end_(nullptr), count_(0)
    for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

    Add(node_iter->value_);



    template<class T>
    inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


    template<class T>
    inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
    auto delete_iter = start_;

    while (delete_iter != nullptr)
    start_ = start_->next_;
    delete delete_iter;
    delete_iter = start_;


    for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

    Add(node_iter->value_);


    return *this;


    template<class T>
    inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)
    count_ = src.count_;
    start_ = src.start_;
    end_ = src.end_;

    return *this;


    template<class T>
    inline void LinkedList<T>::Add(const T &value)
    if (start_ == nullptr)
    start_ = new ListNode(value);
    end_ = start_;

    else
    end_->next_ = new ListNode(value);
    end_ = end_->next_;


    count_++;


    template<class T>
    inline void LinkedList<T>::Remove(std::uint32_t index)
    if (index >= count_)
    throw std::out_of_range("Index was larger than list length.");


    count_--;

    if (index == 0)
    auto old_start = start_;
    start_ = start_->next_;
    if (count_ == 1)
    end_ = nullptr;

    delete old_start;
    return;


    auto current = start_;
    while (--index > 0)

    current = current->next_;


    auto next = current->next_;
    current->next_ = next->next_;

    if (end_ == next)
    end_ = current;


    delete next;


    template<class T>
    inline T LinkedList<T>::Get(std::uint32_t index) const
    if (index >= count_)
    throw std::out_of_range("Index was larger than list length.");


    auto current = start_;
    while (index-- > 0)
    current = current->next_;


    return current->value_;


    template<class T>
    inline void LinkedList<T>::Print() const
    if (start_ == nullptr)
    std::cout << "[empty]" << std::endl;
    return;


    auto current = start_;
    while (current->next_ != nullptr)

    std::cout << current->value_ << " - ";
    current = current->next_;


    std::cout << current->value_ << std::endl;


    template<class T>
    inline std::uint32_t LinkedList<T>::GetCount() const
    return count_;







    share|improve this question























      up vote
      10
      down vote

      favorite
      4









      up vote
      10
      down vote

      favorite
      4






      4





      I am an experienced C# developer and started with C++ a few days ago. I implemented a simple linked list to play around with templates, iterators, pointers, references and stuff.



      What would experienced C++ developers do differently?



      Thread-safety and performance were not a priority in this implementation. I wanted it to work and to be written C++-style, not C#-style.



      #include <stdint.h>
      #include <iostream>

      template<class T>
      class LinkedList final

      public:
      LinkedList();

      LinkedList(const LinkedList<T> &src);

      LinkedList(const LinkedList<T> &&src);

      LinkedList &operator=(const LinkedList &src);

      LinkedList &operator=(const LinkedList &&src);

      void Add(const T &value);

      void Remove(std::uint32_t index);

      T Get(std::uint32_t index) const;

      void Print() const;

      std::uint32_t GetCount() const;

      private:
      struct ListNode

      ListNode(const T value) : value_(value), next_(nullptr)


      ~ListNode()


      ListNode* next_;
      T value_;
      ;

      std::uint32_t count_;
      ListNode* start_;
      ListNode* end_;

      public:
      struct iterator
      typedef std::forward_iterator_tag iterator_category;
      typedef T value_type;
      typedef T* pointer;
      typedef T& reference;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;

      iterator(ListNode* init = nullptr) : current_(init)

      T& operator*()
      return current_->value_;


      const T& operator*() const
      return current_->value_;


      iterator& operator++() // prefix
      if (current_ != nullptr)
      current_ = current_->next_;
      return *this;


      iterator operator++(int) // postfix
      iterator temp = *this;
      ++*this;
      return temp;


      bool operator==(const iterator& x) const
      return current_ == x.current_;


      bool operator!=(const iterator& x) const
      return current_ != x.current_;


      private:
      ListNode * current_;
      ;

      iterator begin()
      return iterator(start_);


      iterator end()
      return iterator();

      ;

      template<class T>
      inline LinkedList<T>::LinkedList(): start_(nullptr), end_(nullptr), count_(0)


      template<class T>
      inline LinkedList<T>::LinkedList(const LinkedList<T>& src)
      : start_(nullptr), end_(nullptr), count_(0)
      for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

      Add(node_iter->value_);



      template<class T>
      inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


      template<class T>
      inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
      auto delete_iter = start_;

      while (delete_iter != nullptr)
      start_ = start_->next_;
      delete delete_iter;
      delete_iter = start_;


      for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

      Add(node_iter->value_);


      return *this;


      template<class T>
      inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)
      count_ = src.count_;
      start_ = src.start_;
      end_ = src.end_;

      return *this;


      template<class T>
      inline void LinkedList<T>::Add(const T &value)
      if (start_ == nullptr)
      start_ = new ListNode(value);
      end_ = start_;

      else
      end_->next_ = new ListNode(value);
      end_ = end_->next_;


      count_++;


      template<class T>
      inline void LinkedList<T>::Remove(std::uint32_t index)
      if (index >= count_)
      throw std::out_of_range("Index was larger than list length.");


      count_--;

      if (index == 0)
      auto old_start = start_;
      start_ = start_->next_;
      if (count_ == 1)
      end_ = nullptr;

      delete old_start;
      return;


      auto current = start_;
      while (--index > 0)

      current = current->next_;


      auto next = current->next_;
      current->next_ = next->next_;

      if (end_ == next)
      end_ = current;


      delete next;


      template<class T>
      inline T LinkedList<T>::Get(std::uint32_t index) const
      if (index >= count_)
      throw std::out_of_range("Index was larger than list length.");


      auto current = start_;
      while (index-- > 0)
      current = current->next_;


      return current->value_;


      template<class T>
      inline void LinkedList<T>::Print() const
      if (start_ == nullptr)
      std::cout << "[empty]" << std::endl;
      return;


      auto current = start_;
      while (current->next_ != nullptr)

      std::cout << current->value_ << " - ";
      current = current->next_;


      std::cout << current->value_ << std::endl;


      template<class T>
      inline std::uint32_t LinkedList<T>::GetCount() const
      return count_;







      share|improve this question













      I am an experienced C# developer and started with C++ a few days ago. I implemented a simple linked list to play around with templates, iterators, pointers, references and stuff.



      What would experienced C++ developers do differently?



      Thread-safety and performance were not a priority in this implementation. I wanted it to work and to be written C++-style, not C#-style.



      #include <stdint.h>
      #include <iostream>

      template<class T>
      class LinkedList final

      public:
      LinkedList();

      LinkedList(const LinkedList<T> &src);

      LinkedList(const LinkedList<T> &&src);

      LinkedList &operator=(const LinkedList &src);

      LinkedList &operator=(const LinkedList &&src);

      void Add(const T &value);

      void Remove(std::uint32_t index);

      T Get(std::uint32_t index) const;

      void Print() const;

      std::uint32_t GetCount() const;

      private:
      struct ListNode

      ListNode(const T value) : value_(value), next_(nullptr)


      ~ListNode()


      ListNode* next_;
      T value_;
      ;

      std::uint32_t count_;
      ListNode* start_;
      ListNode* end_;

      public:
      struct iterator
      typedef std::forward_iterator_tag iterator_category;
      typedef T value_type;
      typedef T* pointer;
      typedef T& reference;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;

      iterator(ListNode* init = nullptr) : current_(init)

      T& operator*()
      return current_->value_;


      const T& operator*() const
      return current_->value_;


      iterator& operator++() // prefix
      if (current_ != nullptr)
      current_ = current_->next_;
      return *this;


      iterator operator++(int) // postfix
      iterator temp = *this;
      ++*this;
      return temp;


      bool operator==(const iterator& x) const
      return current_ == x.current_;


      bool operator!=(const iterator& x) const
      return current_ != x.current_;


      private:
      ListNode * current_;
      ;

      iterator begin()
      return iterator(start_);


      iterator end()
      return iterator();

      ;

      template<class T>
      inline LinkedList<T>::LinkedList(): start_(nullptr), end_(nullptr), count_(0)


      template<class T>
      inline LinkedList<T>::LinkedList(const LinkedList<T>& src)
      : start_(nullptr), end_(nullptr), count_(0)
      for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

      Add(node_iter->value_);



      template<class T>
      inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


      template<class T>
      inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
      auto delete_iter = start_;

      while (delete_iter != nullptr)
      start_ = start_->next_;
      delete delete_iter;
      delete_iter = start_;


      for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

      Add(node_iter->value_);


      return *this;


      template<class T>
      inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)
      count_ = src.count_;
      start_ = src.start_;
      end_ = src.end_;

      return *this;


      template<class T>
      inline void LinkedList<T>::Add(const T &value)
      if (start_ == nullptr)
      start_ = new ListNode(value);
      end_ = start_;

      else
      end_->next_ = new ListNode(value);
      end_ = end_->next_;


      count_++;


      template<class T>
      inline void LinkedList<T>::Remove(std::uint32_t index)
      if (index >= count_)
      throw std::out_of_range("Index was larger than list length.");


      count_--;

      if (index == 0)
      auto old_start = start_;
      start_ = start_->next_;
      if (count_ == 1)
      end_ = nullptr;

      delete old_start;
      return;


      auto current = start_;
      while (--index > 0)

      current = current->next_;


      auto next = current->next_;
      current->next_ = next->next_;

      if (end_ == next)
      end_ = current;


      delete next;


      template<class T>
      inline T LinkedList<T>::Get(std::uint32_t index) const
      if (index >= count_)
      throw std::out_of_range("Index was larger than list length.");


      auto current = start_;
      while (index-- > 0)
      current = current->next_;


      return current->value_;


      template<class T>
      inline void LinkedList<T>::Print() const
      if (start_ == nullptr)
      std::cout << "[empty]" << std::endl;
      return;


      auto current = start_;
      while (current->next_ != nullptr)

      std::cout << current->value_ << " - ";
      current = current->next_;


      std::cout << current->value_ << std::endl;


      template<class T>
      inline std::uint32_t LinkedList<T>::GetCount() const
      return count_;









      share|improve this question












      share|improve this question




      share|improve this question








      edited Jan 16 at 10:14









      BCdotWEB

      8,18211636




      8,18211636









      asked Jan 15 at 21:50









      ovichim

      512




      512




















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          8
          down vote













          Code Review



          Prefer to use C++ header. This is a C-header.



          #include <stdint.h>


          The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).



          #include <cstdint> // C++ headers that have an equivalent C header
          // add a prefix `c` and drop the `.h` suffix.


          When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.



          Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.



           // So good try on these.
          LinkedList(const LinkedList<T> &&src);
          LinkedList &operator=(const LinkedList &&src);

          // But usally they are written like this:
          LinkedList(LinkedList<T>&& src) noexcept;
          LinkedList& operator=(LinkedList&& src) noexcept;


          Also; the easiest way to write move is via swap so you would also normally see:



           void swap(LinkedList& other) noexcept;


          I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.



          This is a good standard Add (though method names usually have a lower case first letter).



           void Add(const T &value);


          You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.



           void Add(T&& value); // pass value by r-value reference allowing a move.
          template<typename... Args>
          void Add(Args&&... args); // pass parameters that allow you to build a `T` in place.


          The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.



           T Get(std::uint32_t index) const;


          // I would write like this:
          T const& get(std::uint32_t index) const; // Get a const reference to the object.
          T& get(std::uint32_t index); // Get a reference to the object.


          The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.



          Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.



           void Print() const;

          // I would write like this:
          void print(std::ostream& str = std::cout) const;


          Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.



           friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)

          list.print(str);
          return str;



          If a function does nothing. Best to not add it to the code.



           ~ListNode() 



          It just clutters stuff up.



          Ahh the fun of writing your own iterators.



           iterator begin() 
          return iterator(start_);


          iterator end()
          return iterator();



          There are two more you need to add:



           const_iterator begin() const return const_iterator(start_);
          const_iterator cbegin() const return const_iterator(start_);
          const_iterator end() const return const_iterator();
          const_iterator cend() const return const_iterator();


          First minor bug.



          Your move semantics don't actually work. Rather than move you have done a shallow copy.



          The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).



          template<class T>
          inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


          template<class T>
          inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)

          count_ = src.count_;
          start_ = src.start_;
          end_ = src.end_;

          return *this;



          This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).



          But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.



          The best way to implement this is basically



          template<class T>
          inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
          : count_(0)
          , start_(nullptr)
          , end_(nullptr)

          swap(src);


          template<class T>
          inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept

          swap(src);
          return *this;


          template<class T>
          void LinkedList<T>swap(LinkedList& other) noexcept

          using std::swap;
          swap(count, other.count);
          swap(start_, other.start_);
          swap(end_, other.end_);



          Second bug.



          You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.



          Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.



          template<class T>
          inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
          auto delete_iter = start_;

          while (delete_iter != nullptr)
          start_ = start_->next_;
          delete delete_iter;
          delete_iter = start_;


          for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

          Add(node_iter->value_);


          return *this;



          There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.



          template<class T>
          inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)

          LinkedList<T> tmp(src); // make a copy of the src.
          swap(tmp); // swap the `tmp` object and this object
          return *this;

          // At this point `tmp` has gone out of scope.
          // Thus its destructor is called. This cleans up the object and
          // destroys its internal list. Note we called swap. So the tmp
          // object contains this objects original content so we safely destroy it.


          The above is the way you first learn.

          But there is also a clever trick, that simplifies the above:



          // This does exactly the same as above with one less line.
          template<class T>
          inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)

          swap(src);
          return *this;



          There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.






          share|improve this answer






























            up vote
            3
            down vote













            Headers



            With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).



            To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need



            #include <cstddef>
            #include <stdexcept>
            #include <iterator>


            You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.



            Interface and naming



            It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace



            void Add(const T &value);

            void Remove(std::uint32_t index);

            T Get(std::uint32_t index) const;

            void Print() const;

            std::uint32_t GetCount() const;


            with



            void push_back(const T& value);
            void push_back(T&& value);
            template<typename... Args>
            reference emplace_back(Args&&... args);

            iterator erase(const_iterator pos);

            T& at(std::size_t index);
            T const& at(std::size_t index) const;

            friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

            std::size_t size() const;


            Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).



            I've hinted in the above that we should declare some useful and conventional member types:



            using value_type = T;
            using size_type = std::size_t;
            using difference_type = std::ptrdiff_t;
            using reference = value_type&;
            using const_reference = value_type const&;
            using pointer = T*;
            using const_pointer = T const*;
            struct iterator;
            struct const_iterator;


            The Rule of Zero, and ownership semantics



            When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.



            In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:



            #include <memory>




            std::unique_ptr<ListNode> head;
            ListNode *tail; // Note: this is a _non-owning_ pointer

            struct ListNode

            std::unique_ptr<ListNode> next;
            T value;
            ;


            Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.



            Initializers



            It's misleading to write



             ListNode(const T value)
            : value(value), next(nullptr)


            This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).



            We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:



            struct ListNode

            T value;
            std::unique_ptr<ListNode> next = ;

            ListNode(value)
            : value(std::move(value))


            ;


            Modified code



            I've made the changes above; there's a few other changes I ought to write up properly when time permits.



            #include <cstddef>
            #include <initializer_list>
            #include <iosfwd>
            #include <iterator>
            #include <memory>
            #include <stdexcept>

            template<class T>
            class LinkedList final

            struct ListNode

            T value;
            std::unique_ptr<ListNode> next = ;

            ListNode(T value)
            : value(std::move(value))


            ;

            std::unique_ptr<ListNode> head = ;
            ListNode *tail = ;
            std::size_t count = 0;

            public:
            using value_type = T;
            using size_type = std::size_t;
            using difference_type = std::ptrdiff_t;
            using reference = value_type&;
            using const_reference = value_type const&;
            using pointer = T*;
            using const_pointer = T const*;

            struct iterator
            typedef std::forward_iterator_tag iterator_category;
            typedef T value_type;
            typedef T* pointer;
            typedef T& reference;
            typedef std::size_t size_type;
            typedef std::ptrdiff_t difference_type;

            iterator(ListNode* init = nullptr) : current(init)

            reference operator*() const
            return current->value;


            iterator& operator++() // prefix
            if (current)
            current = current->next;
            return *this;


            iterator operator++(int) // postfix
            iterator temp = *this;
            if (current)
            current = current->next;
            return temp;


            bool operator==(const iterator& x) const
            return current == x.current;


            bool operator!=(const iterator& x) const
            return current != x.current;


            private:
            ListNode *current;
            ;

            struct const_iterator
            typedef std::forward_iterator_tag iterator_category;
            typedef T const value_type;
            typedef T const * pointer;
            typedef T const & reference;
            typedef std::size_t size_type;
            typedef std::ptrdiff_t difference_type;

            const_iterator(const ListNode* init = nullptr) : current(init)
            const_iterator(const iterator& it) : current(it.curront)

            reference operator*() const
            return current->value;


            const_iterator& operator++() // prefix
            if (current)
            current = current->next.get();
            return *this;


            const_iterator operator++(int) // postfix
            iterator temp = *this;
            if (current)
            current = current->next.get();
            return temp;


            bool operator==(const const_iterator& x) const
            return current == x.current;


            bool operator!=(const const_iterator& x) const
            return current != x.current;


            private:
            const ListNode *current;
            ;

            LinkedList() = default;

            LinkedList(std::initializer_list<T> values)
            for (auto v: values)
            push_back(v);


            LinkedList(const LinkedList<T> &src)
            for (auto value: src)
            push_back(value);

            LinkedList(LinkedList<T> &&src) = default;

            LinkedList &operator=(const LinkedList &src)
            return *this = LinkedList(src);

            LinkedList &operator=(LinkedList &&src) = default;


            void push_back(T value)
            tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
            ++count;


            template<typename... Args>
            reference emplace_back(Args&&... args)
            push_back(T args...);
            return tail->value;


            iterator erase(const_iterator pos);

            T& at(std::size_t index);
            T const& at(std::size_t index) const;

            friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)

            if (!list.head)
            return os << "[empty]" << std::endl;


            for(auto current = list.head.get(); current; current = current->next.get())
            os << current->value << " - ";

            return os << 'n';


            std::size_t size() const return count; ;

            iterator begin() return iterator(head.get());
            const_iterator begin() const return const_iterator(head.get());
            const_iterator cbegin() const return const_iterator(head.get());

            iterator end() return iterator();
            const_iterator end() const return const_iterator();
            const_iterator cend() const return const_iterator();
            ;


            // Test Program
            #include <iostream>
            int main()

            LinkedList<int> list;
            list.push_back(42);
            list.push_back(17);

            std::cout << list << std::endl;

            LinkedList<int> other -200, 0, 16 ;
            std::cout << other.emplace_back(59) << std::endl;
            list = other;

            std::cout << list << std::endl;



            The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.






            share|improve this answer





















              Your Answer




              StackExchange.ifUsing("editor", function ()
              return StackExchange.using("mathjaxEditing", function ()
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
              );
              );
              , "mathjax-editing");

              StackExchange.ifUsing("editor", function ()
              StackExchange.using("externalEditor", function ()
              StackExchange.using("snippets", function ()
              StackExchange.snippets.init();
              );
              );
              , "code-snippets");

              StackExchange.ready(function()
              var channelOptions =
              tags: "".split(" "),
              id: "196"
              ;
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function()
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled)
              StackExchange.using("snippets", function()
              createEditor();
              );

              else
              createEditor();

              );

              function createEditor()
              StackExchange.prepareEditor(
              heartbeatType: 'answer',
              convertImagesToLinks: false,
              noModals: false,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: "",
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              );



              );








               

              draft saved


              draft discarded


















              StackExchange.ready(
              function ()
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185166%2fimplementing-a-linked-list-in-c%23new-answer', 'question_page');

              );

              Post as a guest






























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes








              up vote
              8
              down vote













              Code Review



              Prefer to use C++ header. This is a C-header.



              #include <stdint.h>


              The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).



              #include <cstdint> // C++ headers that have an equivalent C header
              // add a prefix `c` and drop the `.h` suffix.


              When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.



              Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.



               // So good try on these.
              LinkedList(const LinkedList<T> &&src);
              LinkedList &operator=(const LinkedList &&src);

              // But usally they are written like this:
              LinkedList(LinkedList<T>&& src) noexcept;
              LinkedList& operator=(LinkedList&& src) noexcept;


              Also; the easiest way to write move is via swap so you would also normally see:



               void swap(LinkedList& other) noexcept;


              I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.



              This is a good standard Add (though method names usually have a lower case first letter).



               void Add(const T &value);


              You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.



               void Add(T&& value); // pass value by r-value reference allowing a move.
              template<typename... Args>
              void Add(Args&&... args); // pass parameters that allow you to build a `T` in place.


              The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.



               T Get(std::uint32_t index) const;


              // I would write like this:
              T const& get(std::uint32_t index) const; // Get a const reference to the object.
              T& get(std::uint32_t index); // Get a reference to the object.


              The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.



              Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.



               void Print() const;

              // I would write like this:
              void print(std::ostream& str = std::cout) const;


              Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.



               friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)

              list.print(str);
              return str;



              If a function does nothing. Best to not add it to the code.



               ~ListNode() 



              It just clutters stuff up.



              Ahh the fun of writing your own iterators.



               iterator begin() 
              return iterator(start_);


              iterator end()
              return iterator();



              There are two more you need to add:



               const_iterator begin() const return const_iterator(start_);
              const_iterator cbegin() const return const_iterator(start_);
              const_iterator end() const return const_iterator();
              const_iterator cend() const return const_iterator();


              First minor bug.



              Your move semantics don't actually work. Rather than move you have done a shallow copy.



              The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).



              template<class T>
              inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


              template<class T>
              inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)

              count_ = src.count_;
              start_ = src.start_;
              end_ = src.end_;

              return *this;



              This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).



              But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.



              The best way to implement this is basically



              template<class T>
              inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
              : count_(0)
              , start_(nullptr)
              , end_(nullptr)

              swap(src);


              template<class T>
              inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept

              swap(src);
              return *this;


              template<class T>
              void LinkedList<T>swap(LinkedList& other) noexcept

              using std::swap;
              swap(count, other.count);
              swap(start_, other.start_);
              swap(end_, other.end_);



              Second bug.



              You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.



              Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.



              template<class T>
              inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
              auto delete_iter = start_;

              while (delete_iter != nullptr)
              start_ = start_->next_;
              delete delete_iter;
              delete_iter = start_;


              for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

              Add(node_iter->value_);


              return *this;



              There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.



              template<class T>
              inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)

              LinkedList<T> tmp(src); // make a copy of the src.
              swap(tmp); // swap the `tmp` object and this object
              return *this;

              // At this point `tmp` has gone out of scope.
              // Thus its destructor is called. This cleans up the object and
              // destroys its internal list. Note we called swap. So the tmp
              // object contains this objects original content so we safely destroy it.


              The above is the way you first learn.

              But there is also a clever trick, that simplifies the above:



              // This does exactly the same as above with one less line.
              template<class T>
              inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)

              swap(src);
              return *this;



              There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.






              share|improve this answer



























                up vote
                8
                down vote













                Code Review



                Prefer to use C++ header. This is a C-header.



                #include <stdint.h>


                The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).



                #include <cstdint> // C++ headers that have an equivalent C header
                // add a prefix `c` and drop the `.h` suffix.


                When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.



                Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.



                 // So good try on these.
                LinkedList(const LinkedList<T> &&src);
                LinkedList &operator=(const LinkedList &&src);

                // But usally they are written like this:
                LinkedList(LinkedList<T>&& src) noexcept;
                LinkedList& operator=(LinkedList&& src) noexcept;


                Also; the easiest way to write move is via swap so you would also normally see:



                 void swap(LinkedList& other) noexcept;


                I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.



                This is a good standard Add (though method names usually have a lower case first letter).



                 void Add(const T &value);


                You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.



                 void Add(T&& value); // pass value by r-value reference allowing a move.
                template<typename... Args>
                void Add(Args&&... args); // pass parameters that allow you to build a `T` in place.


                The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.



                 T Get(std::uint32_t index) const;


                // I would write like this:
                T const& get(std::uint32_t index) const; // Get a const reference to the object.
                T& get(std::uint32_t index); // Get a reference to the object.


                The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.



                Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.



                 void Print() const;

                // I would write like this:
                void print(std::ostream& str = std::cout) const;


                Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.



                 friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)

                list.print(str);
                return str;



                If a function does nothing. Best to not add it to the code.



                 ~ListNode() 



                It just clutters stuff up.



                Ahh the fun of writing your own iterators.



                 iterator begin() 
                return iterator(start_);


                iterator end()
                return iterator();



                There are two more you need to add:



                 const_iterator begin() const return const_iterator(start_);
                const_iterator cbegin() const return const_iterator(start_);
                const_iterator end() const return const_iterator();
                const_iterator cend() const return const_iterator();


                First minor bug.



                Your move semantics don't actually work. Rather than move you have done a shallow copy.



                The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).



                template<class T>
                inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


                template<class T>
                inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)

                count_ = src.count_;
                start_ = src.start_;
                end_ = src.end_;

                return *this;



                This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).



                But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.



                The best way to implement this is basically



                template<class T>
                inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
                : count_(0)
                , start_(nullptr)
                , end_(nullptr)

                swap(src);


                template<class T>
                inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept

                swap(src);
                return *this;


                template<class T>
                void LinkedList<T>swap(LinkedList& other) noexcept

                using std::swap;
                swap(count, other.count);
                swap(start_, other.start_);
                swap(end_, other.end_);



                Second bug.



                You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.



                Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.



                template<class T>
                inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
                auto delete_iter = start_;

                while (delete_iter != nullptr)
                start_ = start_->next_;
                delete delete_iter;
                delete_iter = start_;


                for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

                Add(node_iter->value_);


                return *this;



                There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.



                template<class T>
                inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)

                LinkedList<T> tmp(src); // make a copy of the src.
                swap(tmp); // swap the `tmp` object and this object
                return *this;

                // At this point `tmp` has gone out of scope.
                // Thus its destructor is called. This cleans up the object and
                // destroys its internal list. Note we called swap. So the tmp
                // object contains this objects original content so we safely destroy it.


                The above is the way you first learn.

                But there is also a clever trick, that simplifies the above:



                // This does exactly the same as above with one less line.
                template<class T>
                inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)

                swap(src);
                return *this;



                There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.






                share|improve this answer

























                  up vote
                  8
                  down vote










                  up vote
                  8
                  down vote









                  Code Review



                  Prefer to use C++ header. This is a C-header.



                  #include <stdint.h>


                  The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).



                  #include <cstdint> // C++ headers that have an equivalent C header
                  // add a prefix `c` and drop the `.h` suffix.


                  When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.



                  Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.



                   // So good try on these.
                  LinkedList(const LinkedList<T> &&src);
                  LinkedList &operator=(const LinkedList &&src);

                  // But usally they are written like this:
                  LinkedList(LinkedList<T>&& src) noexcept;
                  LinkedList& operator=(LinkedList&& src) noexcept;


                  Also; the easiest way to write move is via swap so you would also normally see:



                   void swap(LinkedList& other) noexcept;


                  I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.



                  This is a good standard Add (though method names usually have a lower case first letter).



                   void Add(const T &value);


                  You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.



                   void Add(T&& value); // pass value by r-value reference allowing a move.
                  template<typename... Args>
                  void Add(Args&&... args); // pass parameters that allow you to build a `T` in place.


                  The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.



                   T Get(std::uint32_t index) const;


                  // I would write like this:
                  T const& get(std::uint32_t index) const; // Get a const reference to the object.
                  T& get(std::uint32_t index); // Get a reference to the object.


                  The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.



                  Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.



                   void Print() const;

                  // I would write like this:
                  void print(std::ostream& str = std::cout) const;


                  Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.



                   friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)

                  list.print(str);
                  return str;



                  If a function does nothing. Best to not add it to the code.



                   ~ListNode() 



                  It just clutters stuff up.



                  Ahh the fun of writing your own iterators.



                   iterator begin() 
                  return iterator(start_);


                  iterator end()
                  return iterator();



                  There are two more you need to add:



                   const_iterator begin() const return const_iterator(start_);
                  const_iterator cbegin() const return const_iterator(start_);
                  const_iterator end() const return const_iterator();
                  const_iterator cend() const return const_iterator();


                  First minor bug.



                  Your move semantics don't actually work. Rather than move you have done a shallow copy.



                  The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).



                  template<class T>
                  inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)

                  count_ = src.count_;
                  start_ = src.start_;
                  end_ = src.end_;

                  return *this;



                  This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).



                  But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.



                  The best way to implement this is basically



                  template<class T>
                  inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
                  : count_(0)
                  , start_(nullptr)
                  , end_(nullptr)

                  swap(src);


                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept

                  swap(src);
                  return *this;


                  template<class T>
                  void LinkedList<T>swap(LinkedList& other) noexcept

                  using std::swap;
                  swap(count, other.count);
                  swap(start_, other.start_);
                  swap(end_, other.end_);



                  Second bug.



                  You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.



                  Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.



                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
                  auto delete_iter = start_;

                  while (delete_iter != nullptr)
                  start_ = start_->next_;
                  delete delete_iter;
                  delete_iter = start_;


                  for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

                  Add(node_iter->value_);


                  return *this;



                  There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.



                  template<class T>
                  inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)

                  LinkedList<T> tmp(src); // make a copy of the src.
                  swap(tmp); // swap the `tmp` object and this object
                  return *this;

                  // At this point `tmp` has gone out of scope.
                  // Thus its destructor is called. This cleans up the object and
                  // destroys its internal list. Note we called swap. So the tmp
                  // object contains this objects original content so we safely destroy it.


                  The above is the way you first learn.

                  But there is also a clever trick, that simplifies the above:



                  // This does exactly the same as above with one less line.
                  template<class T>
                  inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)

                  swap(src);
                  return *this;



                  There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.






                  share|improve this answer















                  Code Review



                  Prefer to use C++ header. This is a C-header.



                  #include <stdint.h>


                  The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).



                  #include <cstdint> // C++ headers that have an equivalent C header
                  // add a prefix `c` and drop the `.h` suffix.


                  When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.



                  Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.



                   // So good try on these.
                  LinkedList(const LinkedList<T> &&src);
                  LinkedList &operator=(const LinkedList &&src);

                  // But usally they are written like this:
                  LinkedList(LinkedList<T>&& src) noexcept;
                  LinkedList& operator=(LinkedList&& src) noexcept;


                  Also; the easiest way to write move is via swap so you would also normally see:



                   void swap(LinkedList& other) noexcept;


                  I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.



                  This is a good standard Add (though method names usually have a lower case first letter).



                   void Add(const T &value);


                  You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.



                   void Add(T&& value); // pass value by r-value reference allowing a move.
                  template<typename... Args>
                  void Add(Args&&... args); // pass parameters that allow you to build a `T` in place.


                  The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.



                   T Get(std::uint32_t index) const;


                  // I would write like this:
                  T const& get(std::uint32_t index) const; // Get a const reference to the object.
                  T& get(std::uint32_t index); // Get a reference to the object.


                  The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.



                  Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.



                   void Print() const;

                  // I would write like this:
                  void print(std::ostream& str = std::cout) const;


                  Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.



                   friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)

                  list.print(str);
                  return str;



                  If a function does nothing. Best to not add it to the code.



                   ~ListNode() 



                  It just clutters stuff up.



                  Ahh the fun of writing your own iterators.



                   iterator begin() 
                  return iterator(start_);


                  iterator end()
                  return iterator();



                  There are two more you need to add:



                   const_iterator begin() const return const_iterator(start_);
                  const_iterator cbegin() const return const_iterator(start_);
                  const_iterator end() const return const_iterator();
                  const_iterator cend() const return const_iterator();


                  First minor bug.



                  Your move semantics don't actually work. Rather than move you have done a shallow copy.



                  The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).



                  template<class T>
                  inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_)


                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src)

                  count_ = src.count_;
                  start_ = src.start_;
                  end_ = src.end_;

                  return *this;



                  This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).



                  But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.



                  The best way to implement this is basically



                  template<class T>
                  inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
                  : count_(0)
                  , start_(nullptr)
                  , end_(nullptr)

                  swap(src);


                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept

                  swap(src);
                  return *this;


                  template<class T>
                  void LinkedList<T>swap(LinkedList& other) noexcept

                  using std::swap;
                  swap(count, other.count);
                  swap(start_, other.start_);
                  swap(end_, other.end_);



                  Second bug.



                  You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.



                  Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.



                  template<class T>
                  inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src)
                  auto delete_iter = start_;

                  while (delete_iter != nullptr)
                  start_ = start_->next_;
                  delete delete_iter;
                  delete_iter = start_;


                  for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)

                  Add(node_iter->value_);


                  return *this;



                  There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.



                  template<class T>
                  inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)

                  LinkedList<T> tmp(src); // make a copy of the src.
                  swap(tmp); // swap the `tmp` object and this object
                  return *this;

                  // At this point `tmp` has gone out of scope.
                  // Thus its destructor is called. This cleans up the object and
                  // destroys its internal list. Note we called swap. So the tmp
                  // object contains this objects original content so we safely destroy it.


                  The above is the way you first learn.

                  But there is also a clever trick, that simplifies the above:



                  // This does exactly the same as above with one less line.
                  template<class T>
                  inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)

                  swap(src);
                  return *this;



                  There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.







                  share|improve this answer















                  share|improve this answer



                  share|improve this answer








                  edited Jan 16 at 17:11


























                  answered Jan 16 at 6:34









                  Martin York

                  70.9k481244




                  70.9k481244






















                      up vote
                      3
                      down vote













                      Headers



                      With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).



                      To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need



                      #include <cstddef>
                      #include <stdexcept>
                      #include <iterator>


                      You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.



                      Interface and naming



                      It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace



                      void Add(const T &value);

                      void Remove(std::uint32_t index);

                      T Get(std::uint32_t index) const;

                      void Print() const;

                      std::uint32_t GetCount() const;


                      with



                      void push_back(const T& value);
                      void push_back(T&& value);
                      template<typename... Args>
                      reference emplace_back(Args&&... args);

                      iterator erase(const_iterator pos);

                      T& at(std::size_t index);
                      T const& at(std::size_t index) const;

                      friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

                      std::size_t size() const;


                      Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).



                      I've hinted in the above that we should declare some useful and conventional member types:



                      using value_type = T;
                      using size_type = std::size_t;
                      using difference_type = std::ptrdiff_t;
                      using reference = value_type&;
                      using const_reference = value_type const&;
                      using pointer = T*;
                      using const_pointer = T const*;
                      struct iterator;
                      struct const_iterator;


                      The Rule of Zero, and ownership semantics



                      When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.



                      In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:



                      #include <memory>




                      std::unique_ptr<ListNode> head;
                      ListNode *tail; // Note: this is a _non-owning_ pointer

                      struct ListNode

                      std::unique_ptr<ListNode> next;
                      T value;
                      ;


                      Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.



                      Initializers



                      It's misleading to write



                       ListNode(const T value)
                      : value(value), next(nullptr)


                      This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).



                      We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:



                      struct ListNode

                      T value;
                      std::unique_ptr<ListNode> next = ;

                      ListNode(value)
                      : value(std::move(value))


                      ;


                      Modified code



                      I've made the changes above; there's a few other changes I ought to write up properly when time permits.



                      #include <cstddef>
                      #include <initializer_list>
                      #include <iosfwd>
                      #include <iterator>
                      #include <memory>
                      #include <stdexcept>

                      template<class T>
                      class LinkedList final

                      struct ListNode

                      T value;
                      std::unique_ptr<ListNode> next = ;

                      ListNode(T value)
                      : value(std::move(value))


                      ;

                      std::unique_ptr<ListNode> head = ;
                      ListNode *tail = ;
                      std::size_t count = 0;

                      public:
                      using value_type = T;
                      using size_type = std::size_t;
                      using difference_type = std::ptrdiff_t;
                      using reference = value_type&;
                      using const_reference = value_type const&;
                      using pointer = T*;
                      using const_pointer = T const*;

                      struct iterator
                      typedef std::forward_iterator_tag iterator_category;
                      typedef T value_type;
                      typedef T* pointer;
                      typedef T& reference;
                      typedef std::size_t size_type;
                      typedef std::ptrdiff_t difference_type;

                      iterator(ListNode* init = nullptr) : current(init)

                      reference operator*() const
                      return current->value;


                      iterator& operator++() // prefix
                      if (current)
                      current = current->next;
                      return *this;


                      iterator operator++(int) // postfix
                      iterator temp = *this;
                      if (current)
                      current = current->next;
                      return temp;


                      bool operator==(const iterator& x) const
                      return current == x.current;


                      bool operator!=(const iterator& x) const
                      return current != x.current;


                      private:
                      ListNode *current;
                      ;

                      struct const_iterator
                      typedef std::forward_iterator_tag iterator_category;
                      typedef T const value_type;
                      typedef T const * pointer;
                      typedef T const & reference;
                      typedef std::size_t size_type;
                      typedef std::ptrdiff_t difference_type;

                      const_iterator(const ListNode* init = nullptr) : current(init)
                      const_iterator(const iterator& it) : current(it.curront)

                      reference operator*() const
                      return current->value;


                      const_iterator& operator++() // prefix
                      if (current)
                      current = current->next.get();
                      return *this;


                      const_iterator operator++(int) // postfix
                      iterator temp = *this;
                      if (current)
                      current = current->next.get();
                      return temp;


                      bool operator==(const const_iterator& x) const
                      return current == x.current;


                      bool operator!=(const const_iterator& x) const
                      return current != x.current;


                      private:
                      const ListNode *current;
                      ;

                      LinkedList() = default;

                      LinkedList(std::initializer_list<T> values)
                      for (auto v: values)
                      push_back(v);


                      LinkedList(const LinkedList<T> &src)
                      for (auto value: src)
                      push_back(value);

                      LinkedList(LinkedList<T> &&src) = default;

                      LinkedList &operator=(const LinkedList &src)
                      return *this = LinkedList(src);

                      LinkedList &operator=(LinkedList &&src) = default;


                      void push_back(T value)
                      tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
                      ++count;


                      template<typename... Args>
                      reference emplace_back(Args&&... args)
                      push_back(T args...);
                      return tail->value;


                      iterator erase(const_iterator pos);

                      T& at(std::size_t index);
                      T const& at(std::size_t index) const;

                      friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)

                      if (!list.head)
                      return os << "[empty]" << std::endl;


                      for(auto current = list.head.get(); current; current = current->next.get())
                      os << current->value << " - ";

                      return os << 'n';


                      std::size_t size() const return count; ;

                      iterator begin() return iterator(head.get());
                      const_iterator begin() const return const_iterator(head.get());
                      const_iterator cbegin() const return const_iterator(head.get());

                      iterator end() return iterator();
                      const_iterator end() const return const_iterator();
                      const_iterator cend() const return const_iterator();
                      ;


                      // Test Program
                      #include <iostream>
                      int main()

                      LinkedList<int> list;
                      list.push_back(42);
                      list.push_back(17);

                      std::cout << list << std::endl;

                      LinkedList<int> other -200, 0, 16 ;
                      std::cout << other.emplace_back(59) << std::endl;
                      list = other;

                      std::cout << list << std::endl;



                      The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.






                      share|improve this answer

























                        up vote
                        3
                        down vote













                        Headers



                        With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).



                        To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need



                        #include <cstddef>
                        #include <stdexcept>
                        #include <iterator>


                        You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.



                        Interface and naming



                        It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace



                        void Add(const T &value);

                        void Remove(std::uint32_t index);

                        T Get(std::uint32_t index) const;

                        void Print() const;

                        std::uint32_t GetCount() const;


                        with



                        void push_back(const T& value);
                        void push_back(T&& value);
                        template<typename... Args>
                        reference emplace_back(Args&&... args);

                        iterator erase(const_iterator pos);

                        T& at(std::size_t index);
                        T const& at(std::size_t index) const;

                        friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

                        std::size_t size() const;


                        Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).



                        I've hinted in the above that we should declare some useful and conventional member types:



                        using value_type = T;
                        using size_type = std::size_t;
                        using difference_type = std::ptrdiff_t;
                        using reference = value_type&;
                        using const_reference = value_type const&;
                        using pointer = T*;
                        using const_pointer = T const*;
                        struct iterator;
                        struct const_iterator;


                        The Rule of Zero, and ownership semantics



                        When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.



                        In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:



                        #include <memory>




                        std::unique_ptr<ListNode> head;
                        ListNode *tail; // Note: this is a _non-owning_ pointer

                        struct ListNode

                        std::unique_ptr<ListNode> next;
                        T value;
                        ;


                        Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.



                        Initializers



                        It's misleading to write



                         ListNode(const T value)
                        : value(value), next(nullptr)


                        This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).



                        We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:



                        struct ListNode

                        T value;
                        std::unique_ptr<ListNode> next = ;

                        ListNode(value)
                        : value(std::move(value))


                        ;


                        Modified code



                        I've made the changes above; there's a few other changes I ought to write up properly when time permits.



                        #include <cstddef>
                        #include <initializer_list>
                        #include <iosfwd>
                        #include <iterator>
                        #include <memory>
                        #include <stdexcept>

                        template<class T>
                        class LinkedList final

                        struct ListNode

                        T value;
                        std::unique_ptr<ListNode> next = ;

                        ListNode(T value)
                        : value(std::move(value))


                        ;

                        std::unique_ptr<ListNode> head = ;
                        ListNode *tail = ;
                        std::size_t count = 0;

                        public:
                        using value_type = T;
                        using size_type = std::size_t;
                        using difference_type = std::ptrdiff_t;
                        using reference = value_type&;
                        using const_reference = value_type const&;
                        using pointer = T*;
                        using const_pointer = T const*;

                        struct iterator
                        typedef std::forward_iterator_tag iterator_category;
                        typedef T value_type;
                        typedef T* pointer;
                        typedef T& reference;
                        typedef std::size_t size_type;
                        typedef std::ptrdiff_t difference_type;

                        iterator(ListNode* init = nullptr) : current(init)

                        reference operator*() const
                        return current->value;


                        iterator& operator++() // prefix
                        if (current)
                        current = current->next;
                        return *this;


                        iterator operator++(int) // postfix
                        iterator temp = *this;
                        if (current)
                        current = current->next;
                        return temp;


                        bool operator==(const iterator& x) const
                        return current == x.current;


                        bool operator!=(const iterator& x) const
                        return current != x.current;


                        private:
                        ListNode *current;
                        ;

                        struct const_iterator
                        typedef std::forward_iterator_tag iterator_category;
                        typedef T const value_type;
                        typedef T const * pointer;
                        typedef T const & reference;
                        typedef std::size_t size_type;
                        typedef std::ptrdiff_t difference_type;

                        const_iterator(const ListNode* init = nullptr) : current(init)
                        const_iterator(const iterator& it) : current(it.curront)

                        reference operator*() const
                        return current->value;


                        const_iterator& operator++() // prefix
                        if (current)
                        current = current->next.get();
                        return *this;


                        const_iterator operator++(int) // postfix
                        iterator temp = *this;
                        if (current)
                        current = current->next.get();
                        return temp;


                        bool operator==(const const_iterator& x) const
                        return current == x.current;


                        bool operator!=(const const_iterator& x) const
                        return current != x.current;


                        private:
                        const ListNode *current;
                        ;

                        LinkedList() = default;

                        LinkedList(std::initializer_list<T> values)
                        for (auto v: values)
                        push_back(v);


                        LinkedList(const LinkedList<T> &src)
                        for (auto value: src)
                        push_back(value);

                        LinkedList(LinkedList<T> &&src) = default;

                        LinkedList &operator=(const LinkedList &src)
                        return *this = LinkedList(src);

                        LinkedList &operator=(LinkedList &&src) = default;


                        void push_back(T value)
                        tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
                        ++count;


                        template<typename... Args>
                        reference emplace_back(Args&&... args)
                        push_back(T args...);
                        return tail->value;


                        iterator erase(const_iterator pos);

                        T& at(std::size_t index);
                        T const& at(std::size_t index) const;

                        friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)

                        if (!list.head)
                        return os << "[empty]" << std::endl;


                        for(auto current = list.head.get(); current; current = current->next.get())
                        os << current->value << " - ";

                        return os << 'n';


                        std::size_t size() const return count; ;

                        iterator begin() return iterator(head.get());
                        const_iterator begin() const return const_iterator(head.get());
                        const_iterator cbegin() const return const_iterator(head.get());

                        iterator end() return iterator();
                        const_iterator end() const return const_iterator();
                        const_iterator cend() const return const_iterator();
                        ;


                        // Test Program
                        #include <iostream>
                        int main()

                        LinkedList<int> list;
                        list.push_back(42);
                        list.push_back(17);

                        std::cout << list << std::endl;

                        LinkedList<int> other -200, 0, 16 ;
                        std::cout << other.emplace_back(59) << std::endl;
                        list = other;

                        std::cout << list << std::endl;



                        The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.






                        share|improve this answer























                          up vote
                          3
                          down vote










                          up vote
                          3
                          down vote









                          Headers



                          With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).



                          To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need



                          #include <cstddef>
                          #include <stdexcept>
                          #include <iterator>


                          You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.



                          Interface and naming



                          It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace



                          void Add(const T &value);

                          void Remove(std::uint32_t index);

                          T Get(std::uint32_t index) const;

                          void Print() const;

                          std::uint32_t GetCount() const;


                          with



                          void push_back(const T& value);
                          void push_back(T&& value);
                          template<typename... Args>
                          reference emplace_back(Args&&... args);

                          iterator erase(const_iterator pos);

                          T& at(std::size_t index);
                          T const& at(std::size_t index) const;

                          friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

                          std::size_t size() const;


                          Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).



                          I've hinted in the above that we should declare some useful and conventional member types:



                          using value_type = T;
                          using size_type = std::size_t;
                          using difference_type = std::ptrdiff_t;
                          using reference = value_type&;
                          using const_reference = value_type const&;
                          using pointer = T*;
                          using const_pointer = T const*;
                          struct iterator;
                          struct const_iterator;


                          The Rule of Zero, and ownership semantics



                          When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.



                          In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:



                          #include <memory>




                          std::unique_ptr<ListNode> head;
                          ListNode *tail; // Note: this is a _non-owning_ pointer

                          struct ListNode

                          std::unique_ptr<ListNode> next;
                          T value;
                          ;


                          Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.



                          Initializers



                          It's misleading to write



                           ListNode(const T value)
                          : value(value), next(nullptr)


                          This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).



                          We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:



                          struct ListNode

                          T value;
                          std::unique_ptr<ListNode> next = ;

                          ListNode(value)
                          : value(std::move(value))


                          ;


                          Modified code



                          I've made the changes above; there's a few other changes I ought to write up properly when time permits.



                          #include <cstddef>
                          #include <initializer_list>
                          #include <iosfwd>
                          #include <iterator>
                          #include <memory>
                          #include <stdexcept>

                          template<class T>
                          class LinkedList final

                          struct ListNode

                          T value;
                          std::unique_ptr<ListNode> next = ;

                          ListNode(T value)
                          : value(std::move(value))


                          ;

                          std::unique_ptr<ListNode> head = ;
                          ListNode *tail = ;
                          std::size_t count = 0;

                          public:
                          using value_type = T;
                          using size_type = std::size_t;
                          using difference_type = std::ptrdiff_t;
                          using reference = value_type&;
                          using const_reference = value_type const&;
                          using pointer = T*;
                          using const_pointer = T const*;

                          struct iterator
                          typedef std::forward_iterator_tag iterator_category;
                          typedef T value_type;
                          typedef T* pointer;
                          typedef T& reference;
                          typedef std::size_t size_type;
                          typedef std::ptrdiff_t difference_type;

                          iterator(ListNode* init = nullptr) : current(init)

                          reference operator*() const
                          return current->value;


                          iterator& operator++() // prefix
                          if (current)
                          current = current->next;
                          return *this;


                          iterator operator++(int) // postfix
                          iterator temp = *this;
                          if (current)
                          current = current->next;
                          return temp;


                          bool operator==(const iterator& x) const
                          return current == x.current;


                          bool operator!=(const iterator& x) const
                          return current != x.current;


                          private:
                          ListNode *current;
                          ;

                          struct const_iterator
                          typedef std::forward_iterator_tag iterator_category;
                          typedef T const value_type;
                          typedef T const * pointer;
                          typedef T const & reference;
                          typedef std::size_t size_type;
                          typedef std::ptrdiff_t difference_type;

                          const_iterator(const ListNode* init = nullptr) : current(init)
                          const_iterator(const iterator& it) : current(it.curront)

                          reference operator*() const
                          return current->value;


                          const_iterator& operator++() // prefix
                          if (current)
                          current = current->next.get();
                          return *this;


                          const_iterator operator++(int) // postfix
                          iterator temp = *this;
                          if (current)
                          current = current->next.get();
                          return temp;


                          bool operator==(const const_iterator& x) const
                          return current == x.current;


                          bool operator!=(const const_iterator& x) const
                          return current != x.current;


                          private:
                          const ListNode *current;
                          ;

                          LinkedList() = default;

                          LinkedList(std::initializer_list<T> values)
                          for (auto v: values)
                          push_back(v);


                          LinkedList(const LinkedList<T> &src)
                          for (auto value: src)
                          push_back(value);

                          LinkedList(LinkedList<T> &&src) = default;

                          LinkedList &operator=(const LinkedList &src)
                          return *this = LinkedList(src);

                          LinkedList &operator=(LinkedList &&src) = default;


                          void push_back(T value)
                          tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
                          ++count;


                          template<typename... Args>
                          reference emplace_back(Args&&... args)
                          push_back(T args...);
                          return tail->value;


                          iterator erase(const_iterator pos);

                          T& at(std::size_t index);
                          T const& at(std::size_t index) const;

                          friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)

                          if (!list.head)
                          return os << "[empty]" << std::endl;


                          for(auto current = list.head.get(); current; current = current->next.get())
                          os << current->value << " - ";

                          return os << 'n';


                          std::size_t size() const return count; ;

                          iterator begin() return iterator(head.get());
                          const_iterator begin() const return const_iterator(head.get());
                          const_iterator cbegin() const return const_iterator(head.get());

                          iterator end() return iterator();
                          const_iterator end() const return const_iterator();
                          const_iterator cend() const return const_iterator();
                          ;


                          // Test Program
                          #include <iostream>
                          int main()

                          LinkedList<int> list;
                          list.push_back(42);
                          list.push_back(17);

                          std::cout << list << std::endl;

                          LinkedList<int> other -200, 0, 16 ;
                          std::cout << other.emplace_back(59) << std::endl;
                          list = other;

                          std::cout << list << std::endl;



                          The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.






                          share|improve this answer













                          Headers



                          With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).



                          To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need



                          #include <cstddef>
                          #include <stdexcept>
                          #include <iterator>


                          You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.



                          Interface and naming



                          It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace



                          void Add(const T &value);

                          void Remove(std::uint32_t index);

                          T Get(std::uint32_t index) const;

                          void Print() const;

                          std::uint32_t GetCount() const;


                          with



                          void push_back(const T& value);
                          void push_back(T&& value);
                          template<typename... Args>
                          reference emplace_back(Args&&... args);

                          iterator erase(const_iterator pos);

                          T& at(std::size_t index);
                          T const& at(std::size_t index) const;

                          friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

                          std::size_t size() const;


                          Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).



                          I've hinted in the above that we should declare some useful and conventional member types:



                          using value_type = T;
                          using size_type = std::size_t;
                          using difference_type = std::ptrdiff_t;
                          using reference = value_type&;
                          using const_reference = value_type const&;
                          using pointer = T*;
                          using const_pointer = T const*;
                          struct iterator;
                          struct const_iterator;


                          The Rule of Zero, and ownership semantics



                          When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.



                          In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:



                          #include <memory>




                          std::unique_ptr<ListNode> head;
                          ListNode *tail; // Note: this is a _non-owning_ pointer

                          struct ListNode

                          std::unique_ptr<ListNode> next;
                          T value;
                          ;


                          Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.



                          Initializers



                          It's misleading to write



                           ListNode(const T value)
                          : value(value), next(nullptr)


                          This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).



                          We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:



                          struct ListNode

                          T value;
                          std::unique_ptr<ListNode> next = ;

                          ListNode(value)
                          : value(std::move(value))


                          ;


                          Modified code



                          I've made the changes above; there's a few other changes I ought to write up properly when time permits.



                          #include <cstddef>
                          #include <initializer_list>
                          #include <iosfwd>
                          #include <iterator>
                          #include <memory>
                          #include <stdexcept>

                          template<class T>
                          class LinkedList final

                          struct ListNode

                          T value;
                          std::unique_ptr<ListNode> next = ;

                          ListNode(T value)
                          : value(std::move(value))


                          ;

                          std::unique_ptr<ListNode> head = ;
                          ListNode *tail = ;
                          std::size_t count = 0;

                          public:
                          using value_type = T;
                          using size_type = std::size_t;
                          using difference_type = std::ptrdiff_t;
                          using reference = value_type&;
                          using const_reference = value_type const&;
                          using pointer = T*;
                          using const_pointer = T const*;

                          struct iterator
                          typedef std::forward_iterator_tag iterator_category;
                          typedef T value_type;
                          typedef T* pointer;
                          typedef T& reference;
                          typedef std::size_t size_type;
                          typedef std::ptrdiff_t difference_type;

                          iterator(ListNode* init = nullptr) : current(init)

                          reference operator*() const
                          return current->value;


                          iterator& operator++() // prefix
                          if (current)
                          current = current->next;
                          return *this;


                          iterator operator++(int) // postfix
                          iterator temp = *this;
                          if (current)
                          current = current->next;
                          return temp;


                          bool operator==(const iterator& x) const
                          return current == x.current;


                          bool operator!=(const iterator& x) const
                          return current != x.current;


                          private:
                          ListNode *current;
                          ;

                          struct const_iterator
                          typedef std::forward_iterator_tag iterator_category;
                          typedef T const value_type;
                          typedef T const * pointer;
                          typedef T const & reference;
                          typedef std::size_t size_type;
                          typedef std::ptrdiff_t difference_type;

                          const_iterator(const ListNode* init = nullptr) : current(init)
                          const_iterator(const iterator& it) : current(it.curront)

                          reference operator*() const
                          return current->value;


                          const_iterator& operator++() // prefix
                          if (current)
                          current = current->next.get();
                          return *this;


                          const_iterator operator++(int) // postfix
                          iterator temp = *this;
                          if (current)
                          current = current->next.get();
                          return temp;


                          bool operator==(const const_iterator& x) const
                          return current == x.current;


                          bool operator!=(const const_iterator& x) const
                          return current != x.current;


                          private:
                          const ListNode *current;
                          ;

                          LinkedList() = default;

                          LinkedList(std::initializer_list<T> values)
                          for (auto v: values)
                          push_back(v);


                          LinkedList(const LinkedList<T> &src)
                          for (auto value: src)
                          push_back(value);

                          LinkedList(LinkedList<T> &&src) = default;

                          LinkedList &operator=(const LinkedList &src)
                          return *this = LinkedList(src);

                          LinkedList &operator=(LinkedList &&src) = default;


                          void push_back(T value)
                          tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
                          ++count;


                          template<typename... Args>
                          reference emplace_back(Args&&... args)
                          push_back(T args...);
                          return tail->value;


                          iterator erase(const_iterator pos);

                          T& at(std::size_t index);
                          T const& at(std::size_t index) const;

                          friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)

                          if (!list.head)
                          return os << "[empty]" << std::endl;


                          for(auto current = list.head.get(); current; current = current->next.get())
                          os << current->value << " - ";

                          return os << 'n';


                          std::size_t size() const return count; ;

                          iterator begin() return iterator(head.get());
                          const_iterator begin() const return const_iterator(head.get());
                          const_iterator cbegin() const return const_iterator(head.get());

                          iterator end() return iterator();
                          const_iterator end() const return const_iterator();
                          const_iterator cend() const return const_iterator();
                          ;


                          // Test Program
                          #include <iostream>
                          int main()

                          LinkedList<int> list;
                          list.push_back(42);
                          list.push_back(17);

                          std::cout << list << std::endl;

                          LinkedList<int> other -200, 0, 16 ;
                          std::cout << other.emplace_back(59) << std::endl;
                          list = other;

                          std::cout << list << std::endl;



                          The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.







                          share|improve this answer













                          share|improve this answer



                          share|improve this answer











                          answered Jan 16 at 12:35









                          Toby Speight

                          17.8k13491




                          17.8k13491






















                               

                              draft saved


                              draft discarded


























                               


                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function ()
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185166%2fimplementing-a-linked-list-in-c%23new-answer', 'question_page');

                              );

                              Post as a guest













































































                              Popular posts from this blog

                              Chat program with C++ and SFML

                              Function to Return a JSON Like Objects Using VBA Collections and Arrays

                              Will my employers contract hold up in court?