Data Structures & Algorithms Linear Data Structures Syllabus

Linear Data Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Linear Data Structures in Data Structures & Algorithms, not a summary of it.

1. 1

   Arrays & Strings

   4 topics

   • Static and Dynamic Arrays
   • Array Techniques
   • String Manipulation
   • Multidimensional Arrays and Matrices
2. 2

   Linked Lists

   3 topics

   • Singly Linked Lists
   • Doubly and Circular Linked Lists
   • Linked List Techniques
3. 3

   Stacks

   3 topics

   • Stack ADT and Operations
   • Stack Implementations
   • Stack Applications
4. 4

   Queues & Deques

   4 topics

   • Queue ADT and Operations
   • Queue Variants
   • Monotonic Queue
   • Queue using Stacks and Vice Versa

Linear Data Structures flashcards for Data Structures & Algorithms

22 of 50 cards from the Linear Data Structures deck — real questions with worked answers.

1. What is a static array, and what is its defining constraint?

   A static array is a contiguous, fixed-size block of memory holding elements of the same type. Its size is fixed at allocation time and cannot change during execution.

2. What is a dynamic array and how does it grow?

   A dynamic array (e.g., C++ vector, Python list) is a resizable array. When capacity is exceeded, it allocates a larger block (typically doubling), copies existing elements over, and frees the old block.

3. Why does appending $n$ elements to a dynamic array cost $O(n)$ total despite occasional resizes?

   Because doubling makes resizes geometrically rare; the total copy work is $\sum 2^{k} \approx 2n$, giving an amortized cost of $O(1)$ per append and $O(n)$ overall.

4. What is the time complexity of accessing element at index $i$ in an array, and why?

   $O(1)$. The address is computed directly as $\text{base} + i \times \text{size\_of\_element}$, so no traversal is needed.

5. What is the cost of inserting or deleting at an arbitrary position in an array of size $n$?

   $O(n)$, because on average $\frac{n}{2}$ elements must be shifted to fill or make room.

6. Compare an array and a linked list on random access and insertion at the front.

   Array: random access $O(1)$, front insertion $O(n)$. Linked list: random access $O(n)$, front insertion $O(1)$.

7. Describe the two-pointer technique and a problem it solves.

   Two pointers traverse a structure from different positions (e.g., both ends or fast/slow) to reduce complexity. Example: finding a pair summing to a target in a sorted array in $O(n)$ instead of $O(n^{2})$.

8. What is the sliding window technique used for?

   Maintaining a contiguous subrange whose bounds move to satisfy a condition, solving subarray/substring problems (e.g., max sum of size $k$, longest substring without repeats) in $O(n)$.

9. What is a prefix sum array and how does it enable range-sum queries?

   $P[i]$ stores the sum of the first $i$ elements. The sum of range $[l, r]$ is computed in $O(1)$ as $P[r+1] - P[l]$.

10. How does Kadane's algorithm find the maximum subarray sum?

    It scans once, keeping $\text{cur} = \max(x, \text{cur} + x)$ and tracking the best value seen. Runs in $O(n)$ time, $O(1)$ space.

11. What does it mean for an in-place array algorithm to use $O(1)$ auxiliary space?

    It rearranges elements within the original array using only a constant amount of extra memory, regardless of input size (e.g., in-place reversal by swapping ends inward).

12. In most languages, are strings mutable or immutable, and what is a consequence?

    Strings are typically immutable (e.g., Java, Python). Each modification creates a new string, so building a string by repeated concatenation costs $O(n^{2})$; use a mutable builder for $O(n)$.

13. How do you check if two strings are anagrams efficiently?

    Compare character-frequency counts. Using a fixed-size count array over the alphabet gives $O(n)$ time and $O(1)$ extra space.

14. What is the naive substring-search time complexity, and name a faster algorithm.

    Naive search is $O(nm)$ for text length $n$ and pattern length $m$. The KMP algorithm runs in $O(n + m)$ using a prefix (failure) function.

15. How is a 2D matrix of dimensions $m \times n$ stored in row-major order, and what is the address formula?

    Rows are stored consecutively. The element at $(i, j)$ has offset $\text{base} + (i \times n + j) \times \text{size}$.

16. How do you transpose a square matrix in place?

    For all $i < j$, swap $A[i][j]$ with $A[j][i]$. This runs in $O(n^{2})$ time with $O(1)$ extra space.

17. How can you rotate an $n \times n$ matrix 90° clockwise in place?

    Transpose the matrix, then reverse each row. Both steps are $O(n^{2})$ and use $O(1)$ extra space.

18. What is the total number of elements and the space complexity of an $m \times n$ matrix?

    It has $m \times n$ elements and uses $O(mn)$ space.

19. Define a singly linked list node and its structure.

    A node holds a data field and a single pointer 'next' to the following node. The list is accessed via a 'head' pointer; the last node's next is null.

20. What are the time complexities of insertion at the head vs. search in a singly linked list?

    Head insertion is $O(1)$; search (and access by index) is $O(n)$ because nodes must be traversed sequentially.

21. 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.

22. 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)$.

See more Linear Data Structures flashcards →

Planning Linear Data Structures for Data Structures & Algorithms

Linear Data Structures (Data Structures & Algorithms) FAQ