Project 3: Circularly-linked list

Description

The purpose of this assignment is to write implementation of a node class that supports circularly-linked list functionality.

Instructions

1. Create new project and add the following C++ source files:

   • circularly_linked_list.h, the Node class header file.

   • circularly_linked_main.cpp, the file that contains the main( ) driver with sample client code to test the circularly-linked list. At the beginning you should comment out most of the code, so that you can compile and test your program after each implementation step.

2. Add new implementation file, circularly_linked_list.cpp, to the project. You will write your implementation of the Node class member functions in this file.

3. Each constructor of the Node object should set pointer to the next Node to pointng to itself. For example,

   
   // circularly_linked_list.cpp
   #include "circularly_linked_list.h"
   
   // Constructor
   Node::Node( int value )
   : pnext( NULL ), data( value )
   {
       pnext = this;
   }
   
   

4. Implement insert( ) function which inserts the other node in front of the current one. This function is almost identical to the insert function of the singly_linked_list.cpp presented earlier in class. The only difference is that the input parameter is now a reference to the other Node, and function should now return that reference back to the caller to allow chaining of the insert calls.

5. The Node copy constructor should insert the new node into the list by asking the original node to complete this operation:

   
   // Copy constructor
   Node::Node( Node const& other );
   : pnext( NULL ), data( other.data )
   {
       pnext = this;
       other.insert( *this );
   }
   
   

6. Add function is_single( ) that provides a boolean answer to the question whether the node is linked to itself or to some other node:

   
   bool Node::is_single() const
   {
       return ( pnext == this );
   }
   
   

7. Add distance( ) function to the Node implementation, so that it calculates the distance between the nodes measured in hops between the nodes:

   
   int Node::distance( Node const& other ) const
   {
       if ( &other == this && is_single() ) {
           return 0;
   
       } else if ( other.is_single() ) {
           // distance cannot be measured
           return -1;
       }
   
       int hops = 1;
   
       Node const* previous = this;
       Node const* iter = pnext;
       while ( iter != &other ) {
           previous = iter;
           if ( previous == this ) {
               return -1; // other not found on this list
           }
           iter = iter->pnext;
           ++hops;
       }
   
       return hops;
   }
   
   

8. Add size( ) function to return number of nodes in the list. Hint: call the distance( ) function to get the distance between the next node (pnext) and the current node (this).

9. Add implementation for the remove( ) function. It's first task is to locate the node that needs to be removed. The iteration is very similar to the one implemented by the distance( ) function. Once you have the pointer to the node to be removed, take it off the list, and then make removed node single by setting its pointer to itself. The remove function should return true if the node has been found (and successfully removed), false otherwise.

10. Add Node destructor to take the node object off the list before it gets destroyed:

    
    // Destructor
    Node::~Node()
    {
        remove( *this );
    }
    
    

11. Write implementation for the print_list( ) function that prints the list size and values of all nodes present in the list.

12. Make sure your code compiles and runs properly with the code in circularly_linked_main.cpp.

13. You have 1 week to complete this assignment. When ready, submit your source files via e-mail attachment sent to:
    Igor Kholodov Igor.Kholodov@bristolcc.edu
    Please ZIP multiple files into a single archive before attaching.
    Thank you!