Priority Queue with Doubly Linked List Insertion

Question

I am implementing a priority queue waitlist using a doubly linked list. My method creates a new node (priority and student id). Depending on the node priority the method will sort the node into the queue.

what I get is                                what I should get

Waitlisted:             109 in 2123      |   Waitlisted:             109 in 2123
Current waitlist:       109              |   Current waitlist:       109
                                         |
Waitlisted:             105 in 2123      |   Waitlisted:             105 in 2123
Current waitlist:       105              |   Current waitlist:       105 109
                                         |
Waitlisted:             108 in 2123      |   Waitlisted:             108 in 2123
Current waitlist:       109 105          |   Current waitlist:       105 108 109
                                         |
Waitlisted:             106 in 2123      |   Waitlisted:             106 in 2123
Current waitlist:       106              |   Current waitlist:       105 106 108 109
                                         |
Waitlisted:             107 in 2123      |   Waitlisted:             107 in 2123
Current waitlist:       109 106          |   Current waitlist:       105 106 107 108 109

I am able to insert a new node when the queue is empty on the first loop. Starting from the 2nd run the return values of the queue are wrong.

Code

void enqueue( PQNode** ppFront, WaitlistEntry info ){
    /* create a new node to store the info */
    PQNode *temp = (PQNode*)malloc(sizeof(PQNode)); //create a new node to store the info
    temp->info = info;
    temp->pNext = NULL;
    temp->pPrev = NULL;

    /* check if the LL is empty and add the new node to the front if it is */
    if(*ppFront == NULL){
        *ppFront = temp;
        return;
    }

    /* check if the new node should come before the first node in the LL */
    if(temp->info.iPriority > (*ppFront)->info.iPriority){
        temp->pNext = *ppFront;
        (*ppFront)->pPrev = temp;
        *ppFront = temp;
        return;
    }   

    /* walk back through the previous nodes in the LL until the correct insertion point is found */
    /* remember to also check whether the previous node is NULL */
    while((*ppFront)->pNext != NULL && temp->info.iPriority <= (*ppFront)->info.iPriority){
        *ppFront = (*ppFront)->pNext;
    }

    /* insert the new node into the place you found with your loop */
    /* note you may need a special case for when the previous node is NULL */
    if((*ppFront)->pNext == NULL){
        (*ppFront)->pNext = temp;
        temp->pPrev = *ppFront;
        return;
    }
    temp->pPrev = *ppFront;
    temp->pNext = (*ppFront)->pNext;
    (*ppFront)->pNext->pPrev = temp;
    (*ppFront)->pNext = temp;
    return;
}

Structs

typedef struct{
    int iPriority;          /* Priority of the student to be enrolled */
    int iStudentID;         /* ID of the student */
} WaitlistEntry;

typedef struct PQNode {
    WaitlistEntry info;     /* WaitlistEntry stored in the node (sorted with largest priority first) */
    struct PQNode* pNext;   /* Pointer to next node in the LL */
    struct PQNode* pPrev;   /* Pointer to previous node in the LL */
} PQNode;

typedef struct{
    int iCourseNumber;      /* Course number of the course */
    int* iStudentIDs;       /* Array of IDs of students enrolled in the course */
    int iNumEnrolled;       /* Number of Students currently enrolled in course */
    int iMaxEnrolled;       /* Max number of Students that can enroll in the course */
    PQNode* pFront;         /* Priority queue representing the waitlist for the course */
} Course;

I've managed to fix up the code some, but I'm still stuck.

There is an error in the enqueue logic, but it is presumed that there is an error in the display function without relation to it. — BLUEPIXY
Breaking things into smaller functions can help you debug your logic when things like this occur. For example, when I deal with doubly linked lists, I tend to rely on a set of connect(prev, current, next) and disconnect(prev, next) functions because the logic can be confusing when dealing with NULL lists, NULL prev/next pointers, etc. Similarly, finding the insertion point can be put into its own function as well. See this paste for an example of what I'm talking about. The main functions to look at are FindPriorityEnd and Enqueue. — user539810

Pablo Pablo · Accepted Answer · 2017-07-04T01:56:53

As BLUEPIXY mentioned, the last bit of the function is a bit wrong (//edit you've changed your code in the meantime, I'm referring to your original code). When you go through the list in the while block, and then you realize that curr is the tail, you fail to check whether you got there because either temps priority is greater than the tail's or you've reached the end of the list and temp should become the new tail.

Also, the very last part you are inserting temp at the wrong side.

The last part of your code should like this

// edit posting the whole code, I only changed the last bit of your function, and the parameters for enqueue, much easier to write test code for this.

void print_queue(PQNode *queue)
{
    if(queue == NULL)
    {
        puts("empty queue");
        return;
    }

    for(;;)
    {
        printf("%d (priority %d)", queue->info.iStudentID, queue->info.iPriority);
        queue = queue->pNext;

        if(queue == NULL)
        {
            puts("");
            return;
        }

        printf(" <--> ");
    }
}


void enqueue( PQNode** ppFront, int id, int prio ){
    /* create a new node to store the info */
    PQNode *temp = (PQNode*)malloc(sizeof(PQNode)); //create a new node to store the info
    temp->info.iStudentID = id;
    temp->info.iPriority = prio;
    temp->pNext = NULL;
    temp->pPrev = NULL;
    PQNode *curr = *ppFront;


    /* check if the LL is empty and add the new node to the front if it is */
    if(curr == NULL){
        *ppFront = temp;
        return;
    }

    /* check if the new node should come before the first node in the LL */
    if(temp->info.iPriority > curr->info.iPriority){
        temp->pNext = *ppFront;
        (*ppFront)->pPrev = temp;
        *ppFront = temp;
        return;
    }   

    /* walk back through the previous nodes in the LL until the correct insertion point is found */
    /* remember to also check whether the previous node is NULL */
    while(curr->pNext != NULL && temp->info.iPriority <= curr->info.iPriority){
        curr = curr->pNext;
    }



    /* insert the new node into the place you found with your loop */
    /* note you may need a special case for when the previous node is NULL */
    if(curr->pNext == NULL){
        // we don't know whether the while stopped because it reached the
        // final node or the priority was greater, we have to check it
        if(temp->info.iPriority <= curr->info.iPriority)
        {
            // the priority is smaller, temp should be the tail
            curr->pNext = temp;
            temp->pPrev = curr;
            return;
        } else {
            // the priority is bigger, curr should the the tail
            // this case is handled by the next section
        }
    }

    temp->pPrev = curr->pPrev;
    temp->pNext = curr;
    curr->pPrev->pNext = temp;
    curr->pPrev = temp;
}

int main(void)
{
    PQNode *queue = NULL;

    enqueue(&queue, 109, 10);
    enqueue(&queue, 105, 40);
    enqueue(&queue, 108, 20);
    enqueue(&queue, 110, 30);
    enqueue(&queue, 911, 11);
    enqueue(&queue, 219, 25);

    print_queue(queue);

    return 0;
}

I get

105 (priority 40) <--> 110 (priority 30) <--> 219 (priority 25) <--> 108 (priority 20) <--> 911 (priority 11) <--> 109 (priority 10)

Priority Queue with Doubly Linked List Insertion

1 Answers