Copy Constructor of Linked List in C++

Muhammad Husnain Feb 03, 2023 Jul 04, 2022

C++ C++ Constructor

Copy Constructor in C++
Linked List in C++
Linked List Implementation in C++

This brief article is about the C++-based implementation of the linked-list having a deep copy constructor.

Copy Constructor in C++

A copy constructor is called for initializing an object using another object of the same class. The copy constructor is called in multiple situations like:

When an object is copied using another object.
When the object is returned as a value from the function.
When an object is passed as a value to a function.

In every class, there is always a default copy constructor, but it does not perform deep copy but performs a shallow copy. Only the address of the pointer is copied with a shallow copy, and both the objects (i.e., caller and passed objects) point to the same memory.

Conversely, in deep copy, the data members’ values are copied to the destination object data members.

Linked List in C++

The linked list data structure stores data in the form of data nodes that can grow dynamically. It does not require contiguous memory, so it can efficiently be stored anywhere in the memory.

Linked List Implementation in C++

Let’s start implementing the linked list. First, we need to create a class for getting data nodes:

template <class T >
class Node
{
public:
    T info;
    Node<T>* next;

    Node ( ){
        next = 0;
    }
    Node ( T val ){
        info = val;
        next = 0;
    }
};

The Node class has two members – one for storing data (i.e., info), and the other is the pointer to the class itself for storing the address of the next node. The class is made templated so that list of any data type can be created.

The above implementation provides two constructors. The first is the default constructor, and the other is parameterized.

Let’s have a look at the template class for the linked list:

template <class T>
class LSLL
{
private:
    Node<T> * head;
public:
    LSLL ( ){
        head = 0;
    }
};

The class LSLL has only one pointer to the Node class, which will be used to hold the address of the first node of the linked list.

To provide the user with the functionality to deeply copy one linked-list object to another, we need to provide a user-defined copy constructor implementation as given below:

LSLL(LSLL& PassedObj)
{
    if (PassedObj.head == NULL) {
        head = NULL;
    }
    else {
        //copy all nodes of PassedObj to the caller object
        //attach first node to the head of the caller object
        Node<T>* newNode = new Node<T>();
        newNode->info = PassedObj.head->info;
        newNode->next = NULL;
        head = newNode;

        //Now deep-copy all the remaining nodes of the Passed linked list object
        Node<T>* PassedItr = PassedObj.head->next;
        Node<T>* CallerItr = head;
        while (PassedItr != NULL)
        {
            CallerItr->next = new Node<T>();
            CallerItr->next->info = PassedItr->info;
            CallerItr->next->next = NULL;
            CallerItr = CallerItr->next; //move to newly added node
            PassedItr = PassedItr->next; //move one node further
        }
    }
}

The above code segment creates a deep copy of the first node of the passed object and attaches it to the head of the caller list object. After that, all the remaining nodes of the passed object are deeply copied and attached to the caller-linked-list node.

Let’s have a cognitive view of the whole implementation:

#include <iostream>
using namespace std;

template <class T >
class Node
{
public:
    T info;
    Node<T>* next;

    Node()
    {
        next = NULL;
    }
    Node(T val)
    {
        info = val;
        next = NULL;
    }
};

template <class T>
class LSLL
{
private:
    Node<T>* head;
public:
    LSLL()
    {
        head = NULL;
    }
    LSLL(LSLL& PassedObj)
    {

        if (PassedObj.head == NULL) {
            head = NULL;
        }
        else {
            //copy all nodes of PassedObj to the caller object
            //attach first node to the head of the caller object
            Node<T>* newNode = new Node<T>();
            newNode->info = PassedObj.head->info;
            newNode->next = NULL;
            head = newNode;

            //Now deep-copy all the remaining nodes of the Passed linked list object
            Node<T>* PassedItr = PassedObj.head->next;
            Node<T>* CallerItr = head;
            while (PassedItr != NULL)
            {
                CallerItr->next = new Node<T>();
                CallerItr->next->info = PassedItr->info;
                CallerItr->next->next = NULL;
                CallerItr = CallerItr->next; //move to newly added node
                PassedItr = PassedItr->next; //move one node further
            }
        }
    }
    void insertAtHead(T val)
    {
        Node<T>* x = new Node<T>(val);
        x->next = head;
        head = x;
    }
    void displayAll()
    {
        Node<T>* x = head;
        {
            while (x != 0)
            {
                cout << x->info << endl;
                x = x->next;
            }
        }
    }
    int isEmpty()
    {
        if (head == 0)
            return 1;
        return 0;
    }
    void insetAtTail(T val)
    {
        Node<T>* x = head;
        if (isEmpty())
        {
            insertAtHead(val);
            return;
        }

        while (x->next != 0)
        {
            x = x->next;
        }
        x->next = new Node<T>(val);
    }
    void insertAfter(T key, T val)
    {
        if (isEmpty())
            return;

        Node<T>* x = head;
        while (x != 0 && x->info == key)
            x = x->next;

        if (!x)
            return;

        Node<T>* temp = new Node<T>(val);

        temp->next = x->next;
        x->next = x;
    }
};
int main()
{
    LSLL<int> list;
    list.insertAtHead(200);
    list.insertAtHead(100);
    list.insetAtTail(300);
    list.displayAll();

    LSLL<int> list2(list);
    cout << "List2: " << endl;
    list2.displayAll();
    return 0;
}

The main driver code first creates a list object, inserts three nodes into it, and calls the displayAll function. After that, it creates a new linked-list object, list2 and calls for its parameterized copy-constructor with the list as an argument.

Note that the list2 object is the caller object while the list is the passed object.

Output:

Author: Muhammad Husnain

Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.

Copy Constructor in C++

Linked List in C++

Linked List Implementation in C++

Related Article - C++ Constructor