1
\$\begingroup\$

I want to improve this code. How to enter all elements in linked list simultaneously? I have not written code to delete a node becauseI want to only merge list for learning purpose.

#include <iostream>
#include <utility>

template<class T>
class LinkedList
{
  struct Node
  {
    T data;
    Node * next = nullptr;
    Node()          : data(), next(nullptr) {}
    Node(T&& value) : data(std::move(value)), next(nullptr) {}
  };

  Node *head;
public:
  LinkedList() : head(nullptr) {}
  LinkedList(const LinkedList& ll) = delete; //copy constructor
  LinkedList& operator=(const LinkedList& ll) = delete; //copy assignment
  ~LinkedList()
  {
    Node *tmp = nullptr;
    while(head)
    {
      tmp = head;
      head = head->next;
      delete tmp;
    }
    head = nullptr;
  }

   void insert(T&& value)
   {
    Node *node = new Node(std::move(value));
    Node *tmp = head;
    if(tmp == nullptr)
    {
      head = node;
    }
    else
    {
      while(tmp->next != nullptr)
      {
        tmp = tmp->next;
      }
      tmp->next = node;
    }
  }

  void mergeSortedList(LinkedList<T>& ll2)
  {
    Node *node = new Node();
    node->next = nullptr;
    Node *tmp = nullptr;
    tmp = node;

    Node *head1 = head;
    Node *head2 = ll2.head;

    while(head1 != nullptr && head2 != nullptr)
    {
      if(head1->data <= head2->data)
      {
        tmp->next = head1;
        tmp = tmp->next;
        head1 = head1->next;
      }
      else
      {
        tmp->next = head2;
        tmp = tmp->next;
        head2 = head2->next;
      }
    }
    while(head1 != nullptr && head2 == nullptr)
    {
      tmp->next = head1;
      tmp = tmp->next;
      head1 = head1->next;
    }
    while(head2 != nullptr && head1 == nullptr)
    {
      tmp->next = head2;
      tmp = tmp->next;
      head2 = head2->next;
    }
    tmp = tmp->next;
    delete tmp;

    // head of the new list
    head = node->next;
  }

  void printList()
  {
    Node *node = head;
    if(node == nullptr)
    {
      std::cout << "Empty List \n";
    }
    while(node != nullptr)
    {
      std::cout << node->data << " ";
      node = node->next;
    }
    std::cout << "\n";
  }
};

int main()
{
  LinkedList<int> ll1;
  ll1.insert(5);
  ll1.insert(10);
  ll1.insert(18);
  ll1.insert(25);
  std::cout << "List 1 : ";
  ll1.printList();

  LinkedList<int> ll2;
  ll2.insert(6);
  ll2.insert(8);
  ll2.insert(11);
  ll2.insert(20);
  ll2.insert(23);
  ll2.insert(28);
  ll2.insert(40);
  std::cout << "List 2 : ";
  ll2.printList();

  ll1.mergeSortedList(ll2);
  std::cout << "Merged List : ";
  ll1.printList();
}
\$\endgroup\$

closed as off-topic by Graipher, Toby Speight, t3chb0t, Sᴀᴍ Onᴇᴌᴀ, Dannnno Feb 6 '18 at 19:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Graipher, Toby Speight, t3chb0t, Sᴀᴍ Onᴇᴌᴀ, Dannnno
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Are you purposely avoiding std::merge() for this? \$\endgroup\$ – Toby Speight Feb 5 '18 at 10:34
  • \$\begingroup\$ This code crashes for me with: HEAP[Test.exe]: Invalid address specified to RtlValidateHeap( 007E0000, 007F0188 ) \$\endgroup\$ – user673679 Feb 5 '18 at 10:36
  • 2
    \$\begingroup\$ It looks like your merge function doesn't alter the second list. After merging, the nodes from the second list are in both lists, and so they get deleted twice - once in each destructor. Also, I don't think the last few lines of your merge function are correct - shouldn't it set the head of the new list to be node->next, and then delete node? \$\endgroup\$ – user673679 Feb 5 '18 at 11:02
  • \$\begingroup\$ @Toby Speight: std::merge doesn't merge in place, std::inplace_merge does but requires two consecutive sequences. Anyway, as any STL algorithm, they require iterators to be available, which is futher ahead in the learning process. \$\endgroup\$ – papagaga Feb 5 '18 at 14:41
  • \$\begingroup\$ @papagaga: Right--to merge one linked list into another, you'd use std::list<T>::merge. \$\endgroup\$ – Jerry Coffin Feb 5 '18 at 19:14
2
\$\begingroup\$

Misc.:

  • (Opinion:) Member functions shouldn't contain the name of the class, because it's redundant. Instead use something like printToStdOut and sortedMergeFrom.

  • There's an awful lot of var = var->next; throughout the class. Although it's only one line of code, it's worth factoring this out into an advance function like so:

    #include <cassert>
    ...
    static void advance(Node*& node)
    {
        assert(node != nullptr);
        node = node->next;
    }
    

    This allows us to check every time that the node is not nullptr. It's also easier to visually parse advance(tmp) or advance(node) than tmp = tmp->next. Note that uses a reference to a pointer (i.e. alters a pointer outside the function's own scope), so be careful not to pass head into it directly.

  • Most of the code in the insert function is actually getting the last node in the list. This could be factored out into a separate function.

  • printList should be const.

  • printList could be a little neater: The node variable is only needed if head isn't null. (It also prints an extra line for empty lists). Generally, it's best to treat special cases at the start of the function, and return early:

    void printToStdOut() const
    {
        if (head == nullptr)
        {
            std::cout << "Empty List \n";
            return;
        }
    
        Node* node = head;
    
        while (node != nullptr)
        {
            std::cout << node->data << " ";
            advance(node);
        }
    
        std::cout << "\n";
    }
    

Merge:

It sounds like you want to do an in-place merge, and avoid creating any extra nodes. You're 90% of the way there.

We have two sources from which to take the next possible node. The first node of each source is compared, and added the smallest to the output list. We're really just rewiring the next pointers in both lists to point to the next smallest node from the two sources.

If we keep track of the first node chosen (the smaller of the two lists' heads), we can set head to that node afterwards, and set the other list's head to nullptr (because all the nodes now belong to the first list, and we don't want to delete them twice).

Refactoring and a bit of renaming, gives the following:

void sortedMergeFrom(LinkedList<T>& list2)
{
    Node *source1 = head;
    Node *source2 = list2.head;

    Node *merged = /* take the "smallest" from the two sources... */; // previously "node" - we actually only need a pointer, not an allocated node
    Node *current = merged; // previously "tmp" - the "tail" of the new list, onto which we add stuff

    while (source1 != nullptr && source2 != nullptr)
    {
        if (source1->data <= source2->data)
        {
            current->next = source1;
            advance(source1);
        }
        else
        {
            current->next = source2;
            advance(source2);
        }

        advance(current);
    }

    // if we have extra nodes in either list, they're already connected, so we only need one assignment:
    // (we don't bother advancing the source or current pointers here...)
    if (source1 != nullptr)
        current->next = source1;

    if (source2 != nullptr)
        current->next = source2;

    head = merged;
    list2.head = nullptr;
}

Picking the first node is kinda awkward. It becomes a lot easier if we treat the special cases (nullptr head in each list) first, and factor out the idea of "taking" a pointer from a source and advancing that source:

static Node* take(Node*& node)
{
    Node* result = node;
    advance(node);
    return result;
}

void sortedMergeFrom(LinkedList<T>& list2)
{
    if (list2.head == nullptr)
        return; // nothing to do!

    if (head == nullptr)
    {
        head = list2.head;
        list2.head = nullptr;

        return; // take everything from list2
    }

    Node *source1 = head;
    Node *source2 = list2.head;

    Node *merged = (source1->data <= source2->data) ? take(source1) : take(source2);
    Node *current = merged;

    while (source1 != nullptr && source2 != nullptr)
    {
        if (source1->data <= source2->data)
            current->next = take(source1);
        else
            current->next = take(source2);

        advance(current);
    }

    if (source1 != nullptr)
        current->next = source1;

    if (source2 != nullptr)
        current->next = source2;

    head = merged;
    list2.head = nullptr;
}

Taking the smaller of the two sources could itself be factored out, but that's left as an excercise for the reader...

\$\endgroup\$
3
\$\begingroup\$

Node constructor

It seems odd that we can only provide rvalues as argument to the constructor. I'd expect to be able to pass by copy, too.

The usual way to allow that is to accept a T by value, and move-construct data from that value:

Node(T value = T()) : data(std::move(value)) {}

Note two other changes there: I've added a default argument, so we don't need to write a default constructor, and I've omitted the initialization of next, as we wrote a suitable default initializer for it.

List constructor

If we provide an initializer for head, we don't need to write a default constructor.

We might want to accept a list of elements when creating a linked list. That would look something like this:

LinkedList() = default;
LinkedList(std::initializer_list<T> elements)
{
    for (auto& e: elements)
         insert(std::move(e));
}

Pointer ownership

We need to be absolutely clear that every object created with new has exactly one owner, that knows when the object is no longer in use and will delete it at that point. When moving nodes from one list to another, it is essential that the ownership is transferred - if both lists think they are owner of a node, it will be double-deleted, and if neither lists does, it will be leaked.

We can write code to do this manually, but it's easier and less error-prone to #include <memory> and then make use of the smart pointer types that are provided for us.

\$\endgroup\$

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