Thread: trouble making making copy constructor for circular linked list

  1. #1
    Registered User
    Join Date
    Jun 2014
    Location
    Tampa, Florida, United States
    Posts
    28

    trouble making making copy constructor for circular linked list

    As the title suggests, i'm attempting to make the copy constructor in my class copy each element in the circular linked list. I am just starting to learn about linked lists in general, but i wanted to verify to see if the logic makes sense,

    Code:
    #include <iostream>
    
    
    
    
    template <class T>
    class List{
    
    
    private:
        class Node {
            T data;
            Node *next;
        };
    public:
    
    
        List();
        List(const List &);
        ~List();
    
    
        int getSize() const;
    
    
        bool isEmpty() const;
        bool insert(const T&, const int &);
        bool remove(const int &);
    
    
        T runJosephusAlgorithm();
    
    
        const List& operator=(const List&);
    
    
        void display(ostream&) const;
        friend ostream& operator << <>(ostream&, const List<T>&);
    
    
    private:
        Node *first; // pointer to the first element of the linked list
    
    
    
    
    
    
    };
    
    
    template <class T>
    
    
    List<T>::List()                                     //implements the default constructor to create an empty list     
    {
    }
    
    
    template <class T>               
    List<T>::List(const List & Original_list)          // copy constructor creates copy of original list in body
    {
        
        Node *newNodeptr = NULL; 
        first = Original_list.head; //original pointer
        
        do
        {
            newNodeptr = new Node;                              // do while 
            newNodeptr -> data = first ->data; 
            newNodeptr = newNodeptr ->next; 
            first = first ->next; 
            
        }while(first ->next!= Original_list.head);
        
    }
    
    
    
    
    int main()
    {
        
    }
    The thinking i had behind the copy constructor is that I have "first" pointer, pointing to the original list head and another pointer pointing to NULL, but later while be implemented to point to the copy constructors first head( given that the while loop condition is satisfied: while the pointer pointing to the next head in the original list is not the first head, then it keeps copying nodes until the circular list has been copied). The elements are also copied into the new node made in the do while loop, and then the both the first pointer and new node pointer are both incremented into the next node to do the same thing ( copy contents etc).

    A few questions about linked lists in general: If i'm trying to make a linked list 'circular', does this imply that i can't have any pointers pointing to NULL since the last pointer of the last node should always point to the first head? How do i make it so that the loop circulates, meaning in terms of the programming how is it different from just a singly linked list?

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    For a circular linked list, it may make more sense to have a pointer to the last node of a list, which in turn points to the first node of a list. This makes append operations faster.

    Instead of using a dummy node, a pointer to pointer can be used to simplify appending nodes to what is initially an empty list. These are circular list examples.

    Code:
        Node *pNew = NULL;           // ptr to empty list
        Node **ppNew = &pNew;        // ptr to pNew or the last node's next pointer
        Node *pNode;                 // temp ptr
        // ...
            *pNode = new Node;       // allocate a node
            // ...
            *ppNew = pNode;          // append node to list
            ppNew = &(pNode->next);  // advance ppNew
            pNode->next = pNew;      // set pointer to first node
    or you can use a check for empty list:

    Code:
        Node *pNew = NULL;           // ptr to empty list
        Node *pLast = NULL;          // ptr to last node of list
        Node *pNode;                 // temp ptr
        // ...
            *pNode = new Node;       // allocate a node
            // ...
            if(pNew == NULL){        // append node to list
                pNew  = pNode;
                pLast = pNode;
            }else{
                pLast->next = pNode;
            }
            pNode->next = pNew;      // set pointer to first node
    Last edited by rcgldr; 09-09-2015 at 08:49 PM.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Too late to edit or delete my previous post. The name changes might make it easier to understand the examples:

    using pointer to pointer:

    Code:
        Node *pFirst = NULL;          // ptr to empty list
        Node **ppLast = &pFirst;      // ptr to pFirst or the last node's next pointer
        Node *pNode;                  // temp ptr
        // ...
            *pNode = new Node;        // allocate a node
            // ...
            *ppLast = pNode;          // append node to list
            ppLast = &(pNode->next);  // advance ppLast
            pNode->next = pFirst;     // set pointer to first node
    using check for empty list:

    Code:
        Node *pFirst = NULL;          // ptr to empty list
        Node *pLast = NULL;           // ptr to last node of list
        Node *pNode;                  // temp ptr
        // ...
            *pNode = new Node;        // allocate a node
            // ...
            if(pFirst == NULL){       // append node to list
                pFirst = pNode;
                pLast  = pNode;
            }else{
                pLast->next = pNode;
            }
            pNode->next = pFirst;     // set pointer to first node
    Last edited by rcgldr; 09-09-2015 at 11:09 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Making A Linked List From A 2D Array
    By Al3x_Payn3 in forum C Programming
    Replies: 1
    Last Post: 11-24-2014, 07:39 PM
  2. Trouble making a font name list
    By geek@02 in forum Windows Programming
    Replies: 6
    Last Post: 11-10-2006, 04:20 PM
  3. Linked list copy constructor issue
    By Craptastic! in forum C++ Programming
    Replies: 1
    Last Post: 08-03-2003, 08:30 PM
  4. linked list copy constructor
    By brianptodd in forum C++ Programming
    Replies: 3
    Last Post: 04-15-2003, 11:45 AM
  5. Making a doubly linked list
    By mlupo in forum C Programming
    Replies: 1
    Last Post: 10-16-2002, 09:05 PM