Queue Implementation using Linked List

Linked list based queue me array size ki koi static limitation nahi hoti. Queue tab tak expand ho sakti hai jab tak system me free RAM available ho. Linked list me queue ko maintain karne ke liye do pointers use hote hain: front aur rear.

Pointer Roles

• front: Points to the first node (Head of list). Dequeue operation O(1) me front se hota hai.
• rear: Points to the last node (Tail of list). Enqueue operation O(1) me rear ke aage naya node attach karke hota hai.

front                                                  rear
  |                                                      |
  v                                                      v
[ Data: 10 | Next ] ---> [ Data: 20 | Next ] ---> [ Data: 30 | Next: NULL ]

C Implementation

struct Node { int data; struct Node* next; };
struct Node *front = NULL, *rear = NULL;

void enqueue(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val; newNode->next = NULL;
    if (rear == NULL) { front = rear = newNode; return; }
    rear->next = newNode;
    rear = newNode;
}

int dequeue() {
    if (front == NULL) { printf("Queue Underflow!\n"); return -1; }
    struct Node* temp = front;
    int val = temp->data;
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
    return val;
}

Agli post me hum cover karenge Double-Ended Queue (Deque): Input and Output-Restricted.