Types of Data Structures

Types of Data Structures

A data structure is a deliberate arrangement of data in memory together with the set of operations that arrangement makes cheap. The word "deliberate" is the whole point: the same 1,000 integers can live in a contiguous array, a chain of linked nodes, a balanced tree, or a hash table, and each layout hands you a completely different bill for the operations you care about. Choosing a data structure is really choosing which operations you want to be fast and which you are willing to let be slow. There is no universally best structure, only the best structure for a given access pattern.

The intuition worth internalising: memory is a flat array of numbered cells. Every fancy structure is ultimately built on that flat tape plus pointers (stored cell numbers) and a bit of cleverness about where you put things so you don't have to look everywhere to find them.

A precise definition and the two big families

Formally, a data structure is a triple: (1) a set of values it stores, (2) a layout mapping those values onto memory, and (3) an interface of operations with a defined cost for each. We classify structures along two axes.

• Linear vs. non-linear. In a linear structure each element has exactly one predecessor and one successor (arrays, linked lists, stacks, queues). In a non-linear structure an element may connect to many others (trees, graphs, heaps).
• Contiguous vs. linked. Contiguous structures occupy one unbroken block of memory (arrays, matrices, dynamic arrays). Linked structures scatter nodes anywhere and stitch them together with pointers (linked lists, trees, graphs).

A second, orthogonal cut is primitive types (int, char, bool, float, pointer) which the hardware understands directly, versus composite / abstract structures built out of them. An Abstract Data Type (ADT) is the interface only — e.g. a Stack promises push/pop/peek — while the data structure is the concrete implementation (a stack can be backed by an array or a linked list). Interviewers care that you keep these separate.

Worked example: the same task, three layouts, operations counted

Task: store the sequence [10, 20, 30, 40, 50] and then insert 25 at index 2 (so it sits between 20 and 30). Let's count the actual work.

• Contiguous array. To keep elements packed, we must shift 30, 40, 50 one slot right before writing 25. That is 3 element moves for a 5-element list. In general, inserting at the front of an n-element array costs n moves — O(n). But reading index 2 is one address computation, base + 2 × size — O(1).
• Singly linked list. Reaching index 2 means walking node-by-node from the head: node 0 → node 1 → node 2, that's 2 pointer hops. The insert itself is then 2 pointer writes (new node points to node 2; node 1 points to new node) — no shifting at all. Random access is O(n), but splicing once you hold the spot is O(1).
• Hash table (keyed by value). If instead the question were "is 30 present?", a hash table computes hash(30) mod capacity and probes one bucket — expected ~1 comparison, O(1) average. The array would scan up to 5 elements — O(n).

Notice no structure won every line. The array paid 3 moves so future reads stay O(1); the list paid 2 hops to make the write O(1); the hash traded ordering away entirely to make membership O(1). That trade is the essence of the topic.

Common pitfalls and what an interviewer probes

• Confusing ADT with implementation. "Use a stack" is a contract, not a layout. Expect "how would you implement it, and what changes if it's array-backed vs. list-backed?" (array-backed can need resizing; list-backed uses more memory per element but never resizes).
• Quoting average as if it were worst. Hash-table lookup is O(1) average but O(n) worst case under adversarial collisions; a dynamic array append is O(1) amortised but the individual resize is O(n). Say which one you mean.
• Ignoring the cache. Two structures with identical Big-O can differ 10× in practice: arrays are contiguous and prefetch-friendly, while linked lists chase pointers all over the heap, causing cache misses. Interviewers reward mentioning this.
• Forgetting the hidden costs of "O(1)". A dynamic array's O(1) append hides occasional doubling-and-copy; a balanced tree's O(log n) hides rotation bookkeeping.
• Space vs. time. A trie gives O(m) prefix lookup (m = key length) but can explode memory; a hash set is compact but loses ordering and prefix queries.

When it matters in practice + trade-offs vs. neighbouring classes

Pick the structure by the operation you repeat most, then check the others don't become disqualifying.

• Frequent random reads by index, rare inserts → array / dynamic array. O(1) read, O(n) middle-insert. Neighbour: a linked list would make reads O(n), a strictly worse trade here.
• Frequent insert/delete at ends or arbitrary spliced positions you already hold → linked list or deque. O(1) splice vs. the array's O(n) shift. You pay with O(n) search and worse locality.
• Keyed lookup, no ordering needed → hash map/set. O(1) average vs. a balanced tree's O(log n). Choose the tree instead when you need sorted iteration, range queries, or a hard worst-case guarantee — the tree's O(log n) is always true, the hash's O(1) is only average.
• Always-fastest min/max, streaming priorities → heap: O(log n) push/pop, O(1) peek. A sorted array gives O(1) peek but O(n) insert; an unsorted array gives O(1) insert but O(n) find-min.

The recurring pattern: constant < logarithmic < linear. Moving up a class buys you a capability (ordering, unbounded growth, cheap membership) and you accept the higher cost only on the operations you do rarely.

Key takeaways

• A data structure is layout + operations; choosing one means choosing which operations are cheap and accepting that others get expensive — there is no free lunch.
• Classify along linear vs. non-linear and contiguous vs. linked; keep the ADT (interface) separate from its concrete implementation.
• Always state best / average / worst explicitly — hash O(1) average but O(n) worst; dynamic-array append O(1) amortised; balanced-tree O(log n) guaranteed.
• Big-O ties are broken in the real world by cache locality and hidden constants: contiguous beats pointer-chasing even at equal asymptotics.