Skip to content
academia.sh
tr
Log in

Course Intermediate

Data Structures

By the end of this course

Start course

01

Linear Structures

Arrays, linked lists, stacks, queues, and skip lists; the consequences of contiguous and linked layout.

  1. 01 Arrays Contiguous memory layout, constant-time access through address arithmetic, the fixed-size constraint, and the language of cost.
  2. 02 Dynamic Arrays Capacity growth, the choice of growth factor, amortized cost analysis, and the shrink threshold.
  3. 03 Linked Lists Node and link structure, singly and doubly linked lists, the cost of pointer relinking, and their practical limits.
  4. 04 Stacks The abstract data type concept, the last-in-first-out model, two implementation options, and typical use cases.
  5. 05 Queues and Deques The first-in-first-out model, a queue in fixed memory using a circular buffer, the deque, and use cases.
  6. 06 Skip Lists Reducing search cost by adding layers to a sorted linked list, probabilistic height, and expected cost.

02

Dictionaries and Sets

Hash tables, collision resolution, set structures, and disjoint sets.

  1. 01 Hash Tables Computing a location from a key, the qualities of a hash function, the load factor, and the conditions for average constant cost.
  2. 02 Collision Resolution Chaining and open addressing, probing strategies, clustering, the deletion problem, and a comparison of the two families.
  3. 03 Sets and Multisets The membership-focused abstract type, hash-based and ordered implementations, bitsets, and counted multisets.
  4. 04 Disjoint Sets The dynamic grouping problem, the union-find structure, union by rank, path compression, and its uses.

03

Trees

From tree terminology to balanced search trees, heaps, tries, and range structures.

  1. 01 Tree Terminology The concepts of root, child, leaf, depth, and height; the definition of a tree, representation options, and areas of use.
  2. 02 Binary Trees The at-most-two-children constraint, the definitions of full and complete trees, the height–node count relationship, and array representation.
  3. 03 Tree Traversals Preorder, inorder, and postorder traversal, level-order traversal, recursive and stack-based forms, and their uses.
  4. 04 Binary Search Trees The ordering invariant, search–insert–delete operations, the three deletion cases, and the degenerate tree problem.
  5. 05 Balanced Search Trees The rotation operation, the AVL balance criterion and its four cases, red–black tree color invariants, and a comparison of the two families.
  6. 06 2-3 and 2-3-4 Trees Multiple keys per node, growth by splitting upward, perfect depth balance, and the correspondence with red–black trees.
  7. 07 B-Trees Design driven by block-based storage, high branching factor, the B+ tree leaf chain, and index usage.
  8. 08 Heaps Priority queues, the heap condition, array representation, sift-up and sift-down, and the linear cost of building a heap.
  9. 09 Tries The key becoming a path, sharing common prefixes, prefix queries, and the memory–speed trade-off.
  10. 10 Segment and Fenwick Trees Situations that require both range queries and point updates together, the segment tree, and the Fenwick tree.
  11. 11 Multidimensional Trees Spatial queries, alternating splits in a k-d tree, nearest-neighbor search, pruning, and the curse of dimensionality.

04

Graphs

The concept of a graph, representation options, breadth-first and depth-first search, and topological sort.

  1. 01 The Concept of a Graph Vertex and edge definitions, directed and undirected graphs, weight, degree, path, and cycle concepts.
  2. 02 Graph Representations Adjacency matrix versus adjacency list, memory and operation costs, the sparsity criterion, and the edge list.
  3. 03 Breadth-First Search Layer-by-layer traversal with a queue, visited marking, unweighted shortest path, and path reconstruction.
  4. 04 Depth-First Search Deep traversal with a stack, recursive and explicit-stack forms, discovery–finish times, and cycle detection.
  5. 05 Topological Sort Producing a valid execution order from a dependency graph, an in-degree-based algorithm, cycle detection, and uses.

Start typing to search.

↑↓ ↵ Esc navigate · open · close