How to Copy Constructor of Linked List in C++

1. Linked List
2. Linked List Data Structure
3. Copy Constructor in C++
4. Methods for Implementing a Copy Constructor in a Linked List in C++
5. Conclusion

The article provides insights into linked lists, exploring the linked list data structure, the significance of copy constructors, and methods for their implementation in C++, fostering a comprehensive understanding of efficient data management in programming.

Linked List

In C++, a linked list is a data structure used to organize elements sequentially. It consists of nodes, where each node contains data and a reference (pointer) to the next node in the sequence.

The last node’s pointer is typically set to null, indicating the end of the list. Linked lists provide dynamic memory allocation and efficient insertions/deletions, but accessing elements may require linear traversal.

Linked List Data Structure

A linked list data structure’s main advantage is its ability to store data in non-contiguous memory locations. It’s a linear data structure consisting of nodes, where each node stores the data item (key and related satellite data) and a reference to the next node.

A head pointer points to the first node in this data structure; therefore, it is sometimes called a head node. Some classic implementations of the singly-linked lists also have a tail pointer pointing to the last node of the list.

For example, the following figure shows an example depiction of a linked-list concept without a tail pointer.

The linked list has three types:

1. Singly Linked List or Simple Linked List

   It is a simple linked list, also called a singly linked list, in which we can only move forward. Each node stores the data item and the reference of the next node.

2. Doubly Linked List

   It is a linked list in which we can move forward and backward. Each node of the doubly linked list consists of the data item, the next node’s reference, and the previous node’s reference.

   It suites batter in do/redo states scenarios, including web browsers’ next page and previous navigations.

3. Circular Linked List

   It is nearly the same as a singly linked list, except that the next pointer in the last node of the list always points to the first node. This creates a circle; therefore, it is called a circular linked list.

   It is usually handy in circular queue management systems.

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 a 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.

Methods for Implementing a Copy Constructor in a Linked List in C++

Shallow Copy in C++ Linked List Copy Constructor

Utilizing a shallow copy in a linked list copy constructor involves duplicating pointers without replicating the underlying data. While this method is memory-efficient, it poses a risk.

Modifications to one list can inadvertently impact others, leading to unintended consequences. Shallow copy’s importance lies in scenarios where memory conservation is critical, but careful consideration is essential to prevent unintended data modifications across linked lists, ensuring program stability and reliability.

Let’s explore a complete working example of a linked list and its copy constructor using the shallow copy method:

#include <iostream>

// Node class to represent elements in the linked list
class Node {
 public:
  int data;
  Node* next;

  explicit Node(int value) : data(value), next(nullptr) {}
};

// Linked list class with a copy constructor using shallow copy method
class LinkedList {
 private:
  Node* head;

 public:
  // Constructor to initialize an empty linked list
  LinkedList() : head(nullptr) {}

  // Constructor to initialize linked list with values
  LinkedList(std::initializer_list<int> values) : head(nullptr) {
    for (int value : values) {
      push_back(value);
    }
  }

  // Copy Constructor using shallow copy method
  LinkedList(const LinkedList& other) : head(other.head) {}

  // Function to display the linked list
  void display() const {
    Node* current = head;
    while (current != nullptr) {
      std::cout << current->data << " ";
      current = current->next;
    }
    std::cout << std::endl;
  }

  // Function to add a new node to the end of the list
  void push_back(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
      head = newNode;
    } else {
      Node* last = head;
      while (last->next != nullptr) {
        last = last->next;
      }
      last->next = newNode;
    }
  }
};

int main() {
  // Creating an original linked list
  LinkedList originalList;
  originalList.display();  // Output: (empty)

  // Adding elements to the original list
  originalList = {1, 2, 3, 4};  // Corrected assignment
  std::cout << "Original List: ";
  originalList.display();  // Output: 1 2 3 4

  // Creating a new linked list using the copy constructor with shallow copy
  LinkedList shallowCopiedList(originalList);
  std::cout << "Shallow Copied List: ";
  shallowCopiedList.display();  // Output: 1 2 3 4

  // Modifying the original list
  originalList.push_back(5);
  std::cout << "Modified Original List: ";
  originalList.display();  // Output: 1 2 3 4 5

  // Displaying the shallow copied list after modification
  std::cout << "Shallow Copied List after Modification: ";
  shallowCopiedList.display();  // Output: 1 2 3 4 5

  return 0;
}

The Node class is the foundation, defining elements in the linked list, each holding an integer data and a next pointer. The LinkedList class, featuring a private head member, introduces two constructors for initializing an empty list or populating it with given values.

The focus shifts to the copy constructor, emphasizing the shallow copy method. Here, the constructor directly duplicates the head pointer, leading to shared nodes between the original and new lists.

Modifications in one list consequently affect the other.

A display function facilitates visualizing the list contents, while the push_back function adds a node to the list’s end, illustrating the shared nature of nodes in the shallow copy. The main function orchestrates the demonstration, showcasing the creation, modification, and impact of shallow copy on the linked lists.

Output:

The provided code exemplifies the concept of a copy constructor in a linked list using the shallow copy method. The output showcases the shared nature of nodes between the original and copied lists.

Understanding the implications of shallow copy is crucial for developers, as it allows them to make informed decisions based on the desired behavior of their programs. While shallow copy can be efficient, it is essential to be mindful of potential side effects when modifications are made to either list.

Deep Copy in C++ Linked List Copy Constructor

In a linked list copy constructor, employing a deep copy is crucial for creating an independent replica of the original list. Unlike a shallow copy, which merely duplicates the pointers, a deep copy replicates the entire structure, ensuring distinct memory allocations.

This prevents unintended side effects and ensures that modifications in one list do not affect the other. Deep copy guarantees data integrity and independence between linked lists, a vital consideration for maintaining consistency and preventing unintended data corruption or loss.

Code Example:

#include <iostream>

// Node class to represent elements in the linked list
class Node {
 public:
  int data;
  Node* next;

  explicit Node(int value) : data(value), next(nullptr) {}
};

// Linked list class with a copy constructor
class LinkedList {
 private:
  Node* head;

 public:
  // Constructor to initialize an empty linked list
  LinkedList() : head(nullptr) {}

  // Constructor to initialize linked list with values
  LinkedList(std::initializer_list<int> values) : head(nullptr) {
    for (int value : values) {
      push_back(value);
    }
  }

  // Copy Constructor using deep copy method
  LinkedList(const LinkedList& other) : head(nullptr) {
    // Helper function for deep copy
    copyNodes(other.head);
  }

  // Helper function to perform deep copy of nodes
  void copyNodes(Node* current) {
    Node* last = nullptr;
    while (current != nullptr) {
      // Create a new node with the same data
      Node* newNode = new Node(current->data);

      // If this is the first node, set it as the head
      if (last == nullptr) {
        head = newNode;
      } else {
        // Otherwise, link it to the previous node
        last->next = newNode;
      }

      // Update the last pointer and move to the next node
      last = newNode;
      current = current->next;
    }
  }

  // Function to display the linked list
  void display() const {
    Node* current = head;
    while (current != nullptr) {
      std::cout << current->data << " ";
      current = current->next;
    }
    std::cout << std::endl;
  }

  // Function to add a new node to the end of the list
  void push_back(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
      head = newNode;
    } else {
      Node* last = head;
      while (last->next != nullptr) {
        last = last->next;
      }
      last->next = newNode;
    }
  }
};

int main() {
  // Creating an original linked list
  LinkedList originalList;
  originalList.display();  // Output: (empty)

  // Adding elements to the original list
  originalList = {1, 2, 3, 4};  // Corrected assignment
  std::cout << "Original List: ";
  originalList.display();  // Output: 1 2 3 4

  // Creating a new linked list using the copy constructor
  LinkedList copiedList(originalList);
  std::cout << "Copied List: ";
  copiedList.display();  // Output: 1 2 3 4

  return 0;
}

We commence with the definition of a Node class, encapsulating the essence of individual elements within the linked list. Each node comprises an integer data and a next pointer, with the constructor initializing these values.

The introduction of the LinkedList class follows, featuring a private member head that serves as the entry point to the list. Two constructors are implemented, one for an empty list and another that accepts an initializer list to populate the list with specified values.

Central to our exploration is the copy constructor, a pivotal component. This constructor invokes the copyNodes helper function, which is responsible for traversing the original list and creating new nodes with identical data.

This methodology ensures the formation of a deep copy, establishing independent structures in memory.

A display function is crafted to facilitate a visual representation of the linked list contents, aiding in comprehending the state of the lists before and after the copy operation. Additionally, a push_back function is integrated, enabling the addition of a new node to the list’s end and offering a practical illustration of the deep copy mechanism in action.

Output:

The presented code showcases the importance of a deep copy method in the context of a linked list copy constructor. By carefully replicating the nodes and their data, the copy constructor ensures that the copied list remains distinct from the original.

The output of the code demonstrates the successful creation of a copied list without any shared memory references. Understanding and implementing such deep copy mechanisms are crucial for maintaining data integrity, especially in dynamic data structures like linked lists.

Move Semantics in C++ Linked List Copy Constructor

Utilizing move semantics in a Linked List copy constructor is crucial for optimal performance. Unlike deep copy methods, which involve duplicating data, move semantics allow the transfer of ownership of existing nodes.

This results in a more efficient process, minimizing unnecessary memory allocations and deallocations. Move semantics excel in scenarios where resource transfer, rather than duplication, is key, enhancing the overall speed and efficiency of the copy constructor.

This approach is particularly valuable when dealing with large datasets or frequent object transfers, contributing to a more streamlined and resource-efficient code.

Code Example:

#include <iostream>

// Node class to represent elements in the linked list
class Node {
 public:
  int data;
  Node* next;

  explicit Node(int value) : data(value), next(nullptr) {}
};

// Linked list class with a copy constructor using move semantics
class LinkedList {
 private:
  Node* head;

 public:
  // Constructor to initialize an empty linked list
  LinkedList() : head(nullptr) {}

  // Constructor to initialize linked list with values
  LinkedList(std::initializer_list<int> values) : head(nullptr) {
    for (int value : values) {
      push_back(value);
    }
  }

  // Copy Constructor using move semantics
  LinkedList(LinkedList&& other) noexcept : head(other.head) {
    other.head = nullptr;  // Reset the original list's head
  }

  // Copy Assignment Operator
  LinkedList& operator=(const LinkedList& other) {
    // Check for self-assignment
    if (this != &other) {
      // Delete existing nodes
      while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
      }

      // Perform deep copy
      Node* current = other.head;
      while (current != nullptr) {
        push_back(current->data);
        current = current->next;
      }
    }

    return *this;
  }

  // Destructor to free memory when the list goes out of scope
  ~LinkedList() {
    while (head != nullptr) {
      Node* temp = head;
      head = head->next;
      delete temp;
    }
  }

  // Function to display the linked list
  void display() const {
    Node* current = head;
    while (current != nullptr) {
      std::cout << current->data << " ";
      current = current->next;
    }
    std::cout << std::endl;
  }

  // Function to add a new node to the end of the list
  void push_back(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
      head = newNode;
    } else {
      Node* last = head;
      while (last->next != nullptr) {
        last = last->next;
      }
      last->next = newNode;
    }
  }
};

int main() {
  // Creating an original linked list
  LinkedList originalList;
  originalList.display();  // Output: (empty)

  // Adding elements to the original list
  originalList = {1, 2, 3, 4};
  std::cout << "Original List: ";
  originalList.display();  // Output: 1 2 3 4

  // Creating a new linked list using the move semantics copy constructor
  LinkedList movedList(std::move(originalList));
  std::cout << "Moved List: ";
  movedList.display();  // Output: 1 2 3 4

  // Displaying the original list after move
  std::cout << "Original List after Move: ";
  originalList.display();  // Output: (empty)

  return 0;
}

In this version, a custom copy assignment operator has been introduced to address the encountered error. The Node class remains integral, representing elements within the linked list with integer data and a pointer to the next node.

The LinkedList class now features default and initializer list constructors. The move semantics copy constructor efficiently transfers ownership, while the custom copy assignment operator ensures a deep copy when needed.

A destructor manages memory upon the list’s exit. Essential functions like display() and push_back(int value) facilitate output and node addition.

The main() function orchestrates a demonstration, creating, modifying, and displaying linked lists utilizing move semantics.

Output:

In the provided C++ code, an original linked list (originalList) is initialized as an empty list and displayed. Subsequently, elements {1, 2, 3, 4} are added to the original list through the assignment operator with an initializer list.

A new linked list (movedList) is then created using the move semantics copy constructor, facilitating the efficient transfer of ownership of elements from the original list to the new list. The display of the moved list confirms the successful move operation, while the output of the original list after the move signifies that its contents are now empty.

Conclusion

The article delved into the intricacies of linked lists, a fundamental data structure in C++. The focus centered on the copy constructor, a critical element for managing linked list duplications.

Various methods, such as shallow copy, deep copy, and move semantics, were explored for implementing the copy constructor. A comprehensive understanding of these concepts equips developers to make informed choices when implementing linked lists, balancing efficiency and data integrity in C++ programs.