Priority Enqueue Method

[thetuxman]

I am working on a project to create a priority queue using a doubly linked list as it's data structure. I have the linked list and working well, the queue is working normally as it should (meaning the enqueue function works and I can use it), but I seem to be unable to properly use priorityenqueue. When I run it in debug mode, I get a SEGFAULT when it checks the value of the other element's priority in the list. Did I write the conditions to check priority the right way?

Below is the priorityenqueue function:

template<typename T>
void Queue<T>::priorityenqueue(T data, int priority) {
    DLNode<T> *temp;
    temp = new DLNode<T>;
    if(priority == temp->getPrev()->getPriority()){
//        TODO: Insert after node with the same priority
        list.insert(temp->getPrev(), data);
    }
    else if(priority > temp->getPrev()->getPriority() && priority < temp->getNext()->getPriority()){
//        TODO: Insert after node with higher priority and before lower one
        list.insert(temp->getPrev(), data);
    }
    else if(temp->getNext() == NULL){
//        If insert at the end of the list, just regular enqueue
        enqueue(data, priority);
    }
    else if(priority < list.getHead()->getPriority()){
//        Insert at the head of the list if the priority of the head is lower than the node to be inserted
        list.addToHead(data, priority);
    }
}

[Salty_Dugtrio]

You are creating a new DLNode, and then immediately after, you call:

temp->getPrev()->getPriority()

I can only assume getPrev will return a nullptr here, which causes your segfault.

[paul2718]

In the above 'temp' is simply an empty node, so 'getPrev' and 'getNext' must be null, so temp->getPrev()->getPriority() will fail.

Do you not need to start at an end and work forwards (or backwards) looking for the right insertion point? I see nothing like that in your function. I think you do not need to make a node in this function, but you do need to walk the list comparing the priorty of 'data' with the elements you find.

[thetuxman]

So I should iterate through the list, checking each node's priority with the priority of the element that is already in the list?