Question

Double linked list implementation of PutItem function. How to fix my code to get desired output below:

Output:

2 5 8

#ifndef ITEMTYPE_H
#define ITEMTYPE_H

enum RelationType { LESS, GREATER, EQUAL};

class ItemType
{
public:
    ItemType();
    void setValue(int newValue);
    int getValue() const;
    RelationType ComparedTo(ItemType newItem);

private:
    int value;
};

#endif // ITEMTYPE_H

// ItemType.cpp

#include "ItemType.h"

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

void ItemType::setValue(int newValue)
{
    value = newValue;
}

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

RelationType ItemType::ComparedTo(ItemType newItem)
{
    if (value < newItem.value)
        return LESS;
    else if (value > newItem.value)
        return GREATER;
    else
        return EQUAL;
}

// Dlists.h

#ifndef DLISTS_H
#define DLISTS_H

#include "ItemType.h"

struct NodeType;

class Dlists
{
public:
    Dlists();
    void FindItem(NodeType *head, ItemType item, NodeType *& location, bool &found);
    void PutItem(ItemType item);
    void DeleteItem(ItemType item);
    void Print() const;

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

#endif // DLISTS_H

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

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

Dlists::Dlists()
{
    head = nullptr;
    currentPos = nullptr;
    length = 0;
}

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

void Dlists::FindItem(NodeType *head, ItemType item, NodeType *&location, bool &found)
{
    bool mts = true;
    location = head;
    found = false;

    while (mts && !found)
    {
        if(item.ComparedTo(location->info) == EQUAL)
            found = true;
        else if (item.ComparedTo(location->info) == LESS)
            mts = false;
        else // greater
        {
            location = location->next;
            mts = (location != nullptr);
        }
    }
}

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

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

    if (length == 0) // if list is empty
    {
        head = newNode;
        newNode->next = nullptr;
        newNode->prev = nullptr;
    }
    else if (length == 1)
    {
        if(item.ComparedTo(head->info) == LESS)
        {
            newNode->prev = nullptr;
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        else // if item is greater than the sole node
        {
            newNode->prev = head;
            newNode->next = nullptr;
            head->next = newNode;
        }
    }
    else // insertion point is in the middle
    {
        FindItem(head, item, location, found);
        newNode->prev = location->prev;
        newNode->next = location;
        (location->prev)->next = newNode;
        location->prev = newNode;
    }

    // increment the list
    length++;
}

// driver.cpp

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

int main()
{
    Dlists myList;
    ItemType item;

    // Adding 2 to the list
    item.setValue(2);
    myList.PutItem(item);

    // Adding 5 to the list
    item.setValue(5);
    myList.PutItem(item);

    // Adding 8 to the list
    item.setValue(8);
    myList.PutItem(item);

    // Printing the list
    myList.Print();

}

Answer 1

I have changed the Dlists.cpp implementation for FindItem() and PutItem() Functions,

FindItem function always returns the pointer next to which we need to put the new Item. If it returns nullptr, then our new node must be inserted to the head position else we Insert the new node to the next of location pointer. Corresponding changes to the code have been made. Good Luck!

#ifndef ITEMTYPE_H
#define ITEMTYPE_H

enum RelationType { LESS, GREATER, EQUAL};

class ItemType
{
public:
ItemType();
void setValue(int newValue);
int getValue() const;
RelationType ComparedTo(ItemType newItem);

private:
int value;
};

#endif // ITEMTYPE_H

// ItemType.cpp

#include "ItemType.h"

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

void ItemType::setValue(int newValue)
{
value = newValue;
}

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

RelationType ItemType::ComparedTo(ItemType newItem)
{
if (value < newItem.value)
return LESS;
else if (value > newItem.value)
return GREATER;
else
return EQUAL;
}

// Dlists.h

#ifndef DLISTS_H
#define DLISTS_H

#include "ItemType.h"

struct NodeType;

class Dlists
{
public:
Dlists();
void FindItem(NodeType *head, ItemType item, NodeType *& location, bool &found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void Print() const;

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

#endif // DLISTS_H

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

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

Dlists::Dlists()
{
head = nullptr;
currentPos = nullptr;
length = 0;
}

void Dlists::Print() const
{
NodeType *temp = head;
while (temp != nullptr)
{
cout << temp->info.getValue() << " ";
temp = temp->next;
}
}
//FindItem returns the pointer next to which we need to insert the other node
void Dlists::FindItem(NodeType *head, ItemType item, NodeType *&location, bool &found)
{
location = head;
NodeType* prev=nullptr;
found = false;

while (location!=nullptr && !found)
{
if(item.ComparedTo(location->info) == EQUAL)
found = true;
else if (item.ComparedTo(location->info) == LESS)
{
location=prev;
found=true;
}
else // greater
{
prev=location;
location = location->next;
}
}
if(location==nullptr) location=prev;
}

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

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

if (length == 0) // if list is empty
{
head = newNode;
newNode->next = nullptr;
newNode->prev = nullptr;
}
else if (length == 1)
{
if(item.ComparedTo(head->info) == LESS)
{
newNode->prev = nullptr;
newNode->next = head;
head->prev = newNode;
head = newNode;
}
else // if item is greater than the sole node
{
newNode->prev = head;
newNode->next = nullptr;
head->next = newNode;
}
}
else // insertion point is next to the location pointer
{
FindItem(head, item, location, found);
//FindItem always returns a pointer after which we need to insert the next node
if(location==nullptr){
newNode->next=head;
head->prev=newNode;
head=newNode;
}
else{
newNode->prev=location;
newNode->next=location->next;
location->next=newNode;
//cout<<location->info.getValue()<<endl;
}
}

// increment the list
length++;
}

// driver.cpp

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

int main()
{
Dlists myList;
ItemType item;

// Adding 2 to the list
item.setValue(2);
myList.PutItem(item);

// Adding 5 to the list
item.setValue(5);
myList.PutItem(item);

// Adding 8 to the list
item.setValue(8);
myList.PutItem(item);

// Printing the list
myList.Print();

}