Saltar al contenido ForoHackers

Data structures: start here

Estructuras de datos
#3397 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder