How do I implement a deep copy constructor into a linked list?

Question

For this problem that I'm currently working on, I'm trying to create a method within this linked list that performs a deep copy from one item to another. Right now the inside of the method is empty because I cannot get anything to work for the life of me. Is there any way I could get some help implementing this deep copy constructor in the area of code below that is commented? Thanks.

#include <string>
#include <iostream>
#include <cstddef>

using std::string;

class Item { 

public:

  string s; 

  Item(const char *a_s = "") { 
    s = a_s;
  }

  Item(string a_s) {
    s = a_s;
  }
};


class List {

  private:

      class ListNode { 

        public: 
          Item item; 
          ListNode * next; 
          ListNode(Item i) { 
            item = i;
            next = nullptr;
          }
      }; 

      ListNode * head; 
      ListNode * tail;

  public:

      class iterator {

        ListNode *node;

      public:
        iterator(ListNode *n = nullptr) {
          node = n;
        }

        Item& getItem() { return node->item; } //Not sure how this works
        void next() { node = node->next; }
        bool end() { return node==nullptr; }

      };



  public:

      List() {
        head = nullptr;
        tail = nullptr; //Sets the head and tail
      }

      List(const List & copy) { //Trying to create a copy constructor right here.

      }

      bool empty() { //Tells you if the list is empty
        return head==nullptr;
      }

      void append(Item a) { 

        ListNode *node = new ListNode(a);
          if ( head == nullptr ) {
            head = node;
            tail = node;
          } else {
            tail->next = node;
            tail = node;
          }
      }

      bool remove (Item &copy);

      void traverse() {
        ListNode *tmp = head;
        while(tmp != nullptr) {
          tmp = tmp->next;
        }
      }

      iterator begin() const {
        return iterator(head);
      }

};

    bool List::remove(Item &copy)
    {
      if (!empty()) {
        copy = head->item;
        ListNode *tmp = head->next;
        delete head;
        head = tmp;
        if (head==nullptr)
          tail = nullptr;
        return true;
      }
      return false;
    }


int main() {
   List l;
   l.append("eggs");

   List l2 = l; 

   std::cout << "done.\n";

   return 0;
}

Initialize your `head` and `tail` pointers to `nullptr`, start at the head of the passed-in list `copy`, and call `this->append()` in a loop for each item in `copy` until you get to the end of `copy`. That is the simplest way to do it. You wrote the code to `append()` already, so just reuse it. — PaulMcKenzie, Sep 19 '19 at 00:44
@PaulMcKenzie 's suggestion is made all the better by having the `tail` pointer. Normally I avoid this approach because every time you insert you have to go hunting for the end before you can insert. The `tail` pointer makes that hunting smurfing easy. Don't forget to complete the [Rule of Three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) by adding a destructor to do the clean up and an assignment operator to handle `List l2; l2 = l;` You may find the [Copy and Swap Idiom](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom) very helpful. — user4581301, Sep 19 '19 at 00:59
@user4581301 -- Yes, I was hesitant to post the solution until I saw there was a tail pointer. Once I saw that the end of the list is an O(1) operation, then just go for it and loop on `append()`. — PaulMcKenzie, Sep 19 '19 at 01:00
So I want to append the items from the first objects to the second object using the append() function in a for loop? — Laurel Link, Sep 19 '19 at 01:02
@JohnHarrison -- Yes. You have all of the code written already, you just haven't figured out how to use it yet. — PaulMcKenzie, Sep 19 '19 at 01:03
Another useful tip: Take advantage of the [Member Initializer List](https://en.cppreference.com/w/cpp/language/initializer_list). All members of a class must be initialized before entering the body of the constructor. That's not all that important for `head = nullptr;`, but when you have a member that has a lengthy construction, following it with an assignment adds insult to injury. Plus if the member's constructor requires arguments, the only place you can provide them is in the member initializer list. Aaaand Paul just showed that off in his answer. — user4581301, Sep 19 '19 at 01:06

PaulMcKenzie · Answer 1 · 2019-09-19T01:21:38.693

Assuming that append() is working correctly, you can just call it repeatedly in a loop for each item in copy.

This approach, given how you implemented your linked list with a tail pointer, makes it an ideal solution. You wrote the append function, so it's just a matter of using it in a strategic way.

Be warned however, that if you had implemented your linked list without a tail pointer (where you had to traverse to the end of the list to append), this approach would still work, but would be highly inefficient and not satisfactory.

Here is an example (untested):

List(const List & copy) : head(nullptr), tail(nullptr) 
{ 
     ListNode *copyNode = copy.head;
     while (copyNode)
     {
         append(copyNode->item);
         copyNode = copyNode->next;
     }
 }

Note that this was not tested for boundary conditions, so you may need to check for copy being empty before having to go through the loop.

Here is an example that works for a simple case

Personal preference: Rather than the extra `append` at the end for `tail`, I'd `while (copyNode != nullptr)`. Both will compile to the same thing. — user4581301, Sep 19 '19 at 01:10
Even simpler that what I had in mind. I get crapped on by the coding standard for not explicitly stating what's being compared so I have to have the `!= nullptr` and now it's ingrained. Thankful I should be that Yoda Conditionals I need not. — user4581301, Sep 19 '19 at 01:18

How do I implement a deep copy constructor into a linked list?

1 Answers1