Skip to the content ForoHackers
Log inJoin

Data structures: start here

Data structures
#3397 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply