Thread: Accessing next entry in a queue.

No.

1) I've told you already that "system" is really a bad name for a variable.

2) You can't just free a node inside a linked list. You need to change the next-pointer of the previous node to point to the node after the node you want to remove.

3) You always return 1 so there isn't really a need for the return value at all.

Bye, Andreas

Originally Posted by peripatein

Furthermore, I'd now like to create a function the purpose of which is to delete from the Order's queue a specific order for the driver with the given name. May I write it thus? (Please note that the declarations themselves of the relevant struct and the function are a given)

Code:

typedef struct order{
    int orderID;
    int isSpecific;
    char specificDriver[101];
    struct order* next;
}Order;
int removeOrderByName(TaxiSystem * system, char * name){
    while (system->ordersQueue != NULL && !strcmp(system->ordersQueue->specificDriver, name))
        system->ordersQueue = system->ordersQueue->next;
    free(system);
    return 1;
}

Nope, this breaks all over the place (you haven't tested it, have you? ;-)

Perhaps you should step back a bit, and re-familiarize yourself with pointers and linked lists (via the relative chapters in your textbook, for example... or any other source).

However, I can't really understand why they are forcing you to use a queue implementation that is not utilizing a head and a tail pointer, which is the norm.

Anyway, here's a possible implementation of a function that removes a node from the drivers queue (which is a vanilla linked-list) based on the name.

Code:

int driversQ_delete_driver_by_name( Driver **driversQ, const char *name )
{
    Driver *cur = NULL;        /* current node */
    Driver *nxt = NULL;        /* node next to current */

    if ( !driversQ || !(*driversQ) || !name)
        return 0;

    cur = *driversQ;

    /* first node is treated as a special case */
    if ( 0 == strncmp( (*driversQ)->name, name, 101) ) {
        *driversQ = (*driversQ)->next;
        free( cur );
        return 1;
    }

    // walk the queue until either NULL or a node containing 'name' is found
    nxt = cur->next;
    while ( nxt && 0 != strncmp(nxt->name, name, 101) ) {
        cur = nxt;
        nxt = cur->next;
    }

    if ( !nxt )            // data was not found in list
        return 0;

    cur->next = nxt->next;
    free( nxt );

    return 1;
}

The tricky part is that we need 2 temporary pointers when walking the list, because if the desired node is found, then before freeing it we need to link its previous node with its next node. Since singly linked lists do not have prev pointers in their node, this approach is necessary.

It also means that we can treat the first node as a special case, in an effort to simplify the code.

A similar implementation could be something like the following...

Code:

int driversQ_delete_driver_by_name( Driver **driversQ, const char *name )
{
    Driver *cur = NULL;            /* current node */
    Driver *prv = NULL;            /* node before current */

    if ( !driversQ || !name )
        return 0;

    /* walk the queue until either NULL or a node containing 'name' is found */
    cur = *driversQ;
    while ( cur && 0 != strncmp(cur->name, name, 101) ) {
        prv = cur;
        cur = cur->next;
    }

    if ( !cur )                /* name was not found */
        return 0;

    if ( cur == *driversQ )            /* name was found in first node */
        *driversQ = (*driversQ)->next;
    else                    /* name was found elsewhere */
        prv->next = cur->next;

    free( cur );

    return 1;

which is pretty much the same thing with slightly different wording.

It should be easy to modify it for any of the queues in your exercise, or any other single linked list for that matter (but try them with several test cases, because I haven't).

PS. Actually, the Internet is full of code snippets and even full programs showing this kind of stuff.

That was highly discouraging, albeit am certain you didn't mean it to be. I misconstrue some particular elements in the logic involved in using structs and pointers, but that does NOT indicate that I "lack the fundamental knowledge of the basics needed to solve this exercise". And the fact that I am finding the exercise challenging, similarly, per se, is not an indication that the only means whereby I could solve it would be resorting to the textbook (or Google). I happen to find some of the comments on this forum in regard to my questions rather helpful and enlightening. A few of the comments greatly contributed to dispel several uncertainties and scruples. I strongly believe that via the appropriate guidance, in this forum, I shall be able to solve this exercise quite well and mostly by myself.

Originally Posted by peripatein

But why, how rather, does "next" have the address to the next Driver struct?

I'm assuming that the program that created the linked list of driver structs set all of the "next" pointers in all of the driver strurctures to the "next" driver structures while it was adding driver structures to the linked list.

@peripatein:

I felt bad, so here is a sample program implementing the basic queue operations on a vanilla singly linked list, plus the function that deletes a driver by name (it may contains bugs)...

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct driver{
    char           name[101];
    int            priority;
    struct driver  *next;
}Driver;

/* ------------------------------------------------------------------
 * Destroy the queue and set it to NULL
 */
void driversQ_free( Driver **driversQ )
{
    Driver *temp = NULL;

    if ( !driversQ )
        return;

    temp = *driversQ;
    while ( *driversQ ) {
        temp = (*driversQ)->next;
        free( *driversQ );
        *driversQ = temp;
    }

    return;
}

/* ------------------------------------------------------------------
 * Create a node with the specified data and insert it at the back of the queue.
 */
int driversQ_enqueue( Driver **driversQ, const char *name, int priority )
{
    Driver *node = NULL;

    if ( !driversQ )
        return 0;

    /* create & set a new node */
    node = malloc( sizeof(Driver) );
    if ( !node )
        return 0;
    strncpy( node->name, name, 101 );
    node->priority    = priority;
    node->next    = NULL;

    /* when queue is empty */
    if ( !(*driversQ) ) {
        *driversQ = node;
    }
    /* when queue already has at least one node */
    else {
        node->next = *driversQ;
        *driversQ = node;
    }

    return 1;
}

/* ------------------------------------------------------------------
 * Remove the front node of the queue.
 */
int driversQ_dequeue( Driver **driversQ )
{
    Driver *cur = NULL;
    Driver *nxt = NULL;

    if ( !driversQ )
        return 0;

    if ( !(*driversQ) )
        return 1;

    /* when queue has only one node */
    if ( !(*driversQ)->next ) {
        free( *driversQ );
        *driversQ = NULL;
        return 1;
    }

    /* walk the queue until last valid node */
    cur = *driversQ;
    nxt = (*driversQ)->next;
    while ( nxt->next ) {
        cur = nxt;
        nxt = nxt->next;
    }

    free(nxt);
    cur->next = NULL;

    return 1;
}

/* ------------------------------------------------------------------
 * Starting from the back of the queue, delete the
 * first node found to contain the specified name.
 */
int driversQ_delete_driver_by_name( Driver **driversQ, const char *name )
{
    Driver *cur = NULL;        /* current node */
    Driver *nxt = NULL;        /* node next to current */

    if ( !driversQ || !(*driversQ) || !name)
        return 0;

    cur = *driversQ;

    /* first node is treated as a special case */
    if ( 0 == strncmp( (*driversQ)->name, name, 101) ) {
        *driversQ = (*driversQ)->next;
        free( cur );
        return 1;
    }

    // walk the queue until either NULL or a node containing 'name' is found
    nxt = cur->next;
    while ( nxt && 0 != strncmp(nxt->name, name, 101) ) {
        cur = nxt;
        nxt = cur->next;
    }

    if ( !nxt )            // data was not found in list
        return 0;

    cur->next = nxt->next;
    free( nxt );

    return 1;
}

/* ------------------------------------------------------------------
 * Print all nodes of the queue, back to front.
 */
void driversQ_print( const Driver *driversQ )
{
    while ( driversQ ) {
        printf( "%s %d\n", driversQ->name, driversQ->priority );
        driversQ = driversQ->next;
    }
    putchar('\n');
}

/* ------------------------------------------------------------------
 * Program entry point.
 */
int main( void )
{
    int i;
    Driver *driversQ = NULL;
    const char *testname = "driver-1";

    driversQ_enqueue( &driversQ, "driver-1", 0 );
    driversQ_enqueue( &driversQ, "driver-2", 1 );
    driversQ_enqueue( &driversQ, "driver-3", 0 );
    driversQ_enqueue( &driversQ, "driver-4", 0 );

    driversQ_print( driversQ );

    if ( !driversQ_delete_driver_by_name(&driversQ, testname) ) {
        printf( "Driver %s was not found\n", testname );
    }
    else {
        driversQ_print( driversQ );
    }

    for (i=0; i < 3; i++) {
        puts( "Dequeueing..." );
        driversQ_dequeue( &driversQ );
        driversQ_print( driversQ );
    }

    driversQ_free( &driversQ );

    return 0;
}

EDIT:

The address of the queue's head pointer is passed to functions that may modify it (thus the double pointer declaration in the parameter list of those functions).

Thanks for the kind words, I'm glad I helped.

If I understand your last question correctly, all you have to do is to check if the head pointer of the queue is NULL or not. If it is, then the queue is empty. If not, then in order to remove the 1st node you can set a temporary pointer equal to the head pointer of the queue, then move the head pointer to the next node and finally free() the previously first node via the temporary pointer.

Code:

Driver *temp = driversQ;  // set temp pointer to queue's head
if ( driversQ ) {
    driversQ = driversQ->next;
    free( temp );
}

EDIT:

I forgot to mention that in the code I've showed in the previous post, the head pointer of the queue corresponds to the back of the queue. So the front of the queue is its last node. You could modify the code, so that the head pointer is the front of the queue instead (which is most common).

Depending on your implementation, you may need to remove either the 1st or the last node of the queue. The latter requires to traverse the queue until its last node, and carrying an extra pointer along the way, pointing to the previous node of the current one, so when the last node is reached you can set previous->next to NULL after freeing up the current node.

That's why implementing the queue form the beginning with a head and a tail pointer is the norm. Because this way, you do not need to traverse the whole queue in order to access its last item. And since there are no prev pointers in the nodes, it is better for the dequeue() operation to have the head pointer representing the front of the queue.


I hope it makes sense.