Question

In: Computer Science

Double Linked Lists: Implement the PutItem and DeleteItem function // ItemType.h #ifndef ITEMTYPE_H #define ITEMTYPE_H enum...

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

Solutions

Expert Solution

#######################################
     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!

venereology answered 1 year ago
Next > < Previous

Related Solutions

The goal of this assignment is to implement a set container using linked lists. Use the...
The goal of this assignment is to implement a set container using linked lists. Use the authors bag3.h and bag3.cpp as a basis for implementing your set container using linked lists. The authors bag3.h and bag3.cpp can be found here https://www.cs.colorado.edu/~main/chapter5/ Since you are using the authors bag3.h and bag3.cpp for your Set container implementation, make sure that you change the name of the class and constructors to reflect the set class. Additionally you will need to implement the follow...
In this Java program you will implement your own doubly linked lists. Implement the following operations...
In this Java program you will implement your own doubly linked lists. Implement the following operations that Java7 LinkedLists have. 1. public DList() This creates the empty list 2. public void addFirst(String element) adds the element to the front of the list 3. public void addLast(String element) adds the element to the end of the list 4. public String getFirst() 5. public String getLast() 6. public String removeLast() removes & returns the last element of the list. 7. public String...
In python i want to create a function. The function will take in two linked lists...
In python i want to create a function. The function will take in two linked lists as the parameters. If one is shorter than the other then the shorter will be the length. I want to take the values from both linked lists and turn them into tuples. I then want these tuples to be put into a new linked list. I want to return that linked list. I want to do this using recursion and no helper functions or...
#ifndef CCALC_HEADER #define CCALC_HEADER    class   CCalc { public:     // member functions     CCalc();     void    Add(double...
#ifndef CCALC_HEADER #define CCALC_HEADER    class   CCalc { public:     // member functions     CCalc();     void    Add(double value);     void    Clear();     void    Divide(double value);     double  GetValue() const;     void    Multiply(double value);     void    SetValue(double  newValue);     void    Subtract(double value);    private:     // data members     double  m_total; };    #endif // CCALC_HEADER int     main() {     CCalc       calculator;     char        choice;        // loop and let the user manipulate the calculator     do {         // display the menu and get the user selection         DisplayMenu();         cout <<...
In order to practice on Linked Lists, you will implement one from scratch which will allow...
In order to practice on Linked Lists, you will implement one from scratch which will allow you to examine how they work and explore their capabilities and limitations. You will build a doubly-circular linked list. In doubly linked lists, each node in the list has a pointer to the next node and the previous node. In circular linked lists, the tail node’s next pointer refers to the head and the head node’s previous pointer refers to the tail rather than...
Write a recursive function in C++ that creates a copy of an array of linked lists....
Write a recursive function in C++ that creates a copy of an array of linked lists. Assuming: struct node { int data; node * next; }; class arrayList { public: arrayList(); ~arrayList(); private: node ** head; int size; //(this can equal 10) }
EXTRA CHALLENGE: Could you implement a merge lists function which merges n lists in order? This...
EXTRA CHALLENGE: Could you implement a merge lists function which merges n lists in order? This function would accept a pointer to an array of n pointers, where each pointer refers to a list.
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of songs/artist pairs. Allow your user to add song / artist pairs to the list, remove songs (and associated artist) from the list and be sure to also write a function to print the list! Have fun! Make sure you show your implementation of the use of vectors in this lab (You can use them too ) You MUST modularize your code ( meaning, there...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array is based around having a fixed size per array creation, there is no logical limit on the ability of a linked list to grow. Physical limitations aside, linked lists are capable of growing largely without any limitations. To achieve this, they trade easier access to their individual elements. This is because linked lists have to be traversed from their root node to any node...
implement c++ Quicksort using median of 3 #ifndef QSORT_H #define QSORT_H #include #include using namespace std;...
implement c++ Quicksort using median of 3 #ifndef QSORT_H #define QSORT_H #include #include using namespace std; template T median_of_three(T& a, T& b, T& c, TComparator comparator) { } template size_t partition(vector& vec, TComparator& comparator, size_t low, size_t high) { // TODO: implement. } template void QuickSort(vector& vec, TComparator comparator,size_t low,size_t high) { if(comparator(low,high)){ size_t loc = partition(vec,comparator,low,high); QuickSort(vec,comparator,low,loc-1); QuickSort(vec,comparator,loc+1,high); } return; } template void quicksort(vector& vec, TComparator comparator) { // TODO: implement. size_t size = vec.size(); QuickSort(vec,comparator,0,size-1); } #endif test_case:...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT