Deleting a node from a Queue

Question

I had been working on making a Queue and trying to manage it. I needed a Queue to keep a record of active clients in my udp single server/multiple clients application (I am forced to use udp so please don't suggest shifting to tcp).

There is single Server and x number of clients. Whenever a client sends its first message, the ip number and port number of this client is push()ed into a Queue.

Then, after every 5 sec, server pop()s ip and port number out of the Queue and sends a message to client with this ip and port number. If client replies back within a specific time, it is considered "Active" but if no repy receieved from the client within a time out, the Client is considered dead and must be removed from the Queue.

Now the problem is that how to delete this node. One option is simply adding NULL in place of this node but I want to completely delete this node from the Queue.

Any suggestions are more than welcome.

Below is my code:

struct node
{
    int rollno;
    struct node*n;
};

struct node* create()
{
    struct node*q;
    q=(struct node*)malloc(sizeof(struct node));
    return q;
}
void push(struct node*cur)
{
    if(head==NULL)
    {
        head = cur;
        tail = cur;
        start = cur; //keeps a track of first node
    }
    else
    {
        struct node*f;
        f=head;
        head->n = cur;
        head=head->n; //keep updating head
    }
}

struct node* pop()
{
    struct node*p;
    struct node*s = NULL;p = tail;

    if (p == head && tail != head) /*if at the end of list, display starting from first element as Queue is FIFO*/
    {
        p = start;
        tail=p->n;
        s = p;
        display(s);
        return s;
    }

    if(p == NULL)
    {
        if (start == NULL)  //if no emelemt yet in the Queue
           return NULL;
        else // if at the End of list, go back to start
           {
              p = start;
              tail=p->n;
              s = p;
           }
    }
    else 
    {
           tail=p->n; //keep updating tail
           s = p;
    }

    display(s);
    return s;
}

void main()
{
   while(1)
   {
        //if new client
    struct node*j;  
    j = create();
        // j= ip and port of client.
    j->n=NULL;
        push(j); 
        //after every 5 secs
        {
           pop();
           //if client fails to reply
           {
              delete node.
           }
        }
   }



}

Answer 1

As DPG said, linked list is more suited here.

For now, do you need something like this?

void freenode(struct node* n)
{
    struct node* p = start;
    struct node* last = start;
    while (p != NULL) {
        if (p == n) {
            if (p == start) {
                if (p->n = NULL) {
                    head = NULL;
                    start = NULL;
                    tail = NULL;
            }
            else {
                if (tail == start)
                    tail = start->n;
                    start = start->n;
            }
            }
            else if (p == head) {
                head = last;
            head->n = NULL;
            }
            else {
                last->n = p->n;
            }
            free(p);
            break;
        }
        last = p;
        p = p->n;
    }
}

Answer 2

Since it's meant to be a queue, deletion would happen only at the front meaning you only need to get rid of the head element. Something like:

void delete()
{
    node* temp = head;  /* store the head the pointer so we can free it later */
    head = head->next;  /* make the node next to head be the head */
    free(temp);         /* free the original head pointer */
}

Taking into account your comment, if I've understood correctly you need to delete any node in the linked list.

This is a deletion function for a node in a linked list that takes care of three 3 separate cases - if the node to be deleted is a head, if it's a tail or if it is inbetween (note that you would need to provide your own functionality for identifying a dead node):

/* need id argument to know which node needs to be deleted
 * we need to already know which node is dead */
void delete_arbitrary(int id) 
{
    if (head->rollno == id) /* id matches that of head, let's delete it */
    {
        node* temp = head;  /* store the head pointer so we can free it later */
        head = head->next;  /* make the node next to head be the head */
        free(temp);         /* free the original head pointer */
    }
    else /* node somewhere down the line, let's find it */
    {
        node* curr = head->next /* start from the node after the head */
        node* prev; /* this is to keep track of the previous node */

        while(curr->rollno != id && curr != NULL)
        {
            prev = curr;
            curr = curr->next;
        }

        if (curr == NULL) /* didn't find it so let's report it and quit */
        {
            printf("Node not found\n");
        }
        else if (curr->next == NULL) /* we're at the tail */
        {
            node* temp = tail; /* store it for later deletion */
            tail = prev; /* the previous node is now the tail */
            free(temp); /* free the old tail */
        }
        else /* it's somewhere in between */
        {
            prev->next = curr->next; /* the previous node now points to the one after the current */
            free(curr); /* get rid of the current pointer */
        }
    }
}

Answer 3

If you use malloc function to allocate memory for your nodes, you can release that memory using free function. Here you haven't allocate memory for j pointer and it is a bug.

In your application, you have to check whether each element is active in every 5 minutes and if any node is inactive at the moment, you have to delete it. So, I think you don't need a FIFO data structure. It's better to use linked list data structure.