2
\$\begingroup\$

After improving code from suggestions to my previous question. I have implemented copy constructor, copy assignment, move constructor, move assignmnet. There is a suggestion for sentinal node but I don't know how to write code for that and I have used exit(0) in the end because the program was not terminating. I want to improve this code.

#include <iostream>
#include <utility>

template <typename T>
class circular_doubly_linked_list
{
  struct Node
  {
    T data;
    Node * next;
    Node * prev;
    Node(T value) : data(std::move(value)),
                    next(nullptr),
                    prev(nullptr)
                    {}
  };
  Node *head, *tail;

public:
  circular_doubly_linked_list() : head(nullptr), tail(nullptr) {}
  circular_doubly_linked_list(const circular_doubly_linked_list &); //copy constructor
  circular_doubly_linked_list& operator=(const circular_doubly_linked_list& cdll) //copy assignment
  {
    circular_doubly_linked_list  temp(cdll);
    temp.swap(*this);
    return *this;
  }
  circular_doubly_linked_list(circular_doubly_linked_list&&) noexcept; //move constructor
  circular_doubly_linked_list& operator=(circular_doubly_linked_list&& cdll) noexcept //move assignment
  {
    cdll.swap(*this);
    return *this;
  }
  ~circular_doubly_linked_list();

  void append_node(T);
  void delete_node(T);

  friend void swap(circular_doubly_linked_list& lhs, circular_doubly_linked_list& rhs)
  {
    std::swap(lhs.head, rhs.head);
  }

  template <typename U>
  friend std::ostream & operator<<(std::ostream & os, const circular_doubly_linked_list<U> & cdll)
  {
    cdll.print_list(os);
    return os;
  }

private:

  struct Node *search(T value)
  {
    Node *node = head;
    while(node->next != head)
    {
      if(node->data == value)
      {
        return node;
      }
      node = node->next;
    }
    if(node->data == value)
    {
      return node;
    }
    return nullptr;
  }

  void print_list(std::ostream& os = std::cout) const
  {
    Node *tmp = head;
    while(tmp->next != head)
    {
      std::cout << tmp->data << ' ';
      tmp = tmp->next;
    }
    std::cout << tmp->data << '\n';
  }
};

template <typename T>
circular_doubly_linked_list<T>::circular_doubly_linked_list(const circular_doubly_linked_list & cdll)
{
  if(cdll.head == nullptr)
  {
    head = tail = nullptr;
  }
  else
  {
    head = new Node(cdll.head->data);
    Node *curr = head;
    Node *tmp = head;
    Node *obj_curr = cdll.head;
    while(obj_curr->next != cdll.head)
    {
      curr->next = new Node(obj_curr->next->data);
      obj_curr = obj_curr->next;
      curr = curr->next;
      curr->prev = tmp;
      tmp = tmp->next;
    }
    tail = curr;
    curr->next = head;
    head->prev = curr;
  }
}

template <typename T>
circular_doubly_linked_list<T>::circular_doubly_linked_list(circular_doubly_linked_list&& cdll) noexcept
{
  head = tail = nullptr;
  swap(*this, cdll);
}

template <typename T>
void circular_doubly_linked_list<T>::append_node(T value)
{
  Node *node = new Node(std::move(value));

  if(head == nullptr)
  {
    node->next = node;
    node->prev = node;
    head = node;
    tail = node;
  }

  tail = head->prev;
  tail->next = node;
  node->prev = tail;
  node->next = head;
  head->prev = node;
  tail = node;
}

template <typename T>
void circular_doubly_linked_list<T>::delete_node(T value)
{
  Node *node = search(value);
  if(node == nullptr)
  {
    std::cerr << "No such value in the list\n";
    return;
  }
  else
  {
  Node *tmp = head;
  Node *tail = head->prev;
  if(tmp == node)
  {
    tail->next = tmp->next;
    tmp->prev->next->prev = tail;
    head = tail->prev;
    delete tmp;
    return;
  }
  else if(tail == node)
  {
    Node *curr = tail;
    tmp = tail->prev;
    tmp->next = curr->next;
    head->prev = tmp;
    tail = tmp;
    delete curr;
    return;
  }
  else
  {
    while(tmp->next != head)
    {
      if(tmp == node)
      {
        tmp->prev->next = tmp->next;
        tmp->prev->next->prev = tmp->prev;
        delete tmp;
        return;
      }
      tmp = tmp->next;
    }
  }
}

}

template <typename T>
circular_doubly_linked_list<T>::~circular_doubly_linked_list()
{
  Node *tmp = nullptr;
  while(head!= nullptr)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
}

int main()
{
  circular_doubly_linked_list<int> cdll1;
  cdll1.append_node(3);
  cdll1.append_node(4);
  cdll1.append_node(5);
  cdll1.append_node(6);
  cdll1.append_node(7);
  cdll1.append_node(8);
  std::cout << cdll1;
  cdll1.delete_node(6);
  std::cout << cdll1;
  circular_doubly_linked_list<int> cdll2(cdll1); // using copy constructor
  std::cout << "Linked List 2: " << cdll2;
  circular_doubly_linked_list<int> cdll3 = cdll1; //using copy assignment
  std::cout << "Linked List 3: " << cdll3;
  circular_doubly_linked_list<int> cdll4 = std::move(cdll2); //using move constructor
  std::cout << "Linked list 4: " << cdll4;
  exit(0);
}
\$\endgroup\$
  • \$\begingroup\$ while(head!= nullptr) - How will that ever happen if the list is circular? The need for exit(0) should hint at you that you got yourself an infinite loop you need to resolve. \$\endgroup\$ – StoryTeller Jan 31 '18 at 9:04
  • \$\begingroup\$ @StoryTeller There's a confusion on the forum about the meaning of 'circular'. I asked the same question as you in OP's first post, and got the answer that 'circular' isn't always what you imagine. I guess a double linked list is in a way circular, since you can travel it indefinitely in one direction then the other. \$\endgroup\$ – papagaga Jan 31 '18 at 10:05
  • \$\begingroup\$ @papagaga - I see. Well, either way, I think it's safe to say the code is not "working" if an explicit exit(0) is required. \$\endgroup\$ – StoryTeller Jan 31 '18 at 10:20
2
\$\begingroup\$

An important improvement would be to provide iterators. Your list will feel unfinished and badly designed until then.

I see that you provide numerous functionalities as core interface (searching, printing, etc.) that should remain outside the scope of your class.

The right move is to provide the user a way to go through your container, and let him implement whatever function he needs to apply to its content. That's what iterators are for.

What you need to aim for is orthogonality, or decoupling, or whatever you prefer to call it. Accessing data is the common part of almost everything you'll want to do with your list (sorting, displaying, filtering, searching, etc.), so provide access once and for all, and not once in every particular functionality.

Then if I want to search for an element of the list, I'll write:

#include <algorithm>
    ...
    auto pos = std::find(lst.begin(), lst.end(), elem);
    ...

Or if I want to print the list:

for (auto elem : lst) std::cout << elem << " ";

You might want to take a look at this link: https://stackoverflow.com/questions/7758580/writing-your-own-stl-container/7759622#7759622 before you put your self to the task, because it is notoriously tricky.

\$\endgroup\$

Your Answer

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

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