Skip to the content ForoHackers
Log inJoin

Data structures: start here

Data structures
#891 · Ophuscado · · Report

A data structure is a way of organising data in memory so that the operations you need are cheap. Arrays, lists, hash tables and trees all store the same items; they differ in how fast they find, insert, delete or order them. Choosing well often matters more than any micro-optimisation.

Key concepts

  • Abstract data type versus implementation: a stack or a map is an interface; arrays or linked nodes are ways to build it.
  • Contiguous versus linked memory: arrays are cache-friendly and indexed in constant time; linked nodes insert cheaply but chase pointers.
  • Hashing: a hash function sends a key to a slot; collisions are handled by chaining or probing.
  • Balanced trees: keeping a search tree shallow gives logarithmic search, insertion and deletion.
  • Heaps and priority queues: fast access to the smallest or largest item.

Vocabulary

  • Amortised cost: the average cost per operation over a long sequence, as when a dynamic array doubles.
  • Load factor: the ratio of stored items to slots in a hash table.
  • Invariant: a property the structure keeps true after every operation, such as the heap order.
  • Persistent structure: one that keeps old versions available after an update.

What to study, in order

  1. Build a dynamic array and a singly linked list; time insertion at the front and the end.
  2. Implement a hash table with chaining, then resize it and watch the load factor.
  3. Implement a binary search tree, then a balanced variant such as an AVL or red-black tree.
  4. Build a binary heap and use it for a priority queue and heapsort.
  5. Look at disjoint sets, tries and B-trees, and ask what each one makes fast.

Related tags

#algorithms #memory-management #databases #complexity

Log in or join to reply.