Question

Double Linked Lists: Implement the PutItem and DeleteItem function

// ItemType.h

#ifndef ITEMTYPE_H
#define ITEMTYPE_H

enum RelationType { LESS, GREATER, EQUAL};

class ItemType
{
public:
    ItemType();
    void Initialize(int number);
    int getValue() const;
    RelationType ComparedTo(ItemType);

private:
    int value;
};

#endif // ITEMTYPE_H

// ItemType.cpp

#include "ItemType.h"

ItemType::ItemType()
{
    value = 0;
}

void ItemType::Initialize(int number)
{
    value = number;
}

RelationType ItemType::ComparedTo(ItemType otherItem)
{
        if(value < otherItem.value)
            return LESS;
        else if (value > otherItem.value)
            return GREATER;
        else // if they are equal
            return EQUAL;
}

int ItemType::getValue() const
{
    return value;
}

// DoubleLists.h

#include "ItemType.h"

struct NodeType;

class DoubleLists
{
public:
    DoubleLists();
    ~DoubleLists();

    bool IsFull() const;
    int GetLength() const;
    void MakeEmpty();
    void ResetList();
    ItemType GetNextItem();
    void FindItem(NodeType *listData, ItemType item, NodeType *&location, bool &found);
    void PutItem(ItemType item);
    void DeleteItem(ItemType item);
    void PrintForward() const;

private:
    NodeType *head;
    NodeType *currentPos;
    NodeType *tail;
    int length;
};

struct NodeType
{
    ItemType info;
    NodeType *next;
    NodeType *back;
};

// DoubleLists.cpp

#include "DoubleLists.h"
#include <exception>
#include <iostream>
using namespace std;

DoubleLists::DoubleLists()
{
    length = 0;
    head = nullptr;
    tail = nullptr;
}

bool DoubleLists::IsFull() const
{
    NodeType *location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc exception)
    {
        return true;
    }
}

int DoubleLists::GetLength() const
{
    return length;
}

void DoubleLists::MakeEmpty()
{
    NodeType *tempPtr;

    while(head != nullptr)
    {
        tempPtr = head;
        head = head->next;
        delete tempPtr;
    }
    length = 0;
}

void DoubleLists::ResetList()
{
    currentPos = nullptr;
}

ItemType DoubleLists::GetNextItem()
{
    ItemType item;
    if(currentPos == nullptr)
    {
        currentPos = head;
    }
    item = currentPos->info;
    currentPos = currentPos->next;
    return item;
}

DoubleLists::~DoubleLists()
{
    NodeType *tempPtr;

    while(head != nullptr)
    {
        tempPtr = head;
        head = head->next;
        delete tempPtr;
    }
}

void DoubleLists::PrintForward() const
{
    NodeType *tempPtr = head;
    while (tempPtr != nullptr)
    {
        cout << (tempPtr->info).getValue() << " ";
        tempPtr = tempPtr->next;
    }
}

void DoubleLists::FindItem(NodeType *head, ItemType item, NodeType *&location, bool &found)
{
    bool moreToSearch = true;

    location = head;
    found = false;
    while (moreToSearch && !found)
    {
        if(item.ComparedTo(location->info) == LESS)
        {
            moreToSearch = false;
        }
        else if (item.ComparedTo(location->info) == EQUAL)
        {
            found = true;
        }
        else // if result is GREATER
        {
            location = location->next;
            moreToSearch = (location != nullptr);
        }
    }
}

void DoubleLists::PutItem(ItemType item)
{
    NodeType *newNode;
    NodeType *location;
    bool found;

    // creating a new node with the item data
    newNode = new NodeType;
    newNode->info = item;

    // Finish code here, use FindItem to find insertion point
}
/*
void DoubleLists::DeleteItem(ItemType item)
{
    // Finish code here, use FindItem to find insertion point.
}

How would you finish PutItem and DeleteItem function?

// in main

DoubleLists d;

ItemType i;

i.Initialize(1);

PutItem(i);

i.Initialize(3);

PutItem(i);

i.Initialize(5);

PutItem(i);

i.Initialize(2);

PutItem(i);

// print the data starting from head of list

d.PrintForward();

Output:

1 2 3 5

Answer 1

#######################################
     DoubleLists.cpp
#######################################
#include "DoubleLists.h"
#include <exception>
#include <iostream>
using namespace std;

DoubleLists::DoubleLists()
{
    length = 0;
    head = nullptr;
    tail = nullptr;
}

bool DoubleLists::IsFull() const
{
    NodeType *location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc exception)
    {
        return true;
    }
}

int DoubleLists::GetLength() const
{
    return length;
}

void DoubleLists::MakeEmpty()
{
    NodeType *tempPtr;

    while(head != nullptr)
    {
        tempPtr = head;
        head = head->next;
        delete tempPtr;
    }
    length = 0;
}

void DoubleLists::ResetList()
{
    currentPos = nullptr;
}

ItemType DoubleLists::GetNextItem()
{
    ItemType item;
    if(currentPos == nullptr)
    {
        currentPos = head;
    }
    item = currentPos->info;
    currentPos = currentPos->next;
    return item;
}

DoubleLists::~DoubleLists()
{
    NodeType *tempPtr;

    while(head != nullptr)
    {
        tempPtr = head;
        head = head->next;
        delete tempPtr;
    }
}

void DoubleLists::PrintForward() const
{
    NodeType *tempPtr = head;
    while (tempPtr != nullptr)
    {
        cout << (tempPtr->info).getValue() << " ";
        tempPtr = tempPtr->next;
    }
}

void DoubleLists::FindItem(NodeType *head, ItemType item, NodeType *&location, bool &found)
{
    bool moreToSearch = true;

    location = head;
    found = false;
    while (location != NULL && moreToSearch && !found)
    {
        if(item.ComparedTo(location->info) == LESS)
        {
            moreToSearch = false;
        }
        else if (item.ComparedTo(location->info) == EQUAL)
        {
            found = true;
        }
        else // if result is GREATER
        {
            location = location->next;
            moreToSearch = (location != nullptr);
        }
    }
}

void DoubleLists::PutItem(ItemType item)
{
    NodeType *newNode;
    NodeType *location;
    bool found = false;

    // creating a new node with the item data
    newNode = new NodeType;
    newNode->info = item;
    
    FindItem(head, item, location, found);

    if(found) {
            // item is already present
            return;
    }

    if(length == 0) {
            head = newNode;
            tail = newNode;
            length++;
    } else {
            if(item.ComparedTo(head->info) == LESS) {
                newNode->next = head;
                head->back = newNode;
                head = newNode;
                length++;
            } else {
                NodeType *curr = head->next;
                NodeType *prev = head;

                while(curr != NULL && item.ComparedTo(curr->info) == GREATER) {
                        prev = curr;
                        curr = curr->next;
                }
                newNode->next = prev->next;
                newNode->back = prev;
                prev->next = newNode;
                if(curr != NULL) {
                        curr->back = newNode;
                } else {
                        tail = prev;
                }
                length++;
            }
    }


    // Finish code here, use FindItem to find insertion point
}

/* */
void DoubleLists::DeleteItem(ItemType item)
{
    NodeType *newNode;
    NodeType *location;
    bool found = false;
    
    FindItem(head, item, location, found);
    if(found) {
        NodeType *prev = location->back;
        NodeType *next = location->next;

        if(prev == NULL) {
                head = head->next;
        } else {
                prev->next = next;
        }
        if(next == NULL) {
                tail = tail->back;
        } else {
                next->back = prev;
        }
        length--;
    }
}



#######################################
       DoubleLists.h
#######################################
#include "ItemType.h"

struct NodeType;

class DoubleLists
{
public:
    DoubleLists();
    ~DoubleLists();

    bool IsFull() const;
    int GetLength() const;
    void MakeEmpty();
    void ResetList();
    ItemType GetNextItem();
    void FindItem(NodeType *listData, ItemType item, NodeType *&location, bool &found);
    void PutItem(ItemType item);
    void DeleteItem(ItemType item);
    void PrintForward() const;

private:
    NodeType *head;
    NodeType *currentPos;
    NodeType *tail;
    int length;
};

struct NodeType
{
    ItemType info;
    NodeType *next;
    NodeType *back;
};





#######################################
        ItemType.cpp
#######################################
#include "ItemType.h"

ItemType::ItemType()
{
    value = 0;
}

void ItemType::Initialize(int number)
{
    value = number;
}

RelationType ItemType::ComparedTo(ItemType otherItem)
{
        if(value < otherItem.value)
            return LESS;
        else if (value > otherItem.value)
            return GREATER;
        else // if they are equal
            return EQUAL;
}

int ItemType::getValue() const
{
    return value;
}



#######################################
          ItemType.h
#######################################
#ifndef ITEMTYPE_H
#define ITEMTYPE_H
#include <iostream>


enum RelationType { LESS, GREATER, EQUAL};

class ItemType
{
public:
    ItemType();
    void Initialize(int number);
    int getValue() const;
    RelationType ComparedTo(ItemType);

private:
    int value;
};

#endif // ITEMTYPE_H



#######################################
            main.cpp
#######################################
#include <iostream>
#include "DoubleLists.h"
#include "ItemType.h"

using namespace std; 

int main(){
        
        DoubleLists d;
        ItemType i;

        i.Initialize(1);
        d.PutItem(i);

        i.Initialize(3);
        d.PutItem(i);

        i.Initialize(5);
        d.PutItem(i);

        i.Initialize(2);
        d.PutItem(i);

        // print the data starting from head of list
        d.PrintForward();
}



Please upvote, as i have given the exact answer as asked in question. Still in case of any concerns in code, let me know in comments. Thanks!