Im trying to implement queue with a linked list i think i have the enqueue function correct but im having problems with the dequeue.
I can get it to delete the first number but then the rest of the list is empty can someone point me in the right direction?

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

//Structure node
struct _node
{
    int num;
    struct _node * next;
};
//type definitions
typedef struct _node node;
typedef node * link;

//Structure list
struct _list
{
    link top;//points to node structure
    link bottom;
};
//type definition
typedef struct _list list;
typedef list * linklist;//linklist points to list structure

//buildNode function returns and initialized node
link buildNode()
{
    link node;
    node = malloc(sizeof(node));
    if(node == NULL)
    {
        printf("Malloc Failed. Exiting.\n");
        exit(1);
    }
    node->next = NULL;
    return node;
}

//enqueue function adds and element to the list
void enqueue(linklist listI, int num)
{
    link node;
    link tmp;
    node = buildNode();
    node->num = num;

    if(listI->top == NULL && listI->bottom == NULL)//If the top item in the list is null
    {
        listI->top = node;//set the top item in the list equal to node
        listI->bottom = node;
    }
    else//if the top item in the list is not null
    {
        tmp = listI->bottom;//set tmp equal to the top item in the list

        while(tmp->next != NULL)//while the next item in the tmp list does not equal null
        {
            tmp = tmp->next;//set tmp equal to the next item in the tmp list
        }
        tmp->next = node;//set the next item in the tmp list equal to node
    }
}

//dequeue function deletes the top item from the list
int dequeue(linklist listI)
{
    link tmp;
    link prev;
    int num = 0;

    if(listI->top == NULL && listI->bottom == NULL)
    {
        printf("Trying to dequeue from an empty list. Exiting.\n");
        exit(1);
    }
    else if(listI->top == listI->bottom)
    {
        tmp = listI->top;

        num = tmp->num;
        free(tmp);
        listI->top = NULL;
        listI->bottom = NULL;
    }
    else
    {
        tmp = listI->top;
        prev = listI->top;
        while(tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        while(prev->next != tmp)
        {
            prev = prev->next;
        }
        num = tmp->num;
        prev->next = NULL;
        free(tmp);
    }
    return num;
}

//printList function prints out the items in the list
void printList(linklist listI)
{
    link tmp = listI->top;

    if(tmp == NULL)
    {

    }
    else
    {
        while(tmp != NULL)
        {
            printf("%d\n",tmp->num);
            tmp = tmp->next;
        }
    }
}

//main
int main(void)
{
    int num = 0;
    linklist listA;
    listA = malloc(sizeof(list));

    enqueue(listA, 5);
    enqueue(listA, 1);
    enqueue(listA, 10);
    enqueue(listA, 40);
    printList(listA);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    //num = dequeue(listA);
    //printf("dequeue Node - Num: %d\n",num);
    enqueue(listA, 33);
    printList(listA);

    return 0;
}

Your dequeue logic has two major problems:

  1. It does not take into account updating the bottom node.

  2. Wherever the node is deleted, the list is terminated with NULL rather than maintaining the structure if there are subsequent nodes.

This is a basic single linked list deletion, so you might be well served by boning up on linked lists in general.

Well i figured it out, but now i have another problem. The code will run fun when i compile it in linux but when i compile it with codeblocks or visual studio i throws an error in the print function. it would be line 116.

Anyone know what is causing this?

//Brandon McBride
//queue
//3-25-2015


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

//Structure node
struct _node
{
    int num;
    struct _node * next;
};
//type definitions
typedef struct _node node;
typedef node * link;

//Structure list
struct _list
{
    link top;//points to node structure
    link bottom;
};
//type definition
typedef struct _list list;
typedef list * linklist;//linklist points to list structure

//buildNode function returns and initialized node
link buildNode()
{
    link node;
    node = malloc(sizeof(node));
    if(node == NULL)
    {
        printf("Malloc Failed. Exiting.\n");
        exit(1);
    }
    node->next = NULL;
    return node;
}

//enqueue function adds and element to the list
void enqueue(linklist listI, int num)
{
    link node;
    link tmp;
    node = buildNode();
    node->num = num;

    if(listI->top == NULL && listI->bottom == NULL)//If the top item in the list is null
    {
        listI->top = node;//set the top item in the list equal to node
        listI->bottom = node;

    }
    else//if the top item in the list is not null
    {
        tmp = listI->bottom;

        listI->bottom->next = node;

        tmp->next = node;//set the next item in the tmp list equal to node
        listI->bottom = node;
    }
}

//dequeue function deletes the top item from the list
int dequeue(linklist listI)
{
    link tmp;
    link prev;
    int num = 0;

    if(listI->top == NULL)
    {
        printf("Trying to dequeue from an empty list. Exiting.\n");
        exit(1);
    }
    else if(listI->top == listI->bottom)
    {
        tmp = listI->top;
        num = tmp->num;

        free(tmp);

        listI->top = NULL;
        listI->bottom = NULL;
    }
    else
    {

        tmp = listI->top;
        num = tmp->num;
        listI->top = listI->top->next;

        free(tmp);

    }
    return num;
}
//printList function prints out the items in the list
void printList(linklist listI)
{
    link tmp = listI->top;

    if(tmp == NULL)
    {

    }
    else
    {
        while(tmp != NULL)
        {
            printf("%d\n",tmp->num);
            tmp = tmp->next;
        }
    }
}

//main
int main(void)
{
    int num = 0;
    linklist listA;
    listA = malloc(sizeof(list));

    enqueue(listA, 5);
    enqueue(listA, 1);
    enqueue(listA, 10);
    enqueue(listA, 40);
    printList(listA);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    num = dequeue(listA);
    printf("dequeue Node - Num: %d\n",num);
    //num = dequeue(listA);
    //printf("dequeue Node - Num: %d\n",num);
    enqueue(listA, 33);
    printList(listA);

    return 0;
}

Edited 1 Year Ago by brandon66

It works okay for me in Visual Studio after fixing two bugs. First you never initialize listA in main, so the top and bottom pointers are unintialized. A quick fix is this:

listA = malloc(sizeof(list));
listA->top = listA->bottom = NULL;

Second, and a more subtle problem is in buildNode. The logic is fine, but the amount of memory allocated is incorrect. sizeof(node) gives you the size of a pointer, not the size of the _node structure which is what you need. The change is trivial, but not obvious:

node = malloc(sizeof *node);

Now, while you could say sizeof(struct _node), it's generally better not to depend on a type name on the off chance you end up changing it by renaming the type or using another type. The trick above depends on the fact that sizeof does not evaluate the expression itself, only the resulting size. Otherwise, dereferencing an uninitialized pointer would invoke undefined behavior. However, in this case it's both perfectly safe and conventional.

This bug is a side effect of hiding a pointer in a typedef, which is generally not recommended precisely for reasons like this.

Note that I didn't crash in the same place as you did. There's really nothing wrong with printList, so getting an error there is a false positive and one needs to dig deeper in a debugger to find the real problems.

Edited 1 Year Ago by deceptikon

This question has already been answered. Start a new discussion instead.