Question

Working with Linked Lists in C++

Tasks

As stated in the objectives, you have two methods to implement. These methods (which contain TODO comments) are found in linked_list.cpp.

Part 1

Implement the copy constructor; use the LinkedBag as inspiration for your solution as the technique of creating a deep copy is essentially the same.

Part 2

Implement the replace method.

//linked_list.cpp

#include "linked_list.h"  // Header file
#include <cassert>

template<class Object>
LinkedList<Object>::LinkedList()
        : headPtr( nullptr ), itemCount( 0 )
{
}  // end default constructor

template<class Object>
LinkedList<Object>::LinkedList(const LinkedList<Object>& aList)
        : itemCount( aList.itemCount )
{
    // TODO: Implement me
}  // end copy constructor

template<class Object>
LinkedList<Object>::~LinkedList()
{
    clear();
}  // end destructor

template<class Object>
bool LinkedList<Object>::isEmpty() const
{
    return itemCount == 0;
}  // end isEmpty

template<class Object>
int LinkedList<Object>::getLength() const
{
    return itemCount;
}  // end getLength

template<class Object>
bool LinkedList<Object>::insert(int newPosition, const Object& newEntry)
{
    bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
    if (ableToInsert)
    {
        // Create a new node containing the new entry
        auto newNodePtr = new Node<Object>( newEntry );

        // Attach new node to chain
        if (newPosition == 1)
        {
            // Insert new node at beginning of chain
            newNodePtr->setNext( headPtr );
            headPtr = newNodePtr;
        }
        else
        {
            // Find node that will be before new node
            Node<Object>* prevPtr = getNodeAt( newPosition - 1 );

            // Insert new node after node to which prevPtr points
            newNodePtr->setNext( prevPtr->getNext());
            prevPtr->setNext( newNodePtr );
        }  // end if

        itemCount++;  // Increase count of entries
    }  // end if

    return ableToInsert;
}  // end insert

template<class Object>
bool LinkedList<Object>::remove(int position)
{
    bool ableToRemove = (position >= 1) && (position <= itemCount);
    if (ableToRemove)
    {
        Node<Object>* curPtr = nullptr;
        if (position == 1)
        {
            // Remove the first node in the chain
            curPtr = headPtr; // Save pointer to node
            headPtr = headPtr->getNext();
        }
        else
        {
            // Find node that is before the one to delete
            Node<Object>* prevPtr = getNodeAt( position - 1 );

            // Point to node to delete
            curPtr = prevPtr->getNext();

            // Disconnect indicated node from chain by connecting the
            // prior node with the one after
            prevPtr->setNext( curPtr->getNext());
        }  // end if

        // Return node to system
        curPtr->setNext( nullptr );
        delete curPtr;
        curPtr = nullptr;

        itemCount--;  // Decrease count of entries
    }  // end if

    return ableToRemove;
}  // end remove

template<class Object>
void LinkedList<Object>::clear()
{
    while (!isEmpty())
        remove( 1 );
}  // end clear

template<class Object>
Object LinkedList<Object>::getEntry(int position) const noexcept( false )
{
    // Enforce precondition
    bool ableToGet = (position >= 1) && (position <= itemCount);
    if (ableToGet)
    {
        Node<Object>* nodePtr = getNodeAt( position );
        return nodePtr->getItem();
    }
    else
    {
        std::string message = "getEntry() called with an empty list or ";
        message = message + "invalid position.";
        throw (PrecondViolatedExcep( message ));
    }  // end if
}  // end getEntry

template<class Object>
void LinkedList<Object>::replace(int position, const Object& newEntry) noexcept( false )
{
    // TODO: Implement me; throw a PrecondViolatedExcep if preconditions aren't met
}  // end replace

template<class Object>
Node<Object>* LinkedList<Object>::getNodeAt(int position) const noexcept( false )
{
    // Check preconditions
    if ((position < 1) || (position > itemCount))
    {
        std::string message = "private helper method called with an invalid position";
        throw (PrecondViolatedExcep( message ));
    }

    // Count from the beginning of the chain
    Node<Object>* curPtr = headPtr;
    for (int skip = 1; skip < position; skip++)
    {
        curPtr = curPtr->getNext();
    }

    return curPtr;
}  // end getNodeAt
//  End of implementation file.

Answer 1

#include "linked_list.h" // Header file
#include <cassert>

template<class Object>
LinkedList<Object>::LinkedList()
: headPtr( nullptr ), itemCount( 0 )
{
} // end default constructor

template<class Object>
LinkedList<Object>::LinkedList(const LinkedList<Object>& aList)
: itemCount( aList.itemCount )
{
   // initialize headPtr to null
headPtr = nullptr;
  
   // set listCurPtr to head node of aList
   Node<Object>* listCurPtr = aList.headPtr;
  
   // set curPtr to head node of this list
   Node<Object>* curPtr = headPtr;
  
   // loop over the aList
   while(listCurPtr != nullptr)
   {
       // create a new node with item from listCurPtr
       Node<Object>* node = new Node<Object>(listCurPtr->getItem());
      
       // headPtr is null, set node to headPtr
       if(headPtr == nullptr)
       {
           headPtr = node;
           curPtr = headPtr; // set curr to headPtr
       }
       else // headPtr is not null
       {
           curPtr->setNext(node); // set next of curPtr to node
           curPtr = curPtr->getNext(); // move curPtr to the newly inserted node
       }
      
       // move listCurPtr to next node
       listCurPtr = listCurPtr->getNext();
   }
  
} // end copy constructor

template<class Object>
LinkedList<Object>::~LinkedList()
{
clear();
} // end destructor

template<class Object>
bool LinkedList<Object>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty

template<class Object>
int LinkedList<Object>::getLength() const
{
return itemCount;
} // end getLength

template<class Object>
bool LinkedList<Object>::insert(int newPosition, const Object& newEntry)
{
bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
auto newNodePtr = new Node<Object>( newEntry );

// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext( headPtr );
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
Node<Object>* prevPtr = getNodeAt( newPosition - 1 );

// Insert new node after node to which prevPtr points
newNodePtr->setNext( prevPtr->getNext());
prevPtr->setNext( newNodePtr );
} // end if

itemCount++; // Increase count of entries
} // end if

return ableToInsert;
} // end insert

template<class Object>
bool LinkedList<Object>::remove(int position)
{
bool ableToRemove = (position >= 1) && (position <= itemCount);
if (ableToRemove)
{
Node<Object>* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
}
else
{
// Find node that is before the one to delete
Node<Object>* prevPtr = getNodeAt( position - 1 );

// Point to node to delete
curPtr = prevPtr->getNext();

// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext( curPtr->getNext());
} // end if

// Return node to system
curPtr->setNext( nullptr );
delete curPtr;
curPtr = nullptr;

itemCount--; // Decrease count of entries
} // end if

return ableToRemove;
} // end remove

template<class Object>
void LinkedList<Object>::clear()
{
while (!isEmpty())
remove( 1 );
} // end clear

template<class Object>
Object LinkedList<Object>::getEntry(int position) const noexcept( false )
{
// Enforce precondition
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node<Object>* nodePtr = getNodeAt( position );
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw (PrecondViolatedExcep( message ));
} // end if
} // end getEntry

template<class Object>
void LinkedList<Object>::replace(int position, const Object& newEntry) noexcept( false )
{
   // invalid position, throw PrecondViolatedExcep
if(position < 1 || position > itemCount)
   {
       std::string message = "replace() called with an invalid position";
       throw (PrecondViolatedExcep( message ));
   }

   // get the node at position
   Node<Object>* nodePtr = getNodeAt(position);
  
   // update the item of nodePtr to newEntry
   nodePtr->setItem(newEntry); // assuming Node class contains a method setItem to update the item of the node  
      
} // end replace

template<class Object>
Node<Object>* LinkedList<Object>::getNodeAt(int position) const noexcept( false )
{
// Check preconditions
if ((position < 1) || (position > itemCount))
{
std::string message = "private helper method called with an invalid position";
throw (PrecondViolatedExcep( message ));
}

// Count from the beginning of the chain
Node<Object>* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
{
curPtr = curPtr->getNext();
}

return curPtr;
} // end getNodeAt
// End of implementation file.