Data Structures: Types, Operations, Complexity, and Worked Examples

You may know arrays, stacks, and trees but struggle to explain why one representation fits a problem. The deciding factor is the workload: indexed reads, searches, edits, growth, and worst-case guarantees. The same values can favour different structures when that operation mix changes.

Data structures: meaning, purpose, and the ADT distinction

A data structure organises values, relationships, and supported operations. The sequence 12, 7, 25, 3, 18 can occupy consecutive array slots, form linked nodes, or follow a tree ordering rule. The values stay the same, but operation costs change.

Four terms must remain separate:

• A value is an item such as 12.

• A data type such as int defines valid values and operations.

• An abstract data type (ADT) defines behaviour. A stack offers push, pop, and top.

• An implementation realises that behaviour with an array or linked nodes.

Stacks and queues describe rules of use, not compulsory representations. Ask which operations dominate, what order is required, whether growth is predictable, and which worst-case guarantees matter.

Data structure types without blurred categories

Primitive values such as int 12 are building blocks; composite structures organise them. Arrays, linked lists, stacks, and queues are linear. Trees and graphs are non-linear. Arrays use contiguous storage; linked lists and many trees are pointer-based.

Hash tables map keys to buckets. A linear or non-linear label hides how hashing and collision policy locate keys.

An array can have fixed allocated capacity. A dynamic array grows by allocating a larger block and copying elements. A linked list grows node by node but carries link overhead.

Data structure operations and complexity

Read each bound with its condition:

Big O omits constants, locality, allocation cost, and pointer memory. Count moves, comparisons, visits, and link writes first.

Array versus linked list: one workload, four operations

Use zero-based A = [12, 7, 25, 3, 18], size 5, capacity 8, and the logically identical list 12 -> 7 -> 25 -> 3 -> 18. Assume the array has spare capacity and the list stores both head and tail references. The workload is: read index 4, append 10, delete the first value, then read index 3.

For the array, index 4 returns 18 in one indexed read. Appending 10 writes A[5] once. Deleting the front value 12 shifts 7, 25, 3, 18, 10 five slots left, producing [7, 25, 3, 18, 10]. The final index-3 read returns 18. Across the workload, the array performs two indexed reads, one append write, and five shifts; no resize occurs.

For the linked list, reading logical index 4 visits 12, 7, 25, 3, 18. With a tail reference, appending 10 writes oldTail.next = new and then tail = new. Deleting the front value replaces head with the node holding 7. The final index-3 read visits 7, 25, 3, 18 and returns 18. Thus the two indexed reads cost nine node visits, while the append and front deletion avoid array shifts.

The counts are different kinds of work, so adding visits, writes, and shifts would create a meaningless universal score. Repeated random indexed reads favour the array. Repeated appends plus front deletions favour the linked list when a tail reference is retained. If the array is full or the list has no tail reference, the preconditions and costs change.

Core data structures through short traces

For a stack, run push(12), push(7), push(25). Then pop() returns 25 and leaves top 7: last in, first out. For a queue, run enqueue(12), enqueue(7), enqueue(25). Then dequeue() returns 12 and leaves front 7: first in, first out.

Insert 12, 7, 25, 3, 18 into a BST. Root 12 gets left child 7 and right child 25; 3 goes left of 7, and 18 left of 25. Searching for 18 follows 12 -> 25 -> 18. An arbitrary binary tree need not obey this ordering rule. Study the invariant in Binary Trees and Binary Search Trees.

With h(x) = x mod 7, the buckets are 12 -> 5, 7 -> 0, 25 -> 4, 3 -> 3, and 18 -> 4. The 25 and 18 collision needs chaining or probing, so collision handling and load factor affect lookup.

Choosing a data structure: workload first

Choose a dynamic array for indexed reads and frequent appends; a linked list when traversal is acceptable and known-node edits matter; a stack for undo or nested calls; a queue for arrival order; a hash set or map for membership or key lookup; a balanced tree for ordered lookup and ranges; and a graph for many-to-many relationships.

Also check data size, memory, locality, duplicates, order preservation, library guarantees, mutations, and acceptable average-case behaviour. State the operation mix first.

Four common traps expose missing conditions:

• Linked-list deletion is always O(1). Target discovery was omitted. Count traversal unless the node and predecessor are known.

• Every binary tree is ordered. Search reasoning fails without the BST invariant. Verify it.

• Amortised append means every append is constant-time. Resizing can cost O(n). Separate amortised and worst cases.

• One best complexity cell decides everything. Memory and the remaining workload vanish. Compare the full operation profile.

Data structures in GATE questions and interviews

GATE-style work commonly asks you to trace operations, infer a final structure, compare bounds under stated conditions, or select a representation for an operation profile. The GATE CS Exam Preparation category gives the broader path, while Data Structures MCQs offers focused practice.

In an interview: clarify operations and constraints, justify the structure, state conditional time and space costs, then test edge cases. Mention indexed access, shifts, traversal, pointer updates, resizing, and empty or single-node cases before coding.

Capacity and node-reference checks expose the remaining cost conditions. If array capacity is 5 before inserting 10, allocate a larger block and resize-copy before completing the shifts. If node 7 and its predecessor are already referenced, target discovery disappears and only constant-time link changes remain.

Data structures: the short version and next step

A data structure is a representation chosen for an operation profile. ADT behaviour differs from implementation. Complexity claims require conditions. The array-list trace shows why access patterns matter.

For a five-minute revision, recreate the operation table, then rerun 12, 7, 25, 3, 18 without looking. For GATE-focused subject study, GATE Guidance by Sanchit Sir is a structured route. For coding-round implementation practice, use DSA using Java. Begin with the operations, state the conditions, then choose the representation.