C Program For Linked List Implementation Of Queue

The major disadvantage of array implementation of queue is that the size of the queue is fixed.  If we are not familiar with the size of the queue, then we can implement queue using linked list.  Usually head of the queue will be used as front and tail of the queue will be used as rear.  Basically, we do insertion at the rear and deletion at the front.

            front(head)                                                      rear(tail)
            -----------------           -----------------                ----------------
           |  10    |       -|------->|   20    |     --|---------->|   30  |      --|---->X
           ------------------           -----------------                ----------------

Enqueue:  Insert 40 to the queue.

       front(head)                                                                     rear(tail)
       -----------------        -----------------       ----------------       ----------------
      |  10    |       -|---->|   20    |     --|--->|   30  |      --|--->|  40   |      --|->X
       ------------------       -----------------       ----------------       ----------------

Dequeue:

            front(head)                                                      rear(tail)
            -----------------           -----------------                ----------------
           |  20    |       -|------->|   30    |     --|---------->|   40  |      --|---->X
           ------------------           -----------------                ----------------

Do you know why deletion is performed at the rear?

     To delete a node at the rear, we need to traverse from the start of the list and move all the way to right to get the new rear(tail) and delete the current rear node, which is a very expensive operation.

See Also:
C Program For Array Implementation Of Queue
C Program For Array Implementation Of Stack
C Program For Linked List Implementation Of Stack
C Program For Linked List Implementation Of Queue
C Program For Double Ended Queue (Dequeue)
C Program To Implement Circular Stack
C Program To Implement Circular Queue

C Program To Implement Priority Queue

Example Program For Linked List Implementation Of Queue:

---

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

  struct node {
        int data;
        struct node *next;
  };

  struct node *front = NULL, *rear = NULL;

  struct node * createNode(int data) {
        struct node *newnode = (struct node *)malloc(sizeof (struct node));
        newnode->data = data;
        newnode->next = NULL;
        return (newnode);
  }

  void enqueue(int data) {
        struct node *ptr = createNode(data);
        if (!rear) {
                front = rear = ptr;
                return;
        }
        rear->next = ptr;
        rear = ptr;
  }

  void dequeue() {
        struct node *tmp;
        if (!front) {
                printf("Queue is empty\n");
                return;
        } else if (front == rear) {
                tmp = front;
                front = rear = NULL;
        } else {
                tmp = front;
                front = front->next;
        }
        free(tmp);
        return;
  }

  void display() {
        struct node *tmp;
        if (!front) {
                printf("Queue is empty\n");
        } else {
                tmp = front;
                while (tmp) {
                        printf("%-3d", tmp->data);
                        tmp = tmp->next;
                }
                printf("\n");
        }
        return;
  }

  int main() {

        int data, ch;

        while (1) {

                printf("1. Enqueue\n2. Dequeue\n");

                printf("3. Display\n4. Exit\n");

                printf("Enter your choice:");

                scanf("%d", &ch);

                switch (ch) {

                        case 1:

                                printf("Enter ur i/p to insert:");

                                scanf("%d", &data);

                                enqueue(data);

                                break;

                        case 2:

                                dequeue();

                                break;

                        case 3:

                                display();

                                break;

                        case 4:

                                exit(0);

                        default:

                                printf("Please enter correct option\n");

                                break;

                }

        }

        return 0;

  }

  Output: (C Program For Linked List Implementation Of Queue)

  jp@jp-VirtualBox:$ ./a.out
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:1
  Enter ur i/p to insert:10
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:1
  Enter ur i/p to insert:20
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:3
  10 20 
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:2
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:3
  20 
  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
  Enter your choice:4