Plain-language explanation.
A data structure is a way of organising and storing data in a computer so it can be accessed and modified efficiently. Different structures are optimised for different operations — arrays for fast random access, linked lists for fast insertion/deletion, hash tables for fast lookup.
Core concepts and standard treatment.
Core data structures: arrays (contiguous memory, O(1) random access, O(n) insert/delete); linked lists (nodes with pointers, O(1) insert/delete at head, O(n) access — singly, doubly, circular); stacks (LIFO — Last In First Out — push/pop — used in function call stack, undo operations) and queues (FIFO — First In First Out — enqueue/dequeue — used in BFS, task scheduling); hash tables (key-value store — hash function → array index; collision handling — chaining, open addressing — O(1) average lookup); trees (binary trees — BST for ordered data, AVL trees / Red-Black trees for self-balancing O(log n) operations — used in Java TreeMap, C++ std::map); heaps (priority queue — min-heap / max-heap — O(log n) insert/extract-max — used in Dijkstra, heap sort); and graphs (adjacency list vs adjacency matrix — BFS, DFS traversal — O(V+E)).
Deeper theory, debates and edge cases.
Advanced data structures covers trie (prefix tree — string search, autocomplete — O(L) per operation, L = string length; compressed trie — Patricia tree; suffix tree and suffix array — O(n log n) construction — used in bioinformatics — Burrows-Wheeler transform), segment tree and Fenwick tree (BIT — range query + point update in O(log n) — competitive programming staple), disjoint set union (Union-Find — Kruskal's MST — path compression + union by rank — nearly O(α(n)) amortised — α is inverse Ackermann function), B-tree and B+ tree (database index — MySQL InnoDB B+ tree index; multi-way balanced tree — cache-efficient disk access), and spatial data structures (k-d tree — O(log n) nearest-neighbour search in k dimensions; R-tree — spatial indexing — PostGIS; quadtree / octree — 2D/3D space partitioning — game engines).
How it is applied in practice.
At the systems engineer and database architect level, practitioners design custom data structures for performance-critical applications (lock-free data structures — CAS — compare-and-swap — in concurrent programming; skip list in Redis sorted sets; HAMT — hash array mapped trie in Clojure persistent data structures; rope data structure for text editors — O(log n) string operations); implement database storage engines (LSM-tree in Apache Cassandra, LevelDB, RocksDB — write-optimised; B+ tree in MySQL InnoDB, PostgreSQL — read-optimised); apply cache-efficient data structures (cache line awareness — struct-of-arrays vs array-of-structs — SIMD vectorisation; CPU cache locality in HPC); and contribute to language runtime data structure design (JVM garbage collector data structures — G1GC remembered sets; V8 engine hidden classes and inline caches).