Merge two sorted linked lists in C++

Question

Should I be using std::move or copy when passing LNode in the LinkedList constructor instead of passing by reference?

template <typename T>
struct LNode {
 T data;
 shared_ptr<LNode<T>> next;
 LNode(T p_data) : data(p_data) {}
 LNode() {}
};
template <typename T>
class LinkedList {
public:
 LinkedList(LNode<T>& node) {
 root = make_shared<LNode<T>>(node);
 }
 LinkedList() {}
 void createAndLinkNodes(vector<T>& elements) {
 shared_ptr<LNode<T>> ptr = root;
 for (auto&& elem : elements) {
 shared_ptr<LNode<T>> node = make_shared<LNode<T>>(elem);
 ptr->next = node;
 ptr = ptr->next;
 }
 }
 void mergeList(LinkedList<T>& list2)
 {
 auto ptr1 = root;
 auto ptr2 = list2.root;
 shared_ptr<LNode<T>> ptr3 = make_shared<LNode<T>>();
 auto tail = ptr3;
 while (ptr1!= nullptr && ptr2 != nullptr)
 {
 if(ptr1->data < ptr2->data) {
 appendNode(ptr1,tail);
 }
 else
 {
 appendNode(ptr2,tail);
 }
 }
 tail->next = ptr1 ? ptr1 : ptr2;
 root = ptr3->next;
 }
 void print() {
 shared_ptr<LNode<T>> ptr = root;
 while (ptr != nullptr)
 {
 cout << ptr->data << " ";
 ptr = ptr->next;
 }
 cout << endl;
 }
private:
 void appendNode(shared_ptr<LNode<T>> &node, shared_ptr<LNode<T>> &tail)
 {
 tail->next = node;
 tail = tail->next;
 node = node->next;
 }
private:
 shared_ptr<LNode<T>> root;
};
int main(int argc, char **argv)
{
 cout << "MERGE SORTED LINKED LISTS" << endl;
 LNode<int> r1(2);
 LNode<int> r2(3);
 LinkedList<int> list1(r1);
 LinkedList<int> list2(r2);
 vector<int> elements1 = {5,7};
 vector<int> elements2 = {11};
 list1.createAndLinkNodes(elements1);
 list2.createAndLinkNodes(elements2);
 list1.print();
 list2.print();
 list1.mergeList(list2);
 list1.print();
 return 0;
}

• Christoph: You should make it at least const LNode<T>& node so someone can actually move a node into the constructor. You probably want to read about perfect forwarding. The book Effective modern C++ has a nice section on it.
• user1044328: Thank you, I will read that. Any other feedback is also appreciated.
• Christoph: appendNode() should probably be a member function of LNode of course this changes your code somehow because its more like appendNodeAndNext(). The first call of appendNode isn't correctly intended.

Answer 1

• Missing #includes.
• Don't pollute the global namespace. Wrap your code into its own namespace.

template <typename T>
struct LNode {
 T data;
 shared_ptr<LNode<T>> next;
 LNode(T p_data) : data(p_data) {}
 LNode() {}
};

• LNode is an implementation detail of LinkedList. Nobody should be manually creating LNode's. Either move it within the LinkedList class or wrap it in a namespace that indicates its not part of the public api (e.g. detail namespace).

• Constructors should put the object in a valid state. If T is a numeric type, like int, the default constructor will default initialize data, which does nothing. You need to value-initialize data. Also, not all Ts are default-constructible, so having a default constructor doesn't always make sense.

• Do not pollute the global namespace with either using-directives (using namespace std) or using-declarations (using std::shared_ptr). This becomes problematic in header files as users of your header will have their global namespace polluted with all these symbols. Use them at narrower scopes if you need them. Also consider alias types to contextualize types with more meaningful names.

  template <typename T>
  class LinkedList {
   struct Node;
  public:
   using link_type = std::shared_ptr<Node>;
   using value_type = T;
   using size_type = std::size_t;
   class Node {
   value_type data;
   link_type next;
   public:
   Node(value_type p_data) : data(p_data) {}
   };
  private:
   link_type root;
   size_type size;
  };
  

template <typename T>
class LinkedList {

• Be more expressive with the names of your entities. We write code not just to make the compiler happy, but because other programmers (and our future selves) will need to read and maintain the code. Your LinkedList would be better named as SinglyLinkedList. The C++ Standard Library has a singly-linked list called std::forward_list. Other linked list types include doubly-linked lists (std::list), circular lists, multi-level linked lists, and skip-lists.

 LinkedList(LNode<T>& node) {
 root = make_shared<LNode<T>>(node);
 }

• Consider how the class should be used. Should users be forced to create an LNode for the LinkedList to be rooted upon? That should be the responsibility of your LinkedList. Users should be able to either construct an empty list, provide it a size and maybe an alternative initial value (fallback to default value initialization), provide it a range (iterator pair, std::initializer_list), or another LinkedList.

 LinkedList() {}

• Providing a user-defined body for your special member functions (default constructor, destructor, copy operations, and move operations) disables the class from ever being trivially constructible. If you need a user-defined body to do actual work, use them. Sometimes the default generated definitions do the wrong thing so you need to provide an actual definition. If you just have an empty definition for these special member functions, prefer =default.

 void createAndLinkNodes(vector<T>& elements) {
 shared_ptr<LNode<T>> ptr = root;
 for (auto&& elem : elements) {
 shared_ptr<LNode<T>> node = make_shared<LNode<T>>(elem);
 ptr->next = node;
 ptr = ptr->next;
 }
 }

• The elements parameter should be passed either as a reference-to-const or as a value. If you intend to move from the parameter, use a r-value reference.

  void createAndLinkNodes(std::vector<T> const& elements);
   ^ ^^^^^^ Pass by reference-to-const
  void createAndLinkNodes(std::vector<T> elements);
   ^ Pass by value
  void createAndLinkNodes(std::vector<T>&& elements);
   ^ ^^ Pass by r-value reference
  

  By requiring elements be a mutable reference, you are preventing users from passing in a temporary. Parameters passed by reference-to-non-const are typically used for in-out use-cases.

• Be consistent with your coding style. Some of your scope braces attach to the end of lines, some on new lines. There is also a random blank line at the start of the above function. In mergeList(), there is inconsistent indentation. While indentation whitespace has no value to the compiler, it does to the reader/maintainer. Indentation that breaks from the style of the overall document will draw attention to readers that something else is happening with that line, as if it is a continuation of a statement from the previous line.

• What happens if the user doesn't set the root node through the constructor?

  LinkedList<int> list1;
  std::vector<int> one_to_four{1, 2, 3, 4};
  list1.createAndLinkNodes(one_to_four);
  void createAndLinkNodes(std::vector<T>& elements) {
   std::shared_ptr<LNode<T>> ptr = root; // root is nullptr, so ptr is nullptr.
   for (auto&& elem : elements) {
   shared_ptr<LNode<T>> node = make_shared<LNode<T>>(elem); // this is fine.
   ptr->next = node; // Boom! nullptr->next?
   ptr = ptr->next;
   }
  

 void appendNode(shared_ptr<LNode<T>> &node, shared_ptr<LNode<T>> &tail)
 {
 tail->next = node;
 tail = tail->next;
 node = node->next;
 }

• appendNode isn't just appending, but also incrementing the pointers to their next values. This seems too specialized for your mergeList function.

private:
 shared_ptr<LNode<T>> root;
};

If you want to ensure lifetime by construction through the use a smart pointer, std::unique_ptr would be a more appropriate choice. A primary reason to use smart pointers is to represent ownership of some resource. The natural ownership abstraction for your LinkedList is LinkedList owns the root node and each node owns its next node. Every node only has one owner, so shared ownership is not needed.

std::shared_ptr<T> is a heavier pointer compared to std::unique_ptr<T> and raw pointers (T*). Raw pointers are as light as it gets; a pointer to the object. A std::unique_ptr<T> is a wrapper over a raw pointer and a pointer to a deleter. If the deleter is zero-length, empty base optimization (EBO) is applied to make the size of std::unique_ptr<T> be the same as a raw pointer. A std::shared_ptr<T> contains a pointer to the shared object and a pointer to a shared control block. The details of the control block is not important for this review except that it will have a non-zero length and can't be optimized away. std::shared_ptr<T> is always two pointers. There are other non-standard "shared pointer"-like implementations that make trade-offs to be a "raw pointer"-sized object.

The downside for std::unique_ptr is that you cannot naturally copy them. While you can naturally copy std::shared_ptr, those copies aren't deep copies of the underlying object. std::shared_ptr is shared ownership, so all of the std::shared_ptrs are shallow copies, or in other words, copies of the pointer that points to the underlying object. When dealing with pointer types, which includes smart pointers, you need to consider how the compiler generated special member functions operate on those types.

1. std::shared_ptr

   1. Copy Constructor/Assignment - Copies the root node. Since ownership of the underlying LNode is shared, std::shared_ptr is really a shallow copy of the pointer pointing to roots node. If a shared node in one linked list is modified by another linked list, those changes are shared between both linked lists.

       // Create list1
       LNode<int> root1(0);
       LinkedList<int> list1(root1);
       std::vector<int> one_to_four{1, 2, 3, 4};
       list1.createAndLinkNodes(one_to_four);
       // Create list2
       LNode<int> root2(5);
       LinkedList<int> list2(root2);
       std::vector<int> six_to_nine{6, 7, 8, 9};
       list1.createAndLinkNodes(six_to_nine);
       // Create list 3 from list1's elements, then print those values
       LinkedList<int> list3(list1); 
       list3.print(); // list3 = [0, 1, 2, 3, 4]
       // Merge lists 1 and 2
       list1.mergeList(list2);
       // Print list 3 values
       list3.print() // list3 = [0, 2, 3, 4, 5, 6, 7, 8, 9], oops! 
      

   2. Move Constructor/Assignment - The shared ownership of the underlying object is moved from one pointer to another. This is the correct behavior.

   3. Destructor - Recursive destruction of the std::shared_ptr ownership chain. Stops destruction when a std::shared_ptr is currently in a shared state. With a sufficiently large enough chain of pointers being recursively destructed, you can overflow the stack.

2. std::unique_ptr

   1. Copy Constructor/Assignment - Implicit definitions are not generated since std::unique_ptr has deleted copy operations.

       LinkedList<int> list1();
       LinkedList<int> list2(list1); 
       list2 = list1;
      

      Output:

      <source>:L#:C#: error: call to implicitly-deleted copy constructor of 'LinkedList<int>'
       L# | LinkedList<int> list2(list1);
       | ^ ^^^^^
      <source>:L#:C#: note: copy constructor of 'LinkedList<int>' is implicitly deleted because 
       field 'root' has a deleted copy constructor
       L# | std::unique_ptr<LNode<T>> root;
       | ^
      /include/c++/bits/unique_ptr.h: note: 'unique_ptr' has been explicitly marked deleted here
       L# | unique_ptr(const unique_ptr&) = delete;
       | ^
      <source>:L#:C#: error: object of type 'LinkedList<int>' cannot be assigned because its 
       copy assignment operator is implicitly deleted
       L# | list2 = list1;
       | ^
      <source>:L#:C#: note: copy assignment operator of 'LinkedList<int>' is implicitly deleted
       because field 'root' has a deleted copy assignment operator
       L# | std::unique_ptr<LNode<T>> root;
       | ^
      /include/c++/bits/unique_ptr.h: note: 'unique_ptr' has been explicitly marked deleted here
       L# | unique_ptr& operator=(const unique_ptr&) = delete;
       | ^
      2 errors generated.
      

   2. Move Constructor/Assignment - Ownership of the underlying object is correctly transferred via move.

   3. Destructor - Recursive destruction of the std::unique_ptr ownership chain. With a sufficiently large enough chain of pointers being recursively destructed, you can overflow the stack.

3. Raw pointer (T*)
   1. Copy Constructor/Assignment - Incorrect behavior. Shallow copies the pointer when you want it to copy the node and point to that copied node.
   2. Move Constructor/Assignment - Ownership of the underlying object is correctly transferred via move.
   3. Destructor - Incorrect behavior as it doesn't do anything.

Rule of Three/Five/Zero

The purpose of the rule of three/five/zero is to get the programmer to consider the behavior of the generated special member functions with the data members of the class. If one definition is user-provided, you may be preventing the implicit generation of another. The following chart explains what happens when a special member function is user provided.

Rules for Implicit Generation of Special Member Functions

You could memorize the chart or print it out and pin it somewhere nearby. Smarter people have come up with the rule of three/five/zero. If you need to provide the correct behavior to any of the five special member functions,

1. Copy Constructor;
2. Copy Assignment Operator;
3. Move Constructor;
4. Move Assignment Operator; or
5. Destructor;

then you should consider the behavior of the others and either

1. explicitly default to the compiler implementation (= default;),
2. explicitly delete the compiler from generating its implementation (= delete;), or
3. provide a user-defined implementation.

This is the rule of five. Pre-C++11 did not have move operations, so programmers had to consider only three special member functions (rule of three).

template <typename ElementType>
struct ForwardList {
 ForwardList(ForwardList const& other) {
 // user defined implementation.
 }
 ForwardList& operator=(ForwardList const& other) {
 // user defined implementation.
 }
 ForwardList(ForwardList&&) = default; // explicitly use generated move constructor
 ForwardList& operator=(ForwardList&&) = default; // explicitly use generated move assignment
 ~ForwardList() {
 // user defined implementation.
 }
private:
 std::unique_ptr<Node> root_;
}

If you can avoid writing them because the generated behavior is correct, then do so. This is the rule of zero.

template <typename ElementType>
struct ForwardList {
private:
 std::forward_list<ElementType> underlying_list;
}

Some coding standards will require the special member functions be explicitly declared and defaulted in the rule of zero case. If your coding standard requires it, then do that to be consistent with the rest of the codebase.

template <typename ElementType>
struct ForwardList {
 ForwardList(ForwardList const& other) = default;
 ForwardList& operator=(ForwardList const& other) = default;
 ForwardList(ForwardList&&) = default;
 ForwardList& operator=(ForwardList&&) = default;
 ~ForwardList() = default;
private:
 std::forward_list<ElementType> underlying_list;
}

• indi: "If your intend to move from the parameter, use a forwarding reference. void createAndLinkNodes(std::vector<T>&& elements); ... Pass by forwarding reference " That is not a forwarding reference. That is a rvalue reference. A forwarding reference must be a template parameter. template <typename T> void f(vector<T>&& rvalue_reference); versus template <typename Vector> void f(Vector&& forwarding_reference);

Answer 2

std::forward_list already has a merge() member function. In an interview, I would use that rather than reinventing a wheel. I'll assume that you've already said that and being told that you're tasked with implementing this from scratch for, erm, reasons.

---

The first problem with the code is that it doesn't compile. Guessing that that the undeclared identifiers are from the std namespace, I added

#include <iostream>
#include <memory>
#include <vector>
using std::cout;
using std::endl;
using std::make_shared;
using std::shared_ptr;
using std::vector;

Using using to pollute the global namespace is a bad idea - especially in a header, as that affects every translation unit that includes that header. Reduce the scope of using, or remove them entirely and use fully-qualified names throughout.

---

I don't think LNode ought to be visible outside the list class - it's an implementation detail that client code shouldn't need to know about. They should be able to append T objects - which should be easy enough given that LNode constructor is a conversion for T.

It may be a problem that LNode seems to require that T is default-constructible.

---

The constructor that takes a reference to a node doesn't link the node directly, but copies it. That's inefficient.

Also, instead of default-initialising root then assigning over it in the constructor body, prefer to do so in its initialiser list.

---

The LinkedList default constructor doesn't share the assumptions of createAndLinkNodes(). The former creates a null root, but the latter assumes that root is not null.

It's not clear why createAndLinkNodes() gives std::vector particular privilege, nor why it might modify the vector (instead of accepting it as a reference to const). I also don't see why it removes all the existing elements from the list apart from the root.

---

print() is normally friend operator<<(std::ostream&, LinkedList const&). That allows any output stream to be used.

It's rude to flush the stream (using std::endl instead of plain '\n'). Let the caller do so if it's needed.

---

Since main doesn't use argc and argv, it's better to implement the version that takes no arguments: int main().

return 0 is optional in main(), so we can omit that.

• indi: Oof, you kinda stepped on a landmine with that createAndLinkNodes() function. Ideally, we want to move the elements out of the argument if we can, and copy otherwise. So long as we’re dealing with just vector, this is easy: two overloads, the const& one copies, the && one moves. But if you want to take arbitrary ranges... all bets are off, because you can’t assume it’s safe to move elements out of an arbitrary rvalue range. I took a swing at it, but I really can’t swear that I’ve got it licked.
• Toby Speight: I like that implementation. I think you could make a useful concept, perhaps called range_of_xvalues, for ones we should move from. Or, per the code comment, rvalue_owning_range - I like that better.
• Toby Speight: Yes, that works for the same tests.
• indi: Yeah, I’m just not sure I’ve covered all the "interesting" cases with the tests.