Answer to Question #220780 in C++ for Talal Alshumais

Question

For this final assignment, you will use Qt to create a GUI version of the templated LinkedList you made for assignment 9.  

You may design your window as you wish, but it needs to have the minimum functionality:

• Radio buttons to select between the different types of data your linked list will store(int, double, string, Rational, Date, Complex)
• A button to display the contents of the linked list
• The ability to display only a portion of the linked list
• Buttons to push_back, push_front, pop_front, insert_sorted
• Insert button that can insert an element at any spot in the list (have to define a new function in linked list class)
• Button to perform select_sort
• Button to remove_duplicates
• Should have the ability to make a copy of a list and be able to retain and modify both copies (may make multiple copies).
• Be able to modify any of the lists without losing any information going from one list to the other.
• You may use vectors as long as you use your own vector class, not the one provided with C++/QtCreator.

Answer 1

//linkedlist.h

#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED

using namespace std;

#include "listEmpty.h"

template<typename E>
struct Node
{
    E data; //data  
    Node *next;
    Node( E data ) : data(data), next(0) {}
};

template<typename E>
class LinkedList
{
private:
    Node *head; //head pointer
    Node *tail; //tail pointer
public:

    class Iterator
    {
    private:
        Node *current;
    public:
        Iterator();
        Iterator(Node *ptr);

        int operator*();
        Iterator operator++();
        bool operator==(const Iterator& right) const;
        bool operator!=(const Iterator& right) const;
    };

    LinkedList();
    LinkedList(const LinkedList& source);
    ~LinkedList();
    
    LinkedList & operator=( const LinkedList& source );
    void display() const;
    void push_front( const E& value );
    void push_back( const E& value );
    void pop_front() throw(ListEmpty);
    const E& front() const throw(ListEmpty);
    const E& back() const throw(ListEmpty);
    void clear();
    void select_sort();
    void insert_sorted( const E& value );
    void remove_duplicates();
    Iterator begin();
    Iterator end();

    int length() const;
    int sum() const;
    bool isEmpty() const;

private:
    int getLength(Node *ptr) const;
    int getSum(Node *ptr) const;
};

template<typename E>
LinkedList::Iterator::Iterator():current(0){}

template<typename E>
LinkedList::Iterator::Iterator(Node *ptr):current(ptr){}

template<typename E>
int LinkedList::Iterator::operator*()
{return this->current->data;}

template<typename E>
typename LinkedList::Iterator LinkedList::Iterator::operator++()
{
    current = current->next;
    return *this;
}

template<typename E>
bool LinkedList::Iterator::operator==(const Iterator& right) const
{return (this->current == right.current);}

template<typename E>
bool LinkedList::Iterator::operator!=(const Iterator& right) const
{return (this->current != right.current);}

template<typename E>
LinkedList::LinkedList():head(0),tail(0) {}

template<typename E>
LinkedList::LinkedList(const LinkedList& source)
{
    Node *newNode; //newNode pointer
    Node *current; //current pointer
    //set head to NULL
    head = NULL;

    if(this != &source)
    {
        //if the new list is NULL
        if(source.head == NULL)
        {
            head = NULL;
            tail = NULL;
        } else {
            //current points to the list to be copied
            current = source.head;
            //copy the head node
            head = new Node(0);
            head->data = current->data;
            head->next = NULL;
            
            tail = head;
        
            current = current->next;
            
            //while loop to copy the remaining list
            while(current != NULL) {
                newNode = new Node(0);
                newNode->data = current->data;
                newNode->next = NULL;
            
                tail->next = newNode;
                tail = newNode;
                
                current = current->next;
            }
        }
    }
}

template<typename E>
LinkedList::~LinkedList()
{
    while (head != 0) { pop_front(); }
}

template<typename E>
LinkedList & LinkedList::operator=( const LinkedList& source )
{
    Node *newNode; //new Node
    Node *current; //current Node

    if(this != &source)
    {
        //if the new list is NULL
        if(source.head == NULL)
        {
            head = NULL;
            tail = NULL;
        }
        else
        {
            //current points to the list to be copied
            current = source.head;
            
            //copy the head node
            head = new Node(0);
            head->data = current->data;
            head->next = NULL;
            
            tail = head;
            
            current = current->next;
        
            //while loop to copy the remaining list
            while(current != NULL)
            {
                newNode = new Node(0);
                newNode->data = current->data;
                newNode->next = NULL;
                
                tail->next = newNode;
                tail = newNode;
                
                current = current->next;
            }
        }
    }


    return *this;
}

template<typename E>
void LinkedList::display() const
{
if (head != 0)
   {
       for (Node *curr = head; curr != 0; curr = curr->next)
       {
           cout << curr->data;
           //only output a space if its not the last node
           if (curr != tail)
           {
               cout << ' ';
           }
       }
   }
}


template
void LinkedList::push_front( const E& value )
{
Node* temp; //the temporary pointer

   //initializing
   temp = new Node(value);
   temp->next = head;
   head = temp;

   //check if there is only 1 node, if so point tail to node
   if (tail == 0)
   {
       tail = temp;
   }
}


template
void LinkedList::push_back( const E& value )
{
Node* temp; //the temporary pointer

   //initializing
   temp = new Node(value);

   if(head != 0)
{
tail->next = temp;
tail = temp;
}
else
{
head = temp;
tail = temp;
}
}


template
void LinkedList::pop_front() throw(ListEmpty)
{

try
{
if(head == 0)
throw ListEmpty();
else
{
Node* temp; //temp pointer

temp = head; //set head to the temp
head = head->next; //head equal to next pointer
tail = NULL;

//delete temporary pointer
delete temp;
}
}
catch(ListEmpty)
{
throw;
}

}


template
const E& LinkedList::front() const throw(ListEmpty)
{
try
{
if(head == 0)
throw ListEmpty();
else
return head->data;
}
catch(ListEmpty)
{
throw;
}

}


template
const E& LinkedList::back() const throw(ListEmpty)
{
try
{
if(head == 0)
throw ListEmpty();
else
return tail->data;
}
catch(ListEmpty)
{
throw;
}
}

template
void LinkedList::clear()
{
Node *temp;
while(head != 0)
{
temp = head;

head = head->next;
delete temp;
}
}


template
void LinkedList::select_sort()
{
int size; //size of the current list
   Node* large; //pointer to the largest node
   Node* prevLarge; //pointer to the previous node before the largest node
   Node* end; //pointer to correct position in list for appending
   int pos; //count position
   int count; //controls entire seperator

   //initializing
   size = 0;
   large = 0;
   prevLarge = 0;
   end = 0;
   pos = 0;
   count = 0;

   //get the size of the current list
   for (Node *curr = head; curr != 0; curr = curr->next)
   {
       size++;
   }


   while (count < (size - 1))
   {
       //set largest node to default (head)
       large = head;
       //set end to default
       end = head;
       //node before largest one
       prevLarge = head;

       //reset pos
       pos = 0;

       //finds largest node
       for (Node *curr = head;pos < (size - count);curr = curr->next)
       {
           if (curr->data > large->data)
           {
               large = curr;
           }
           pos++;
       }

       pos = 1;

       //finds node before largest node
       for (Node *curr = head;pos < (size - count);curr = curr->next)
       {
           if (curr->next == large)
           {
               prevLarge = curr;
           }
           pos++;
       }

       pos = 0;

       //chooses correct position in list for appending
       for (Node * curr = head;pos < (size - count);curr = curr->next)
       {
           end = curr;
           pos++;
       }

       if (large != end)
       {
           //if appending to the end
           if (count == 0)
           {
               Node* newNode = new Node(large->data);
               tail->next = newNode;
               tail = newNode;

               //delete old node if deleting first node
               if (large == head)
               {
                   pop_front();
               }
               //deleting a middle node
               else
               {
                   Node* temp = large;
                   prevLarge->next = large->next;
                   large = 0;
                   delete temp;
               }
           }
           //if appending to anything else other than the end
           else
           {
               //create a new node with the data
               Node* newNode = new Node(large->data);

               //appends new node
               newNode->next = end->next;
               end->next = newNode;

               //delete old node if deleting first node
               if (large == head)
               {
                   pop_front();
               }
               //deleting a middle node
               else
               {
                   Node* temp = large;
                   prevLarge->next = large->next;
                   large = 0;
                   delete temp;
               }
           }
       }
       count++;
   }
}


template
void LinkedList::insert_sorted( const E& value )
{
bool notFound = true; //return true or false;
   Node* newNode = new Node(value); //the new node with the value

   //if list is empty, insert new value
   if (head == 0)
   {
       head = newNode;
       tail = newNode;
   }
   //if not, insert value in right position
   else
   {
       for (Node *curr = head;curr != 0 && curr != tail && notFound;
           curr = curr->next)
       {
           //check if value is the smallest
           if (value < curr->data)
           {
               push_front(value);
               notFound = false;
           }
           //if value is found, insert node
           else if (curr->next->data >= value)
           {
               newNode->next = curr->next;
               curr->next= newNode;
               notFound = false;
           }
       }
       //if pos still not found, append value at the end
       if (notFound)
       {
           tail->next = newNode;
           tail = newNode;
       }
   }
}

template
void LinkedList::remove_duplicates()
{
//terminte if list is empty
   if (head == 0)
return;


   Node* dupe = 0; //holds possible deplicate of current node
   Node* prev = head; //points to the previous node before the dupe node

   for (Node *curr = head; curr != 0; curr = curr->next)
   {
       dupe = curr->next;
       prev = curr;
       while (dupe != 0)
       {
           if (curr->data == dupe->data)
           {
               //holds temporary node
               Node* temp = dupe;

               //if the duplicate is the last element, fix tail
               if (dupe == tail)
               {
                   dupe = 0;
                   prev->next = 0;
                   tail = prev;
                   delete temp;
               }
               else
               {
                   prev->next = dupe->next;
                   dupe = dupe->next;
                   delete temp;
               }
           }
           else
           {
               dupe = dupe->next;
               prev = prev->next;
           }
       }
   }
}

template
typename LinkedList::Iterator LinkedList::begin()
{
Iterator temp(head); //iterator pointer

return temp;
}


template
typename LinkedList::Iterator LinkedList::end()
{
Iterator temp(NULL); //iterator pointer

return temp;
}

template
int LinkedList::length() const
{
return getLength(head);
}


template
int LinkedList::getLength(Node *ptr) const
{

if(ptr!= NULL)
{
//get next node
ptr = ptr->next;

//return length of the list
return 1+getLength(ptr);
}
else
return 0;
}
template
int LinkedList::sum() const
{
return getSum(head);
}


template
int LinkedList::getSum(Node *ptr) const
{

if(ptr!= NULL)
{

//return the sum of all of the elements
return ptr->data + getSum(ptr->next);
}
else
return 0;
}

template
bool LinkedList::isEmpty() const
{
if(head == 0)
return true;
else
return false;
}


#endif // LINKEDLIST_H_INCLUDED

listEmpty.h

#ifndef LISTEMPTY_H_INCLUDED
#define LISTEMPTY_H_INCLUDED
#include
#include
using namespace std;

class ListEmpty
{
public:
ListEmpty()
{
message = "The list is empty.";
}

string what()
{
return message;
}
private:
string message;
};

#endif // LISTEMPTY_H_INCLUDED