GateShala
Playground

Data Structures

Data structures and algorithms are the toolkit behind every efficient program, and a core GATE CS subject. Each lesson explains one idea with figures, gives the code in Java, Python and C, and ends with GATE-style practice questions.

Start the first lesson

1Getting Started

  1. Introduction to Data StructuresWhat data structures and algorithms are, the main kinds, and why the choice matters.
  2. Time and Space ComplexityMeasure how running time grows with input size using Big-O, Big-Omega and Big-Theta.
  3. Recursion and Recurrence RelationsHow recursive calls run, and how to find their running time with recursion trees and the master theorem.

2Linear Data Structures

  1. Arrays and Dynamic ArraysConstant-time indexing, address calculation, and how growable arrays stay fast.
  2. Linked ListsNodes connected by pointers, with O(1) insertion at the front and no fixed size.
  3. StacksLast in, first out. Function calls, undo, bracket matching and postfix evaluation.
  4. Queues and DequesFirst in, first out. Circular arrays, double-ended queues and where queues are used.

3Hashing

  1. Hash TablesAverage O(1) search, insert and delete using a hash function, with chaining or open addressing.

4Trees

  1. Binary Trees and TraversalsTree terminology, the four classic traversals, height and counting nodes.
  2. Binary Search TreesKeep keys ordered so search, insert and delete take time proportional to the height.
  3. AVL Trees (Self-Balancing BSTs)Keep a BST balanced with rotations so search, insert and delete stay O(log n) in the worst case.
  4. Heaps and Priority QueuesA complete binary tree stored in an array that always gives you the smallest (or largest) item fast.

5Graphs

  1. Graphs, BFS and DFSRepresent networks with adjacency lists and matrices, and explore them breadth-first and depth-first.
  2. DFS Applications (Edge Types, Cycles, Components)Discovery and finish times, classifying edges, detecting cycles and finding strongly connected components.
  3. Shortest Paths (Dijkstra and Bellman-Ford)Find the cheapest route in a weighted graph, and know when negative edges break things.
  4. Minimum Spanning Trees (Kruskal and Prim)Connect every vertex with the least total edge weight, using greedy algorithms.

6Searching and Sorting

  1. Searching (Linear and Binary Search)Linear search, binary search and its variants, and searching on the answer.
  2. Simple Sorting (Bubble, Selection, Insertion)Three easy O(n²) sorts, how many swaps and comparisons they make, and when they are still useful.
  3. Fast Sorting (Merge, Quick, Counting)Divide-and-conquer sorts in O(n log n), the comparison lower bound, and linear-time counting sort.

7Algorithm Design Techniques

  1. Divide and ConquerSplit, solve recursively, combine. Fast exponentiation, max-min, maximum subarray and fast multiplication.
  2. Greedy AlgorithmsMake the locally best choice at every step. Activity selection, fractional knapsack and Huffman coding.
  3. Dynamic ProgrammingSolve problems with overlapping subproblems by remembering answers, with Fibonacci, coin change, LCS and knapsack.

8GATE Practice

  1. GATE Practice Set (Mixed Topics)A mixed set of GATE-style MCQ, MSQ and NAT questions covering the whole data structures and algorithms syllabus.