Implementing copy constructor in a single linked list C++

Question

I have a C++ code:

#include <iostream>
using namespace std;
struct Node;

typedef Node *NodePtr;

struct Node
{
    int Item;
    NodePtr Next;
};

class LinkedList
{
public:
    LinkedList();                   // default constructor
    ~LinkedList();                  // destructor
    void AddTail(int);              // adds item to tail
private:
    NodePtr Head;
};

LinkedList::LinkedList()
{
    Head = NULL; //declare head as null
}
//Adding on tail
void LinkedList::AddTail(int Item)
{
    NodePtr Crnt;
    NodePtr node = new Node;
    node->Item = Item;
    node->Next = NULL;
//if head is in null declare the added node as head
    if (Head == NULL)
    {
        Head = node;
    }
    else
    { //set the current to head, move the current node to current next node
        Crnt = Head;
        while (Crnt->Next != NULL)
        {
            Crnt = Crnt->Next;
        }
        //Add item to the tail of the linked list
        Crnt->Next = node;
    }
}

int main()
{
    LinkedList la;
    la.AddTail(30);
    la.AddTail(60);
    la.AddTail(90);
    LinkedList lb;
    return 0;
}

So my question is how do I implement a copy constructor(suppose on object lb) that makes a deep copy of the list argument and also adding code for testing the copy constructor on empty and non-empty lists? Thanks in advance.

Solution 1

One of the big rules of programing is Don't Repeat Yourself (DRY). If you have a function that adds and you know it works, keep using it for add-related jobs. This means it's in your best interest to keep add dead stupid and versatile.

Applying the DRY philosophy, the Copy Constructor, assuming the AddTail method works correctly, is astonishingly simple: Call AddTail for every node in the source list.

LinkedList::LinkedList(const LinkedList & src):Head(nullptr)
{
    NodePtr node = src.Head;
    while (node != nullptr)
    {
        AddTail(node->Item);
        node = node->Next;
    }
}

And having a working copy constructor makes the assignment operator, thanks to the Copy and Swap Idiom, also laughably simple:

LinkedList & LinkedList::operator=(LinkedList src) 
// pass by reference performs the copy
{
    std::swap(Head, src.Head); // now just swap the head of the copy 
                               // for the head of the source
    return *this;
} // destructor fires for src and cleans up all the nodes that were on this list 

To finish off The Rule of Three trifecta we need a destructor. This, like the copy constructor is an application of DRY: Call your node removal function over and over until the list is empty. A removal function is an almost certain requirement of any linked list, so here I'm going to assume that there is one called Remove.

LinkedList::~LinkedList()
{
    while (Head != nullptr)
    {
        NodePtr temp = Head;
        Remove(Head);
        delete temp;
    }
}

So now based on two functions that a Linked List cannot function without anyway we have implemented all of the other functions required for basic maintenance. All you need are tested and bug-free Add and Remove functions and the rest comes practically free of charge.

And because the AddTail function hits one of my pet peaves... Here is a trick to greatly reduce the complexity of the function:

void LinkedList::AddTail(int Item)
{
    NodePtr *Crnt = &Head; // instead of pointing where Head points, point at 
                           // Head now we don't care if it is head or any 
                           // other node's Next. They are all abstracted to 
                           // the same thing: A pointer to where the next 
                           // node can be found        
    while (*Crnt != NULL) // keep looking until end of list
    {
        Crnt = &(*Crnt)->Next; // by pointing at the next Next pointer
    }
    //Add item to the tail of the linked list
    NodePtr node = new Node;
    node->Item = Item;
    node->Next = NULL;
    *Crnt = node; // Now just plop the new node over top of the terminating NULL
}

The Remove function, which I'm leaving unimplemented, uses the same pointer -to-pointer trick.

Solution 2

try this (https://ideone.com/9lywXc using your original posted code)

LinkedList::LinkedList(const LinkedList& other):Head(nullptr)
{
    cout << "copy constructor called:\n";
    if(other.Head == nullptr) return;
    NodePtr dummyHead = new Node;
    NodePtr curr = dummyHead;
    NodePtr othcurr = other.Head;
    for(; othcurr!=nullptr; othcurr = othcurr->Next)
    {
        curr->Next = new Node;
        curr = curr->Next;
        cout << (curr->Item = othcurr->Item) << ",";
        curr->Next = nullptr;
    }
    Head = dummyHead->Next;
    delete dummyHead;
}


int main()
{
    LinkedList la;
    la.AddTail(30);
    la.AddTail(60);
    la.AddTail(90);
    LinkedList lb(la);
    return 0;
}

output:

copy constructor called:

30,60,90,

Solution 3

this is an improvement on user4581301 prior answer so that copy constructor is O(n) on input list size. keep track of the tail with a single extra pointer in your encapsulating list class:

class LinkedList
{
public:
    LinkedList():Head(nullptr),Tail(nullptr){}
    LinkedList(const LinkedList& other);
    ~LinkedList() = default;                  // destructor
    void AddTail(int);              // adds item to tail
private:
    NodePtr Head;

    //KEEP TRACK OF TAIL POINTER WITH EXTRA MEMBER
    NodePtr Tail;
};

//via user4581301 response
LinkedList::LinkedList(const LinkedList & src):Head(nullptr),Tail(nullptr)
{
    NodePtr node = src.Head;
    while (node != nullptr)
    {
        AddTail(node->Item);
        node = node->Next;
    }
}

//Adding on tail
void LinkedList::AddTail(int Item)
{
    NodePtr np = new Node{Item,nullptr};
    if(Tail == nullptr && Head == nullptr)
        Head = Tail = np;
    else
    {
        Tail->Next = np;
        Tail = Tail->Next;
    }
}

Solution 4

regarding testing: you can add functionality to spit out the contents of the list. or you can subclass it into a test extension. or you can break encapsulation like this, using operator<<() :

class LinkedList
{
public:
    LinkedList():Head(nullptr),Tail(nullptr){}
    LinkedList(const LinkedList& other);
    ~LinkedList() = default;                  // destructor
    void AddTail(int);              // adds item to tail

    //breaks encapsulation but make some nice sugar to look inside
    friend ostream& operator<<(ostream& s, LinkedList& l)
    {
        s << "list contents: ";
        NodePtr c = l.Head;
        for(; c!=nullptr;c=c->Next)
            s << c->Item << " ";
        s << endl;
        return s;
    }
private:
    NodePtr Head;
    NodePtr Tail;
};

so that

int main()
{
    LinkedList la;
    la.AddTail(30);
    la.AddTail(60);
    la.AddTail(90);
    LinkedList lb(la);
    cout << lb;
    return 0;
}

spits out: list contents: 30 60 90

View more solutions