Clone a linked list nodes

Clone is a way to copy node value existing linked list to new linked list. That is very useful mechanism which are used in most of cases. When we are modified clone linked list there no effect on actual original linkedlist.

Clone of linked list

Note that actual linked list are not modified when changes on clone linked list. And clone linked list node address are different to actual linked list node. Here given code implementation process.

//C Program
//Clone a linked list nodes
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);


//insert Node element
void insert(struct Node**head,int value)
{
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
    
  }else
  {
    node->data=value;
    node->next=NULL;
    if(*head==NULL)
    {
      *head=node;

    }else
    {
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Clone a given singly linked list and 
//returning the head of new created list
struct Node * clone(struct Node *root)
{
  if(root==NULL) return NULL;

  struct Node *list=NULL,*tail=NULL,*new_node=NULL;
  while(root!=NULL)
  {

    //Allocate memory of new node
    new_node=(struct Node*)malloc(sizeof(struct Node));
    
    if(new_node!=NULL)
    {
      new_node->data=root->data;
      new_node->next=NULL;

      if(list==NULL)
      {
        //When first linked list node
        list=new_node;
      }else
      {
        tail->next=new_node;
      }
      tail=new_node;

    }else
    {
      printf("Memory overflow\n");
      break;
    }
    root=root->next;
  }
  return list;
}
//Display element of Node
void display(struct Node*temp)
{
  
  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  while(temp!=NULL)
  {
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
int main()
{
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list

  insert(&head,1);
  insert(&head,-3);
  insert(&head,9);
  insert(&head,4);
  insert(&head,11);
  insert(&head,-7);

  struct Node*root=clone(head);

  //display all node
  display(root);

  return 0;
}

Output

1  -3  9  4  11  -7
//C++ Program 
//Clone a linked list nodes
#include <iostream>
using namespace std;

//create structure
struct Node
{
  int data;
  struct Node*next;
};
class LinkedList
{
  Node*head;//head node
public:
  LinkedList();
  void insert(int);
  void display();
  LinkedList clone();
};
LinkedList::LinkedList()
{
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value)
{
  //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }else
  {
    node->data=value;
    node->next=NULL;
    if(head==NULL)
    {
      //base condition
      head=node;
    }else
    {
      Node*temp=head;
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//Clone a given singly linked list and 
//returning the head of new created list
LinkedList LinkedList :: clone()
{
  
  Node *root=head;

  LinkedList newList;

  if(root==NULL) return newList;

  Node *list=NULL,*tail=NULL,*new_node=NULL;

  while(root!=NULL)
  {

    //Allocate memory of new node
    new_node=new Node;
    
    if(new_node!=NULL)
    {
      new_node->data=root->data;
      new_node->next=NULL;

      if(list==NULL)
      {
        //When first linked list node
        list=new_node;
      }else
      {
        tail->next=new_node;
      }
      tail=new_node;

    }else
    {
      cout<<"\nMemory overflow\n";
      break;
    }
    root=root->next;
  }
  newList.head=list;

  return newList;
}

//display all node value in linked list
void LinkedList:: display()
{
  if(head==NULL)
  {
    cout<<"Empty linked list";
  }
  else
  {
    Node*temp=head;
    cout<<"\nLinked List : ";
    while(temp!=NULL)
    {
      //print node value
      cout<<temp->data<<" ";
      temp=temp->next;
    }
  }

}
int main()
{

  //create object
  LinkedList obj;
  //insert element of linked list
  obj.insert(1);
  obj.insert(-3);
  obj.insert(9);
  obj.insert(4);
  obj.insert(11);
  obj.insert(7);

  //display all node
  obj.display();

  LinkedList obj2;

  obj2=obj.clone();

  //new linked list
  obj2.display();
  return 0;
}

Output

Linked List : 1 -3 9 4 11 7 
Linked List : 1 -3 9 4 11 7
//Java Program
//Clone a linked list nodes
public class LinkedList
{

  static class Node
  {
    int data;
    Node next;
  }
  private Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }
    
  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {

      Node temp=head;
      while(temp!=null)
      {
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
      System.out.println();
    }else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  //Clone a given singly linked list 
  
  public LinkedList clone()
  {

    Node root=head;

    LinkedList newList=new LinkedList();

    if(root==null) return newList;

    Node list=null,tail=null,new_node=null;

    while(root!=null)
    {

      //Allocate memory of new node
      new_node=new Node();
      new_node.data=root.data;
      new_node.next=null;

      if(list==null)
      {
      //When first linked list node
        list=new_node;
      }else
      {
        tail.next=new_node;
      }
      tail=new_node;
      root=root.next;
    }
    newList.head=list;

    return newList;
  }
  public static void main(String[] args) 
  {

    LinkedList obj=new LinkedList();
    obj.insert(1);
    obj.insert(-3);
    obj.insert(9);
    obj.insert(4);
    obj.insert(11);
    obj.insert(7);

    obj.display();

    LinkedList obj2= obj.clone();
    System.out.println(" Clone Linked List ");
    obj2.display();
  }
}

Output

  1  -3  9  4  11  7
 Clone Linked List 
  1  -3  9  4  11  7
#Python Program
#Clone a linked list nodes
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
      #Assign default value
      self.head=None

    #insert new node to linked list  
    def insert(self,data):
      node=Node(data)
      node.next=None
      if self.head==None:
          self.head=node
      else:
          temp=self.head
          while temp.next!=None:
            temp=temp.next
          #add node    
          temp.next=node

    def display(self):
      if(self.head==None):
        print("Empty Linked List")
        return

      temp=self.head


      while(temp!=None):
        print(temp.data,end=" ")
        temp=temp.next

      print()
    def clone(self) :

      root=self.head

      newList=Linked()

      if(root==None) :
        return newList

      result=None
      tail=None
      new_node=None

      while(root!=None) :

        #Allocate memory of new node
        new_node=Node(root.data)
        if(result==None):
          #When first linked list node
          result=new_node
        else :
          tail.next=new_node
        
        tail=new_node
        root=root.next
      
      #set new linked list head node
      newList.head=result

      return newList
  

def main():
    #Create Object of class Linked
    obj=Linked()
    #Perform Linked operation
    obj.insert(1)
    obj.insert(-3)
    obj.insert(9)
    obj.insert(4)
    obj.insert(11)
    obj.insert(7)

    print("\nLinked List Elements  ")
    obj.display()

    obj2=obj.clone()
    print("\nClone Linked List Elements  ")
    obj2.display()

if __name__=="__main__":
    main()

Output

Linked List Elements  
1 -3 9 4 11 7 

Clone Linked List Elements  
1 -3 9 4 11 7 
//C# Program
//Clone a linked list nodes
using System;
public class Node
{
  public int data;
  public Node next;
}
public class LinkedList
{


  private Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }

  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {

      Node temp=head;
      while(temp!=null)
      {
        Console.Write(" {0}",temp.data);
        temp=temp.next;
      }
      Console.WriteLine();
    }else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  //Clone a given singly linked list 

  public LinkedList clone()
  {

    Node root=head;

    LinkedList newList=new LinkedList();

    if(root==null) return newList;

    Node list=null,tail=null,new_node=null;

    while(root!=null)
    {

      //Allocate memory of new node
      new_node=new Node();
      new_node.data=root.data;
      new_node.next=null;

      if(list==null)
      {
        //When first linked list node
        list=new_node;
      }else
      {
        tail.next=new_node;
      }
      tail=new_node;
      root=root.next;
    }
    newList.head=list;

    return newList;
  }
  public static void Main(String[] args) 
  {

    LinkedList obj=new LinkedList();
    obj.insert(1);
    obj.insert(-3);
    obj.insert(9);
    obj.insert(4);
    obj.insert(11);
    obj.insert(7);

    obj.display();

    LinkedList obj2= obj.clone();
    Console.WriteLine(" Clone Linked List ");
    obj2.display();
  }
}

Output

 1 -3 9 4 11 7
 Clone Linked List 
 1 -3 9 4 11 7
<?php
//Php program 
//Clone a linked list nodes
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
  }
}
class LinkedList
{

  private $head;
  function __construct()
  {
    $head=NULL;
  }
    /*
    * Append the Given data value at end of linked list
    * Fun : insert
    * Parm: data value
    *@return None
    */
    function insert($data)
    {
      $newNode=new Node($data); 
      if($this->head==NULL)
      {
        $this->head=$newNode;
      }else{
        $temp=$this->head;
            //find last node of linked list
        while($temp->next!=NULL)
        {
          $temp=$temp->next;
        }
            //add new node to last of linked list
        $temp->next=$newNode;
      }
    }
    //Display all inserted node in linked list
    function display()
    {
      if($this->head==NULL)
      {
        echo "Empty Linked List";
      }
      else
      {
        $temp=$this->head;
        echo "Linked List :";
        while($temp!=NULL)
        {
          //display node value
          echo "  ".$temp->data;
          $temp=$temp->next; //visit to next node
        }
        echo "\n";
      }   
    }
    function clone()
    {
      
      $root=$this->head;

      $newList = new LinkedList();

      if($root==NULL) return $newList;

      $list=NULL;
      $tail=NULL;
      $new_node=NULL;

      while($root!=NULL)
      {

        //Allocate memory of new node
        $new_node=new Node($root->data);
        
     
        $new_node->data=$root->data;
        $new_node->next=NULL;

        if($list==NULL)
        {
          //When first linked list node
          $list=$new_node;
        }else
        {
          $tail->next=$new_node;
        }
        $tail=$new_node;

        
        $root=$root->next;
      }
      $newList->head=$list;

      return $newList;
    }

  }
  function main()
  {
    //Make a object of LinkedList class
    $obj = new LinkedList();

    /*
    *Insert following nodes in linked list
    */
    $obj->insert(1);
    $obj->insert(-3);
    $obj->insert(9);
    $obj->insert(4);
    $obj->insert(11);
    $obj->insert(7);

    //display all node
    $obj->display();


    $obj2=$obj->clone();

    //new linked list
    $obj2->display();
  }
  main();
  ?>

Output

Linked List Elements  
1 -3 9 4 11 7 

Clone Linked List Elements  
1 -3 9 4 11 7 


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved