Rob Pike's rule: pick the right data layout and the algorithm writes itself
Programmer Rob Pike has argued that how you arrange your data almost always matters more for speed than which algorithm you choose, because once the layout is right the method tends to be obvious. That is why databases, compilers, file systems and search engines all rely on carefully chosen data structures.
A data structure is the concrete way information is laid out in memory, together with the routines that insert, delete, look up and walk through it. It differs from an abstract data type, which only promises certain operations and results without saying how they happen. A single abstract list, for instance, can be built as a linked chain or as a resizable array, and each choice performs differently.
The most basic trade-off is between neat rows and chains of pointers. An array keeps elements side by side, so the computer can jump straight to item 500 with a little arithmetic, which makes sequential processing fast. A linked list stores, in each node, the address of the next one; adding or removing an entry never means shuffling everything else along, but finding the 500th element means following the chain step by step.
Everyday software leans on a handful of classics. Relational databases usually index records with B-trees, and compilers typically find variable names with hash tables, which turn a key into an array position and usually answer in constant time, though two keys landing on the same slot must be handled. A stack works like a pile of plates, last in and first out, whereas a queue serves first come, first served. A trie, which stores words one character per node, makes autocomplete and spell-checking quick.
Language support varies widely. Most assembly languages and the old language BCPL offer no built-in data structures, while its descendant C added structs and arrays, and Pascal offered records. Modern languages ship ready-made collections, such as the C++ Standard Template Library and the Java Collections Framework, and many structures now come in concurrent versions that several threads can use at once.
Source: Data structure
