1
\$\begingroup\$

I want to improve this code. I want to enter all values in linked list at a time like circular_linked_list<int> cll1(5, 10, 18, 25);

#include <iostream>
#include <utility>

template <class T>
class circular_linked_list
{
  struct Node
  {
    T data;
    Node * next;
    Node(T&& value) : data(std::move(value)), next(nullptr) {}
    /*
    //to enter any number of arguments
    template <typename... Args>
    Node(Args&&... args) : data(std::forward<Args>(args)...), next(nullptr)
                         {}
                         */
  };
  Node *head;

public:
  circular_linked_list() : head(nullptr) {}
  circular_linked_list(const circular_linked_list& cll) = delete; //copy constructor
  circular_linked_list(circular_linked_list&& cll) = delete; //move constructor
  circular_linked_list& operator=(const circular_linked_list& cll) = delete; //copy assignment
  circular_linked_list& operator=(circular_linked_list&& cll) = delete; //move assignment
  ~circular_linked_list();

  void insert_node(T&&);

  /*
  template <typename... Args>
  void insert_node(Args&&... args)
   { ..
     code
     ..
   } */

  Node *split_list()//Returns the mid-node
  {
    Node *slow_ptr = head;
    Node *fast_ptr = head;

    //If odd number of nodes then fast_ptr->next = head
    //If even number of nodes then fast_ptr->next->next = head
    while(fast_ptr->next != head && fast_ptr->next->next != head)
    {
      fast_ptr = fast_ptr->next->next;
      slow_ptr = slow_ptr->next;
    }
    return slow_ptr;
  }

  void print_split_lists();
  void print_list(Node*);
  void print_list()
  {
    print_list(head);
  }
};

template <class T>
void circular_linked_list<T>::insert_node(T&& value)
{
  Node *node = new Node(std::move(value));
  if(head == nullptr)
  {
    node->next = node;
    head = node;
    return;
  }
  Node *tmp = head;
  while(tmp->next != head)
  {
    tmp = tmp->next;
  }
  tmp->next = node;
  node->next = head;
}

template <class T>
void circular_linked_list<T>::print_split_lists()
{
  Node *head1 = nullptr;
  Node *head2 = nullptr;
  Node *mid_node = split_list();
  Node *tail = head;

  while(tail->next != head)
  {
    tail = tail->next;
  }

  if(head->next != head)
  {
  head2 = mid_node->next;
  }

  tail->next = head2;

  head1 = head;
  mid_node->next = head1;
  std::cout << "First half of list \n";
  print_list(head1);
  std::cout << "Second half of list \n";
  print_list(head2);
}

template <class T>
void circular_linked_list<T>::print_list(Node *head)
{
  Node *tmp = head;
  while(tmp->next != head)
  {
    std::cout << tmp->data << ' ';
    tmp = tmp->next;
  }
  std::cout << tmp->data << '\n';
}

template <class T>
circular_linked_list<T>::~circular_linked_list()
{
  Node *tmp = nullptr;
  Node *tail = head;
  while(tail->next != head)
  {
    tail = tail->next;
  }
  tail->next = nullptr;

  while(head != nullptr)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
}

int main()
{
  //circular_linked_list<int> cll1(5, 10, 18, 25);
  circular_linked_list<int> cll1;
  cll1.insert_node(2);
  cll1.insert_node(3);
  cll1.insert_node(4);
  cll1.insert_node(1);
  cll1.insert_node(0);
  cll1.print_list();
  cll1.print_split_lists();
}
\$\endgroup\$
1
\$\begingroup\$

This is an interesting problem! I don't know that I've ever needed to split a linked list before. I'd love to know whether this is for solving a real-world problem or if you're just doing it for fun. Here are some thoughts on it.

Naming

The first thing I'd do to improve this code would be to fix the naming. That's almost always a good first step for a code review, but in this case, I think it's imperative as some of your methods are deceptively named, implying they do something they do not. For example, the split_list() method does not split the list. Instead, it finds the middle node in the list. It should be called something like get_middle_node(). You even have a comment next to it saying that it does something other than its name. That's a big clue that it's named incorrectly.

Inside the method, there are 2 pointers named slow_ptr and fast_ptr. I had to read the code about 5 times before I understood that the "fast" pointer was incrementing by 2 and the "slow" pointer was incrementing by 1. The names don't even make sense, as pointers don't have a speed. They both access their data in the same amount of time! I would rename them to something like advance_by_1 and advance_by_2. And I would probably also leave a comment explaining that when advance_by_2 hits the head, advance_by_1 will be pointing to the mid node, because that's a fairly clever way of finding the middle node. I don't think it's so clever that you shouldn't do it, but I think you should clarify with a comment.

The name of print_split_lists() is accurate, but I was confused because I thought a caller would end up getting back 2 lists, or that the method would need to be passed the second list, or something. The method doesn't actually split the list - it makes some temporary variables that act like 2 lists, and then prints those. And if I'm not mistaken, it leaves the list in a bad state. That's confusing to me. What would be the use case where I would want to print a single list as 2 lists, but then not actually end up with 2 lists? This seems like a method that's not needed. I'd think you'd want to have a method to split the list in 2 (and return 2 lists), and then just call print_list on each of those 2 new lists.

You ask:

How can I write a function which returns two lists and how to use it in main() function?

There are a couple of ways to handle this. You can:

  1. Write a function that finds the middle node, constructs a new list with the second half of the old list, and sets the old list to be the first half
  2. Write a function that creates 2 new lists and fills them with the 1st and 2nd half of the original list, respectively.

Let's assume for now that version 1 is acceptable. I'd do it like this (not tested) :

void circular_linked_list::split_list_at_middle(circular_linked_list& secondHalf)
{
    Node* tail = find_tail_node();
    Node* mid = find_middle_node();

    // Move the second half of the list into a new list
    second_half.head = mid->next;
    tail->next = second_half.head;

    // Set our list to only be the first half
    mid->next = head;
}

Note that I left out the code to check for empty lists and lists with only a single node. You'll need to handle those, too.

Then in main(), you call it like this:

circular_linked_list secondHalf;
originalList.split_list_at_middle(secondHalf);
std::cout << "First half of list \n";
originalList.print_list();
std::cout << "Second half of list \n";
secondHalf.print_list();

Performance

One of the main weaknesses of linked lists is random access. If you need to find the nth node, you need to iterate over n nodes to get there. So finding the middle node will always require iterating over (list length) / 2 nodes. And finding the tail node always requires iterating over (list length) nodes. Unless you know you'll need to do those 2 things and prepare for it.

One common way to make list insertion very fast (O(1)) is to keep not only a head node, but a tail node. (Some people will just keep a tail node, and then have a method to return the head node that just returns tail->next. It's not worth the tradeoff in my opinion, but you may disagree.) Now an insertion at the end of the list just involves:

newNode->next = tail->next; // or just head
tail->next = newNode;

No searching the list for the end first.

So why can't we do the same thing with the middle node? If you keep a midNode pointer and keep track of the length of the list, you can do something similar. Every time you do an insertion, you increment the length counter. Every time you do a deletion, you decrement it. When the length counter is even during an insertion, increment the midNode pointer to point to midNode->next. If you want to keep it up-to-date during deletions, you need to have a doubly-linked list or you need to walk the list and find the previous node. It is often the case that you need to walk the list to find the node to delete, anyway, so that's not too onerous. It's a little trickier on delete because you need to know whether the node you're deleting is ahead of or after the mid node. But it turns out that your class doesn't actual handle deletions!

Handle Deletions

This class doesn't handle deleting a node. That seems like a pretty big thing that a user of this class will want to do. It's fairly rare to want to be able to insert but not remove in a list, so I recommend adding such a method.

\$\endgroup\$
  • \$\begingroup\$ How can I write a function which returns two lists and how to use it in main() function? \$\endgroup\$ – coder Feb 3 '18 at 19:22
  • \$\begingroup\$ See my above edits. \$\endgroup\$ – user1118321 Feb 3 '18 at 19:33

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.