Linked list: Problem with insert, remove and sort. Here is a LinkedList. I have

Question

Linked list: Problem with insert, remove and sort.

Here is a LinkedList. I have made the implementations, but i belive there are some problems with Insert, Remove and Sort.

Any help and explanation would be appreciated.

Thankyou in advance.

template<typename T>
class Queue
{
public:

   // PRECONDITION: -
   // POSTCONDITION: The queue is empty
   Queue()
   {
       head = nullptr; // Empty list with no objects
   }

   // PRECONDITION: value > 0
   // POSTCONDITION: Object which contains (data,value) is inserted, and sorted into the linked list.
  
   // If the list is empty, object of node is inserted First.
   // If the list is not empty, object is inserted according to the value.
   // Example: i have this list: ('A',5)->('B',7)... and i want to insert ('A',3)... new order should be ('A',3)->('A',5)->('B',7)

   void insert(const T& data, int value)
   {
       if (value > 0)
       {
           Node<T>* newNode = new Node<T>(data, value);
           if (head == nullptr) // if the list is empty
           {
               head = newNode; // head points at newNode
           }
           else // If the list is not empty.
           {
               newNode->next = head;
               head = newNode;
           }
       }
   }

   // PRECONDITION: -
   // POSTCONDITION: object which contains the value "data" is removed and deallokated using the destructor.
   void remove(const T& data)
   {
       Node<T>* delPtr = head;
       if (delPtr == nullptr) // If the list is empty, do nothing
       {
           return;
       }
       while (delPtr != nullptr)
       {
           Node<T>* buffer = delPtr->next;
           if (delPtr->data == data)
           {
               delPtr = delPtr->next;
               delete delPtr;
           }
           delPtr = buffer;
       }
   }

   void sort()
   {
       // Sort Linked List.
       // Lowest value is infront and Highest value is last.
   }

   // PRECONDITION: -
   // POSTCONDITION: Tells wether or not the list is empty
   bool isEmpty() const
   {
       return (head == nullptr);
   }

   ~Queue()
   {
       while (!isEmpty()) remove(head->data);
   }

private:
   Node<T>* head;
};

Explanation / Answer

void insert(const T& data, int value)
    {
        if (value > 0)
        {
            Node<T>* newNode = new Node<T>(data, value);
            newNode->next = head;
            head = newNode;
        }
    }

void remove(const T& data)
    {
        Node<T>* delPtr = head;
        if (delPtr == nullptr) // If the list is empty, do nothing
        {
            return;
        }
   if (head -> data == data)
   {
       head = head -> next;
       delete delPtr;
   }

        while (delPtr->next != nullptr)
        {
            Node<T>* buffer = delPtr->next;
            if (buffer->data == data)
            {
                delPtr->next = buffer->next;
                delete buffer;
            }
        }
    }

void sort()
    {
   Node<T>* tmpHead = head;
   Node<T>* tmp;
   Node<T>* last = nullptr;
        while (tmpHead!=last) {
       tmp = tmpHead;
       while (tmp->next!= last) {
           if(tmp->data > tmp->next->data) {
               T storage = tmp->data;
               tmp->data = tmp->next->data;
               tmp->next->data = storage;
           }
       } //end of while(tmp->next!=last)
       last = tmp;
   }//end of while (tmpHead!=last)
}

I hopr this helps you and resolves all your issues. If you have any querry, please feel free to comment below,

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.