Question

(The SortedLinkedList class template) Complete the

SortedLinkedList class template which is a doubly linked list and is implemented

with a header node and a tail node.

// SortedLinkedList.h

// SortedLinkedList.h

// A collection of data are stored in the list by ascending order

#ifndef SORTEDLIST_H

#define SORTEDLIST_H

using namespace std;

template <typename T>

class SortedList

{

private:

// The basic single linked list node type.

// Nested inside of SortedList.

struct NodeType

{

T data;

NodeType* next;

NodeType* prev;

NodeType(const T & d = T()):data(d)

{

next = nullptr;

prev = nullptr;

}

};

public:

class const_iterator

{

public:

// Public constructor for const_iterator.

const_iterator( )

{

current = nullptr;

}

const T & operator* ( ) const

{

return retrieve( );

}

const_iterator & operator++ ( )

{

current = current->next;

return *this;

}

const_iterator & operator-- ( )

{

current = current->prev;

return *this;

}

bool operator== ( const const_iterator & rhs ) const

{

return current == rhs.current;

}

bool operator!= ( const const_iterator & rhs ) const

{

return !( *this == rhs );

}

protected:

NodeType* current;

T & retrieve( ) const

{

return current->data;

}

const_iterator( NodeType* p )

{

current = p;

}

friend class SortedList<T>;

};

class iterator : public const_iterator

{

public:

iterator( )

{ }

T & operator* ( )

{

return const_iterator::retrieve( );

}

const T & operator* ( ) const

{

return const_iterator::operator*( );

}

iterator & operator++ ( )

{

this->current = this->current->next;

return *this;

}

iterator & operator-- ( )

{

this->current = this->current->prev;

return *this;

}

protected:

iterator( NodeType* p ) : const_iterator{ p }

{ }

friend class SortedList<T>;

};

public:

SortedList()

{

init( );

}

~SortedList()

{

clear( );

delete head;

delete tail;

}

iterator begin( )

{

return iterator( head->next );

}

const_iterator begin( ) const

{

return const_iterator( head->next );

}

// Return iterator representing endmarker of list.

// Mutator version is first, then accessor version.

iterator end( )

{

return iterator( tail );

}

const_iterator end( ) const

{

return const_iterator( tail );

}

// Return number of elements currently in the list.

int size( ) const

{

return theSize;

}

// Return true if the list is empty, false otherwise.

bool empty( ) const

{

return size( ) == 0;

}

void clear( )

{

while( !empty( ) )

iterator temp(erase(tail->prev));

}

// Find x in the list

// If x is found, return x position;

// If x is not found, return the position that x should be located.

iterator find(const T & x )

{

NodeType* ptr = head->next;

// add your code

}

// Insert x before itr.

iterator insert( iterator itr, const T & x )

{

NodeType* newptr = new NodeType(x);

NodeType* p = itr.current;

newptr->prev = p->prev;

newptr->next = p;

p->prev->next = newptr;

p->prev = newptr;

++theSize;

return iterator( newptr );

}

// Erase item at itr.

iterator erase( iterator itr )

{

NodeType* p = itr.current;

iterator retVal( p->next );

p->prev->next = p->next;

p->next->prev = p->prev;

delete p;

--theSize;

return retVal;

}

// add x in the sorted list, find the position that x should be

inserted, and then insert x

iterator add_item(const T & x )

{

// add your code

}

// remove x from the sorted list.

// If x is in the sorted list, find the position of x, and then

remove x.

// If x is not in the sorted list, return the position that x should

be located

iterator remove_item(const T & x )

{

//add your code

}

private:

int theSize;

NodeType* head;

NodeType* tail;

void init( )

{

theSize = 0;

head = new NodeType();

tail = new NodeType();

head->next = tail;

tail->prev = head;

}

};

#endif

1) Read the code carefully, and understand the nested classes const_iterator and

iterator.

2) Implement the member functions find, add_item, and remove_item based on

the corresponding comments. The three functions all return an iterator class.

3) Write an application program that

• creates an int type sorted list using SortedLinkedList class template.

• prompt the user to enter int values, and add these values to the sorted list, stop

adding the values when the user enter 0

• print the sorted list using iterator.

• prompt the user to enter int values to be removed, remove the values from the sorted

list, stop removing the values when the user enter 0.

• print the sorted list using iterator.

Three files should be submitted for this program question.

1) the file SortedLinkedList.h which contains the definition and

implementation of SortedLinkedList class template,

2) the application file a2q1.cpp containing main() function,

3) a script file a2q1result containing result.

Here are the sample runs:

Enter values in the sorted list:

3 6 2 9 5 1 8 7 4 0

The sorted list is:

1 2 3 4 5 6 7 8 9

The values to be removed:

4 6 2 8 0

The sorted list is:

1 3 5 7 9

...

Answer 1

As per the given details the program should be as follows :

iterated find(const T &x)

{

NodeType* ptr = head->next;

while (ptr != NULL)

    {

        if (ptr ->d== x)

            return ptr;

        current = ptr ->next;

    }

    return NULL;

}

=======================add_item

iterator add_item(const T &x)

{

struct Node** head_ref;

struct Node* newNode;

newNode->d = x;

struct Node* current;  

    // if list is empty

    if (*head_ref == NULL)

        *head_ref = newNode;

    // if the node is to be inserted at the beginning

    // of the doubly linked list

    else if ((*head_ref)->d >= newNode->d) {

        newNode->next = *head_ref;

        newNode->next->prev = newNode;

        *head_ref = newNode;

    }

    else {

        current = *head_ref;

        // locate the node after which the new node

        // is to be inserted

        while (current->next != NULL &&

               current->next->d < newNode->d)

            current = current->next;

        /* Make the appropriate links */

        newNode->next = current->next;

        // if the new node is not inserted

        // at the end of the list

        if (current->next != NULL)

            newNode->next->prev = newNode;

        current->next = newNode;

        newNode->prev = current;

    }

}

===================remove============

iterator remove_item(const T& x)

{

struct Node* current = head;

struct Node* next_next;

while (current->next != NULL)

    {

       /* Compare current node with next node */

       if (current->data == x)

       {

           /* The sequence of steps is important*/              

           next_next = current->next->next;

           free(current->next);

           current->next = next_next;

       }

       else /* This is tricky: only advance if no deletion */

       {

          current = current->next;

       }

    }

}

HOPE THIS MAY HELP YOU---

THANK YOU ……. PLEASE LIKE,IT WILL INCREASE MY SCORE,

HOPE YOU WILL ENCOURAGE ME…..