Data Structure and Algorithm Data Structures Syllabus

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 Data Structures in Data Structure and Algorithm, not a summary of it.

1. 1

   Arrays

   6 topics

   • Introduction to Arrays
   • 1-D Arrays
   • 2-D Arrays
   • Dynamic Arrays
   • Array Operations
   • Array Applications
2. 2

   Linked Lists

   6 topics

   • Introduction to Linked Lists
   • Singly Linked List
   • Doubly Linked List
   • Circular Linked List
   • Linked List Operations
   • Linked List Applications
3. 3

   Stacks

   5 topics

   • Introduction to Stacks
   • Stack Operations
   • Array Implementation of Stack
   • Linked List Implementation of Stack
   • Stack Applications
4. 4

   Queues

   8 topics

   • Introduction to Queues
   • Queue Operations
   • Array Implementation of Queue
   • Linked List Implementation of Queue
   • Circular Queue
   • Priority Queue
   • Deque (Double Ended Queue)
   • Queue Applications
5. 5

   Trees

   9 topics

   • Introduction to Trees
   • Binary Trees
   • Binary Search Trees
   • AVL Trees
   • Red-Black Trees
   • Segment Trees
   • Fenwick Trees
   • Tree Traversal Techniques
   • Tree Applications
6. 6

   Heaps

   6 topics

   • Introduction to Heaps
   • Binary Heaps
   • Min-Heap
   • Max-Heap
   • Heap Operations
   • Heap Applications
7. 7

   Graphs

   6 topics

   • Introduction to Graphs
   • Graph Representations
   • Graph Traversal Algorithms
   • Shortest Path Algorithms
   • Minimum Spanning Tree Algorithms
   • Graph Applications
8. 8

   Hashing

   5 topics

   • Introduction to Hashing
   • Hash Functions
   • Collision Resolution Techniques
   • Hash Table Operations
   • Hash Table Applications

Data Structures flashcards for Data Structure and Algorithm

20 of 51 cards from the Data Structures deck — real questions with worked answers.

1. What is an array in data structures?

   An array is a linear data structure that stores a fixed-size, contiguous collection of elements of the same data type, accessed by an index. Elements occupy adjacent memory locations.

2. How is the memory address of an element calculated in a 1-D array?

   For a 1-D array, the address of element at index $i$ is $$\text{Address}(A[i]) = B + (i - L) \times w$$ where $B$ is the base address, $L$ is the lower bound of the index, and $w$ is the size (in bytes) of each element.

3. What is the time complexity of accessing an element by index in an array, and why?

   $O(1)$ — constant time. Because elements are stored contiguously, the address of any index is computed directly with arithmetic, allowing random access without traversal.

4. What are the time complexities of insertion and deletion at an arbitrary position in a static array?

   Both are $O(n)$ in the worst case, because up to $n$ elements may need to be shifted to maintain contiguity.

5. What is the difference between a static array and a dynamic array?

   A static array has a fixed size set at compile/allocation time and cannot grow. A dynamic array can resize at runtime, automatically reallocating to a larger block when it becomes full.

6. How does a dynamic array grow when it runs out of capacity?

   It allocates a new, larger block (commonly double the current capacity), copies all existing elements into it, then frees the old block. This doubling keeps appends amortized $O(1)$.

7. What is the amortized time complexity of appending to a dynamic array, and why is it not $O(n)$?

   Amortized $O(1)$. Although an occasional resize costs $O(n)$ to copy, the doubling strategy spreads that cost across many cheap $O(1)$ appends, averaging to constant time per operation.

8. In row-major order, how is the address of element $A[i][j]$ computed for a 2-D array?

   $$\text{Address}(A[i][j]) = B + \big((i - L_r)\times N_c + (j - L_c)\big)\times w$$ where $B$ is the base address, $N_c$ is the number of columns, $L_r, L_c$ are the lower bounds of rows and columns, and $w$ is the element size.

9. In column-major order, how is the address of element $A[i][j]$ computed for a 2-D array?

   $$\text{Address}(A[i][j]) = B + \big((j - L_c)\times N_r + (i - L_r)\big)\times w$$ where $N_r$ is the number of rows, $L_r, L_c$ are the lower bounds, $w$ is the element size, and $B$ the base address.

10. What is the difference between row-major and column-major storage order for 2-D arrays?

    Row-major stores elements row by row (entire first row, then second, etc.), used by C/C++/Python. Column-major stores column by column, used by Fortran/MATLAB.

11. How many elements does an $m \times n$ 2-D array contain, and what is its total memory size?

    It contains $m \times n$ elements. Total memory is $m \times n \times w$ bytes, where $w$ is the size of each element.

12. List three common operations performed on arrays.

    Traversal (visiting each element), insertion (adding an element at a position), deletion (removing an element), searching (finding an element), and updating (modifying an element's value).

13. What is array traversal and what is its time complexity?

    Traversal is visiting each element of the array exactly once, typically with a loop. Its time complexity is $O(n)$ for $n$ elements.

14. Name three real-world applications of arrays.

    Implementing other data structures (stacks, queues, heaps, hash tables), storing matrices/tables, lookup tables, image pixel grids, and serving as the basis for sorting and searching algorithms.

15. What is a key limitation of static arrays regarding size?

    Their size is fixed at creation; you cannot grow them without allocating a new array and copying. This wastes memory if oversized or causes overflow if undersized.

16. What is a linked list?

    A linked list is a linear data structure where elements (nodes) are stored non-contiguously, each node holding data and one or more pointers/references to other nodes, linked together to form a sequence.

17. What two fields does a node in a singly linked list contain?

    A data field (the value) and a next pointer that references the following node (or null at the end of the list).

18. What is the time complexity of accessing the $k$-th element in a linked list, and why does it differ from an array?

    $O(n)$ in the worst case. Unlike arrays, linked lists have no random access; you must traverse from the head node following next pointers, since nodes are non-contiguous.

19. What are the main advantages of a linked list over an array?

    Dynamic size (grows/shrinks at runtime without reallocation) and $O(1)$ insertion/deletion at a known node without shifting elements. No need for contiguous memory.

20. What are the main disadvantages of a linked list compared to an array?

    No random ($O(1)$) access — access is $O(n)$; extra memory overhead for storing pointers; poor cache locality due to non-contiguous storage.

See more Data Structures flashcards →

Planning Data Structures for Data Structure and Algorithm

Data Structures (Data Structure and Algorithm) FAQ