Data Structure and Algorithm Data Structures Syllabus

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

Each node in a doubly linked list has two pointers — next and prev (previous) — allowing traversal in both directions. A singly linked list has only a next pointer and is one-directional.

What is the extra memory cost of a doubly linked list versus a singly linked list?

One additional pointer (the prev pointer) per node, increasing per-node overhead by the size of one reference.

What defines a circular linked list?

A linked list in which the last node points back to the first node (head) instead of null, forming a closed loop. It can be singly or doubly circular.

In a circular doubly linked list, what do the head's prev pointer and the tail's next pointer reference?

The head's prev pointer references the tail (last node), and the tail's next pointer references the head, forming a bidirectional loop.

What is the time complexity of inserting a node at the head (beginning) of a singly linked list?

$O(1)$ — constant time. The new node's next is set to the current head, and the head pointer is updated to the new node; no traversal needed.

What is the time complexity of inserting a node at the end of a singly linked list without a tail pointer?

$O(n)$, because you must traverse the entire list to reach the last node before linking the new node. With a maintained tail pointer it becomes $O(1)$.

To delete a given node in $O(1)$ time, which type of linked list makes this easiest and why?

A doubly linked list, because the node's prev pointer lets you directly relink the previous and next nodes without traversing from the head to find the predecessor.

Why is deleting a node (given a pointer to it) $O(n)$ in a singly linked list?

Because the singly linked node has no prev pointer; you must traverse from the head to find the predecessor in order to update its next pointer to bypass the deleted node.

Name three applications of linked lists.

Implementing stacks and queues, dynamic memory management (free lists), undo/redo functionality, hash table chaining for collision handling, polynomial representation, and adjacency lists for graphs.

How are linked lists used to implement polynomials?

Each node stores a term's coefficient and exponent, and nodes are linked in order of exponents. This allows efficient representation and addition/multiplication of sparse polynomials.

What is a stack and which principle governs it?

A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle: the most recently inserted element is the first one removed.

Name the two primary operations of a stack and what each does.

Push — adds (inserts) an element to the top of the stack. Pop — removes and returns the element from the top of the stack.

What do the peek (top) and isEmpty operations do on a stack?

peek/top returns the element at the top without removing it. isEmpty returns true if the stack contains no elements (top indicator points below the first position).

What is the time complexity of push, pop, and peek operations on a stack?

All are $O(1)$ — constant time — since they only operate on the top element.

In an array implementation of a stack, what does the 'top' variable represent and what is its initial value for an empty stack?

'top' is the index of the topmost element. For an empty stack it is initialized to $-1$ (no elements). It increments on push and decrements on pop.

What is stack overflow in an array-based stack implementation?

Stack overflow occurs when a push is attempted while the stack is full — i.e., when $top = size - 1$ — and there is no room for a new element.

What is stack underflow?

Stack underflow occurs when a pop or peek is attempted on an empty stack (when $top = -1$), so there is no element to remove or return.

What is the main disadvantage of an array implementation of a stack?

Its size is fixed (static), so it can overflow when full, and it may waste memory if the allocated capacity is larger than needed. Resizing requires copying.

In a linked list implementation of a stack, where are push and pop performed and why?

At the head (front) of the list, because insertion and deletion at the head are $O(1)$, giving constant-time push and pop without traversal.

What is the advantage of a linked list implementation of a stack over an array implementation?

It is dynamic — it grows and shrinks as needed, so there is no fixed-capacity overflow (limited only by available memory) and no wasted preallocated space.

Compare array vs linked list implementations of a stack in terms of memory.

The array version uses contiguous fixed memory with no per-element pointer overhead but may waste or overflow space. The linked list version uses dynamic memory with extra pointer overhead per node but no fixed capacity.

Name three applications of stacks.

Function call management (call stack/recursion), expression evaluation and conversion (infix to postfix/prefix), balanced parentheses checking, undo/redo operations, backtracking, and depth-first search (DFS).

How is a stack used in evaluating arithmetic expressions?

A stack holds operands (and/or operators) during evaluation of postfix/prefix expressions, and is used to convert infix to postfix, ensuring correct operator precedence and order of operations.

Why is a stack used to manage recursive function calls?

Each function call pushes an activation record (parameters, local variables, return address) onto the call stack; when a call returns, its record is popped — matching the LIFO nature of nested calls.

What does the algorithm for checking balanced parentheses use a stack for?

It pushes each opening bracket and pops on each closing bracket, checking the popped bracket matches. A balanced expression leaves the stack empty at the end with all matches correct.

What is a queue and which principle governs it?

A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle: the first element inserted is the first one removed.

What are the two ends of a queue called, and which operation happens at each?

The rear (or back/tail), where enqueue (insertion) occurs, and the front (or head), where dequeue (removal) occurs.

Name the two primary operations of a queue and what each does.

Enqueue — adds an element at the rear of the queue. Dequeue — removes and returns the element from the front of the queue.

What is the key behavioral difference between a stack and a queue?

A stack is LIFO (last-in, first-out) — insertion and removal occur at the same end (top). A queue is FIFO (first-in, first-out) — insertion at the rear and removal at the front, opposite ends.

Name three real-world applications of queues.

CPU/process scheduling, print/job spooling, handling requests in web servers, breadth-first search (BFS), buffering data streams (I/O buffers), and call-center request handling.

What problem does a circular queue solve compared to a simple linear array queue?

A circular queue reuses freed front slots by wrapping the rear index around to the start, preventing the 'false overflow' where a linear array queue reports full even though dequeued space exists at the front.