Dequeue Using Linked List in DSA C - Time & Space Complexity

Time Complexity: Dequeue Using Linked List

O(n)

Understanding Time Complexity

We want to understand how the time to perform operations on a dequeue using a linked list changes as the number of elements grows.

Specifically, how fast can we add or remove items from either end?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert at front
void insertFront(Deque* dq, int value) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = dq->front;
    dq->front = newNode;
    if (dq->rear == NULL) dq->rear = newNode;
}

// Remove from rear
int removeRear(Deque* dq) {
    if (dq->rear == NULL) return -1; // empty
    int val;
    if (dq->front == dq->rear) {
        val = dq->front->data;
        free(dq->front);
        dq->front = NULL;
        dq->rear = NULL;
        return val;
    }
    Node* temp = dq->front;
    while (temp->next != dq->rear) temp = temp->next;
    val = dq->rear->data;
    free(dq->rear);
    dq->rear = temp;
    dq->rear->next = NULL;
    return val;
}
    

This code shows adding an element at the front and removing an element from the rear of a dequeue implemented with a linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop in removeRear that moves through nodes to find the one before the rear.
• How many times: This loop runs once for each node except the last, so up to n-1 times where n is the number of elements.

How Execution Grows With Input

As the number of elements grows, the time to remove from rear grows linearly because we must find the node before the last.

Input Size (n)	Approx. Operations
10	About 9 steps to find the node before rear
100	About 99 steps
1000	About 999 steps

Pattern observation: The steps increase directly with the number of elements, so doubling elements doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means removing from the rear takes longer as the list grows, roughly proportional to the number of elements.

Common Mistake

[X] Wrong: "Removing from the rear is always fast because we have a pointer to the rear node."

[OK] Correct: Even though we have the rear pointer, we must find the node before rear to update its next pointer, which requires walking through the list.

Interview Connect

Understanding how linked list operations scale helps you explain trade-offs in data structure choices clearly and confidently.

Self-Check

"What if we kept a pointer to the node before rear? How would that change the time complexity of removing from the rear?"

Practice

1. What is the main advantage of using a linked list to implement a dequeue compared to an array?

easy

A. Dynamic size allows easy insertion and deletion at both ends

B. Faster access to elements by index

C. Uses less memory than arrays

D. Simpler to implement than arrays

Solution

1. Step 1: Understand linked list flexibility

   A linked list can grow or shrink dynamically without needing a fixed size.

2. Step 2: Compare with array limitations

   Arrays have fixed size and costly resizing; linked lists allow easy insertion/deletion at both ends.

3. Final Answer:

   Dynamic size allows easy insertion and deletion at both ends -> Option A

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked lists grow/shrink easily at ends [OK]

Common Mistakes:

• Confusing faster index access with linked list
• Thinking linked lists always use less memory
• Assuming arrays are simpler to implement

2. Which of the following is the correct way to declare a node structure for a dequeue using a linked list in C?

easy

A. struct Node { int data; struct Node* next; };

B. struct Node { int data; struct Node next; struct Node prev; };

C. struct Node { int data; int next; int prev; };

D. struct Node { int data; struct Node* next; struct Node* prev; };

Solution

1. Step 1: Identify node fields for dequeue

   A dequeue node needs data and pointers to next and previous nodes for double linking.

2. Step 2: Check pointer types

   Correct syntax uses pointers (struct Node*) for next and prev, not int or struct Node directly.

3. Final Answer:

   struct Node { int data; struct Node* next; struct Node* prev; }; -> Option D

4. Quick Check:

   Double linked node = data + next ptr + prev ptr [OK]

Hint: Double linked nodes need next and prev pointers [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer for dequeue
• Declaring next/prev as struct Node instead of pointer

3. Consider the following operations on an empty dequeue implemented using a linked list:
insertFront(10); insertRear(20); insertFront(5); deleteRear();
What will be the state of the dequeue from front to rear after these operations?

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> null

D. 5 -> 20 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   Dequeue: 10 (front) -> 20 (rear)

2. Step 2: Perform insertFront(5) and deleteRear()

   After insertFront(5): 5 -> 10 -> 20
   After deleteRear(): removes 20, so 5 -> 10

3. Final Answer:

   5 -> 10 -> null -> Option A

4. Quick Check:

   Front insert adds at front, rear delete removes last [OK]

Hint: Track front and rear changes stepwise [OK]

Common Mistakes:

• Confusing insertFront and insertRear order
• Forgetting to delete rear element
• Mixing up front and rear positions

4. The following C code snippet for deleting from the front of a dequeue has an error. What is the error?

void deleteFront() {
  if (front == NULL) {
    printf("Dequeue is empty\n");
    return;
  }
  struct Node* temp = front;
  front = front->next;
  if (front == NULL) {
    rear = NULL;
  }
  free(temp);
}

medium

A. Uses free() incorrectly

B. Does not check if dequeue is full

C. Does not update the prev pointer of new front node

D. Does not update rear pointer when dequeue becomes empty

Solution

1. Step 1: Analyze pointer updates after deletion

   After moving front to front->next, the new front's prev pointer still points to old node.

2. Step 2: Identify missing update

   Must set front->prev = NULL to maintain correct double link.

3. Final Answer:

   Does not update the prev pointer of new front node -> Option C

4. Quick Check:

   Update prev pointer after front deletion [OK]

Hint: Always reset prev of new front to NULL [OK]

Common Mistakes:

• Ignoring prev pointer update
• Checking dequeue full in delete function
• Not updating rear when empty (not shown here)

5. You want to implement a function to reverse a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue?

hard

A. Only swap front and rear pointers without changing node links

B. Swap next and prev pointers of each node, then swap front and rear pointers

C. Delete all nodes and re-insert them from rear to front

D. Traverse from front to rear and copy data into a new list in reverse order

Solution

1. Step 1: Understand reversing a doubly linked list

   Reversing means each node's next and prev pointers must be swapped to reverse direction.

2. Step 2: Swap front and rear pointers

   After swapping pointers in nodes, front and rear pointers must also be swapped to reflect new ends.

3. Final Answer:

   Swap next and prev pointers of each node, then swap front and rear pointers -> Option B

4. Quick Check:

   Swap links + swap ends = reverse dequeue [OK]

Hint: Swap next/prev in nodes, then swap front/rear [OK]

Common Mistakes:

• Only swapping front and rear pointers
• Rebuilding list instead of reversing links
• Copying data instead of changing pointers