Data Structures & Algorithms Linear Data Structures Syllabus

How do you reverse a singly linked list iteratively?

Walk the list with three pointers (prev, cur, next), redirecting each node's next to prev. Runs in $O(n)$ time, $O(1)$ space; return prev as the new head.

How does the slow/fast pointer method find the middle of a linked list?

Advance slow by one and fast by two per step. When fast reaches the end, slow is at the middle. Time $O(n)$, space $O(1)$.

How do you detect a cycle in a linked list (Floyd's algorithm)?

Use slow (one step) and fast (two steps) pointers. If they ever meet, a cycle exists; if fast reaches null, there is no cycle. Time $O(n)$, space $O(1)$.

What distinguishes a doubly linked list from a singly linked list?

Each node has both 'next' and 'prev' pointers, enabling $O(1)$ bidirectional traversal and $O(1)$ deletion of a known node, at the cost of extra memory per node.

What defines a circular linked list?

The last node points back to the first (in singly-circular), so there is no null terminator; traversal can loop indefinitely and any node can serve as a starting point.

Give one advantage and one disadvantage of a doubly linked list vs. a singly linked list.

Advantage: constant-time deletion of a given node and backward traversal. Disadvantage: extra memory for the prev pointer and more pointer updates per operation.

How do you delete a node given only a pointer to it (not the head) in a singly linked list?

Copy the next node's data into the current node, then bypass the next node by setting current.next = current.next.next. This fails only for the tail node.

What is a sentinel (dummy) node and why is it useful in linked lists?

A placeholder node before the head that removes special-case handling of empty lists or head insertions/deletions, simplifying code.

How do you merge two sorted linked lists into one sorted list?

Use a dummy head and repeatedly attach the smaller of the two current nodes, advancing that pointer, until one list is exhausted; append the remainder. Time $O(n + m)$.

Define the Stack ADT and its ordering discipline.

A stack is a linear collection with Last-In-First-Out (LIFO) order: the most recently added element is the first removed.

Name the core stack operations and their time complexities.

push (add to top), pop (remove top), peek/top (view top), isEmpty — all $O(1)$.

What error conditions are associated with stack operations?

Stack overflow (push onto a full fixed-capacity stack) and stack underflow (pop or peek on an empty stack).

Compare array-based and linked-list-based stack implementations.

Array-based: cache-friendly, may need resizing, possible fixed capacity. Linked-list-based: grows dynamically with no resizing, but uses extra memory per node and has poorer locality. Both give $O(1)$ push/pop.

How is a stack used to check balanced parentheses?

Push each opening bracket; on a closing bracket, pop and verify it matches. The string is balanced if every close matches and the stack is empty at the end.

Which traversal order does the call stack impose, and name one stack application in expression handling.

LIFO. Applications include evaluating postfix expressions, converting infix to postfix, and function call management / recursion unwinding.

How do you evaluate a postfix (RPN) expression with a stack?

Push operands; on an operator, pop the top two operands, apply it, and push the result. The final remaining value is the answer. Time $O(n)$.

Define the Queue ADT and its ordering discipline.

A queue is a linear collection with First-In-First-Out (FIFO) order: the earliest added element is the first removed.

Name the core queue operations and their time complexities.

enqueue (add at rear), dequeue (remove from front), front/peek, isEmpty — all $O(1)$ with a proper implementation.

Why is a circular array preferred over a plain array for queue implementation?

A circular array reuses freed front slots by wrapping indices with modulo, giving $O(1)$ enqueue/dequeue without shifting elements or wasting space.

In a circular queue of capacity $C$, how are the rear and front indices advanced?

Using modular arithmetic: $\text{rear} = (\text{rear} + 1) \bmod C$ and $\text{front} = (\text{front} + 1) \bmod C$.

What is a deque (double-ended queue)?

A linear structure allowing insertion and removal at both the front and the rear, each in $O(1)$. It generalizes both stacks and queues.

What is a priority queue and how does it differ from an ordinary queue?

A priority queue dequeues the element with the highest priority rather than the earliest inserted. It is typically backed by a heap, giving $O(\log n)$ insert and extract.

What is a circular queue and one problem it solves?

A queue whose storage wraps around a fixed-size array. It avoids the wasted-space problem of a linear array queue where front advances but freed slots cannot be reused.

What is a monotonic queue and what invariant does it maintain?

A deque that keeps its elements in strictly increasing or decreasing order by discarding elements that violate the order before inserting a new one, enabling $O(1)$ min/max queries.

How does a monotonic deque compute the maximum of every sliding window of size $k$?

Maintain a decreasing deque of indices: pop smaller values from the back before pushing, pop the front if it falls outside the window; the front holds the window max. Total time $O(n)$.

Why does the sliding-window-maximum monotonic-queue algorithm run in $O(n)$ despite nested pops?

Each element is pushed and popped from the deque at most once, so the total number of operations is bounded by $2n$, giving amortized $O(1)$ per element.

How do you implement a queue using two stacks?

Use an 'in' stack for enqueue. For dequeue, if the 'out' stack is empty, pop all elements from 'in' into 'out' (reversing order), then pop from 'out'. Amortized $O(1)$ per operation.

How do you implement a stack using two queues (making push costly)?

On push, enqueue the new element into the empty queue, then move all elements from the other queue behind it, so the newest is always at the front. Push is $O(n)$; pop/top are $O(1)$.

Compare LIFO and FIFO structures with a real-world example of each.

LIFO (stack): browser back button / undo history. FIFO (queue): a printer job queue or people waiting in line. Stack removes newest first; queue removes oldest first.

Summarize the average time complexities for array, linked list, stack, and queue on their primary operations.

Array: access $O(1)$, insert/delete $O(n)$. Linked list: access $O(n)$, head insert/delete $O(1)$. Stack: push/pop/peek $O(1)$. Queue: enqueue/dequeue $O(1)$.