Minimum priority queue using Singly Linked LIst

Question

I have written this code for Priority Queue using Singly Linked List. I want to improve this code. Is there any other method to write program for priority queue?

#include <iostream>

template<typename T>
class priorityQueue
{
  struct Node
  {
    int priority;
    T info;
    Node* next;
    Node(T item) : info(item), next(nullptr) {}
  };
  Node* front;

public:
  priorityQueue() : front(nullptr) {}
  ~priorityQueue()
  {
    Node *tmp = nullptr;
    while (front){
      tmp   = front;
      front = front->next;
      delete tmp;
    }
  front = nullptr;
  }

  priorityQueue(const priorityQueue<T> & pq)     = delete;
  priorityQueue& operator=(priorityQueue const&) = delete;

  void insert(T item, int priority)
  {
    Node* tmp;
    Node* node     = new Node(item);
    node->priority = priority;

    if(front == nullptr || priority < front->priority)
    {
      node->next = front;
      front = node;
    }
    else
    {
      tmp = front;
      while(tmp->next != nullptr && tmp->next->priority <= priority)
        tmp = tmp->next;

      node->next  = tmp->next;
      tmp->next   = node;
    }
  }

  void deleteItem(T item)
  {
    Node* find = search(item);
    Node* node = front;
    if(node == find)
      front = node->next;
    else
    {
      while(find != nullptr)
      {
        if(node->next == find)
        {
          node->next = find->next;
          delete find;
          return;
        }
        node = node->next;
      }
    }
  }

  friend std::ostream & operator<<(std::ostream & os, const priorityQueue<T> & pq)
  {
      pq.display(os);
      return os;
  }

private:
  Node *search(T item)
  {
    Node *node = front;
    while(node != nullptr)
    {
    if(node->info == item)
      return node;
    node = node->next;
    }
    std::cerr << "No such element in the list \n";
    return nullptr;
   }

   void display(std::ostream& out = std::cout) const
   {
     Node *node = front;
     out << "\nItem \tPriority \n";
     while(node != nullptr)
     {
       out << node->info << "\t" << node->priority <<"\n";
       node = node->next;
     }
    }
};

int main()
{
  priorityQueue<std::string> pq1;
  pq1.insert("code", 1);
  pq1.insert("sleep", 3);
  pq1.insert("food", 2);
  pq1.insert("date", 4);
  std::cout << pq1;
}

janos · Accepted Answer · 2017-09-02 11:27:26Z

2

Data structures

Although the name "priority queue" is technically correct, I find it a bit misleading, because priority queues are usually implemented using a heap data structure, with insert and find operations in \$O(\log n)\$ time. Your implementation is practically a sorted linked list, with insert and find operations in \$O(n)\$ time. I'd clarify as "naive priority queue" to avoid confusion.

Memory leak

Watch out for memory leaks. When deleting the first item, the deleteItem function simply advances the pointer of front, without actually deleting the item, leaving allocated memory behind.

Performance

deleteItem is inefficient, because it iterates to the node to delete twice: once to find the node to delete, and then one more time to actually delete it.

edited Sep 2, 2017 at 11:27

answered Sep 2, 2017 at 10:45

janos

113k15 gold badges154 silver badges396 bronze badges

\$\begingroup\$ The name is correct. It is still a priority queue. Albeit a slow one. \$\endgroup\$

Emily L.
– Emily L.

2017-09-02 11:26:38 +00:00
Commented Sep 2, 2017 at 11:26

Add a comment |

Harald Scheirich · Accepted Answer · 2017-09-02 11:52:56Z

Pass by Reference

Be more conscious of passing by value and passing by reference, all your functions take objects of type T as value parameters, in most cases that should be const T&. Otherwise you will end up making a copy for every function call and the Node constructor.

API

There are no functions to get and/or remove the first item in the list. If this is supposed to be a priority queue i would at least want to be able to retrieve or pop the first item in the list.

Every item is uniquely identified by itself and the priority, but deletion only uses the item as an identifier, if I add two items e.g.

queue.add("sleep", 1);
queue.add("sleep", 3);

You would only be able to delete the first item

You have insert but deleteItem, using Item in the member function name is unnecessary.

Bad constructor

priority is not initialized in the constructor, if you forget to assign it, it will be uninitialized. Additionally it takes T in its constructor but the priority has to be set "manually" this is not a good pattern, if you pass it in the constructor your constructor indicates that both of these items are necessary to make a valid Node object.

Blocks without braces

This borders into taste issues, i personally try not to use blocks without braces e.g.

if (value)
  return true;

It is too easy to forget that this block is not extended by just keeping the indentation and just add another line to this 'block'. This can lead to bugs that are hard to find

if (value)
  othervalue = 5;
  return true;

This comes into play once you have code that has been sitting around for a bit, I prefer either just using the braces for everything (a lot of code styling tools will do this substitution for you anyway), or only using this if the whole statement fits in one line.

if (value) {
  return true;
}

if (value) return true;

Stack Exchange Network

Minimum priority queue using Singly Linked LIst

2 Answers 2

Data structures

Memory leak

Performance

Pass by Reference

API

Bad constructor

Blocks without braces

You must log in to answer this question.

Hot Network Questions

Minimum priority queue using Singly Linked LIst

2 Answers 2

Data structures

Memory leak

Performance

Pass by Reference

API

Bad constructor

Blocks without braces

You must log in to answer this question.

Related

Hot Network Questions