UnsortedLinkedList.cpp - VTC C++ Unsorted Linked List

/**
 * [UnsortedLinkedList.cpp]
 * The UnsortedLinkedList class definition/implementation.
 */

#include "UnsortedLinkedList.h"


/**
 * UnsortedLinkedList CLASS CONSTRUCTOR(s):
 */
UnsortedLinkedList::UnsortedLinkedList()
{
    length = 0;
    data = 0;
}


/**
 * UnsortedLinkedList CLASS ACCESSORS:
 */
float UnsortedLinkedList::GetNextItem(void)
{
        if(currentPos == 0)     // if the current position is null...
            currentPos = data;  // ...the next item will be the head
        else
            currentPos = currentPos->next; // move to the next item after the current position

    return currentPos->element;
}


/**
 * UnsortedLinkedList CLASS MUTATORS:
 */
void UnsortedLinkedList::InsertItem(float item)
{
    /**
     * NOTE:
     * In an array-based list, items are added to the end, in this (unsorted linked) list, to make
     * things easy, items will be added to the beginning.
     */
    Node    *location = new Node(); // a new node is created because a new one is being added

    location->element = item;       // the new node (the first one) takes the value of the item passed in as parameter
    location->next = data;          // points to the previous head, which was the data
    data = location;                // returns data back to location, because data must always point to the first item in the list
    length++;                       // increment length to reflect the preceding addition of an item
}

void UnsortedLinkedList::DeleteItem(float item)
{
    /**
     * NOTE:
     *
     * Method for deleting an item:
     * i. Find the item to be deleted.
     * ii. Keep the item in a temporary pointer.
     * iii. Link the item before it to the item after it.
     * iv. It this point the item can/will be deleted.
     *
     * The point here is not to lose the linkage between items if one is being deleted.  Therefore,
     * there must be implementations to make sure the list is still linked.
     *
     * To achieve this goal, two pointers will be needed; one to keep a temporary item, and the other
     * will facilitate going through the list.
     */

    Node    *location;

        /**
         * NOTE:
         * The item to be deleted might exist in the list as duplicates.  In such a case, the list
         * should be recursed until all duplicates of the provided item are deleted.
         */
        for(int i = 0; i < length; i++) //fix
        {
            Node    *pTemp;     // will hold the temporary item

            location = data;    // points to the beginning/head of the list

                /**
                 * In the event of deleting an item from a an unsorted linked list, one of two
                 * scenarios will exist:
                 *
                 * If the item to be deleted is at the head of the list, the head can simply be moved
                 * to the item after that one, then it will be safe to get rid of the node.
                 */
                if(item == data->element || length == 1)
                {
                    pTemp = location;

                        /**
                         * NOTE:
                         * If the list contains only one item, it will simply be set to null (0), or
                         * setting it to the next item would be impossible, hence crashing the program.
                         */
                        (length == 1) ? data = 0 : data = data->next;

                    length--;       //fix
                }
                /**
                 * If the item to be deleted is not at the head of the list:
                 */
                else
                {
                        /**
                         * While going through the list, the code must keep track of the item before
                         * the one to be deleted.  Also, the end of the list must not be passed.
                         */
                        while(!(item == (location->next)->element) && (location->next)->next != 0)  // location will always store the item before the one to be deleted
                        {
                            location = location->next;  // move location to the one next to it until it is found
                        }

                        /**
                         * NOTE:
                         * If the item to be deleted is actually found, the following block of code
                         * will be executed.
                         *
                         * The condition is used to safeguard against an attempt to delete a provided
                         * item that is not on the list.
                         */
                        if(location->next->element == item)
                        {
                            pTemp = location->next; // store the item to be deleted in the temporary pointer

                            length--; // decrement the list length to reflect the item deletion

                            location->next = (location->next)->next; // link the item before the one to be deleted to the one after it
                        }
                }

            delete pTemp; // delete the item/unused pointer in either case
        }
}


/**
 * UnsortedLinkedList CLASS GENERAL USE FUNCTIONS:
 */
bool UnsortedLinkedList::IsEmpty(void)
{
    if(length == 0)
        return true;
    else
        return false;
}

bool UnsortedLinkedList::IsFull(void)
{
    Node    *pNode = new Node();    // attempts to allocate memory for another element

        if(pNode == 0)              // if the memory allocation attempt failed...
            return true;            // ...the list is full
        else
        {
            delete pNode;

            return false;
        }
}

void UnsortedLinkedList::ResetList(void)
{
    currentPos = 0;
}

void UnsortedLinkedList::MakeEmpty(void)
{
    Node    *pTempNode = new Node();    // allocates memory for a temporary node

        while(data != 0)
        {
            pTempNode = data;           // stores an element of the list in the temporary pointer

            data = data->next;          // points to the next item in the list (move to the next one)

            delete pTempNode;           // delete the temporary pointer
        }

    length = 0;                         // sets the length of the list to 0, reflecting its items deletion
}

int UnsortedLinkedList::LengthIs(void)
{
    return length;
}

bool UnsortedLinkedList::IsInTheList(float item)
{
    Node    *location = new Node();     // the current location in the list

    location = data;                    // starting from the beginning of the list


     bool   found = false;

        while(location != 0 && !found)
        {
            /**
             * NOTE:
             * Location is a node, that has the element, which is the value being added...
             */
            if(item == location->element)
                found = true;
            else
                /**
                 * ...it also contains a pointer to the next node, through the next variable.
                 */
                location = location->next;  // move to the next item if the item is not found
        }

    return found;
}

void UnsortedLinkedList::Print(void)
{
    Node    *location = new Node();

    location = data;    // points to the head

        while(location != 0)    // while the end of the list is not reached
        {
            std::cout << location->element << std::endl; // ...print the element part of each node

            location = location->next;  // ...move to the next item
        }
}