Data Structures Review

Why data structure choice matters

Imagine storing 10,000 student records. If you pick the wrong structure, a simple task like inserting one new record can become expensive. A data structure is the shape you give data so operations like search, insert, delete, and traversal become easier.

Think of it like organizing books:

• Array = books lined up on fixed shelves with numbered positions
• Linked list = each book tells you where the next book is
• Tree = books arranged like a family hierarchy, from broad categories to specific titles

When reviewing data structures, don't just memorize definitions. Ask:

• How fast is access?
• How easy is insertion or deletion?
• How much memory overhead is added?
• Does the data have a natural hierarchy?

That question-first mindset is what turns theory into problem-solving.

Arrays: simple, fast, and position-based

An array stores elements in contiguous memory, which makes indexed lookup very efficient. If marks[4] is needed, the system can jump straight there instead of checking earlier elements one by one.

Typical strengths:

• Fast access by index: often O(1)
• Good for fixed-size or predictable-size data
• Easy to traverse sequentially

Typical weakness:

• Inserting in the middle may require shifting many elements

If 1,000 values are stored and you insert at position 100, about 900 elements may move. That is why insertion can be O(n).

int marks[5] = {78, 82, 91, 67, 88};
printf("%d", marks[2]); // prints 91

Use arrays when position matters more than frequent structural changes.

Linked lists: flexible shape, slower access

A linked list is like a treasure hunt: each node stores data and a pointer to the next node. Unlike arrays, elements do not need to sit next to each other in memory.

This gives linked lists a big advantage:

• Easy insertion/deletion at known positions, especially near the head
• Dynamic size without pre-deciding capacity

But there is a trade-off:

• No direct indexing like list[50]
• To reach the 50th node, you must follow links step by step

So access is usually O(n), while insertion at the beginning is often O(1).

Real example: a music playlist where songs are frequently added or removed between existing songs. The order changes often, so flexibility matters more than instant indexed access.

Trees: data with levels and relationships

A tree organizes data hierarchically. It has a root, children, and leaf nodes. If arrays are rows of lockers and linked lists are chains, trees are branching roads.

Trees are useful when data has levels:

• File systems: C:/Users/Riya/Documents
• Company structure: CEO → Manager → Employee
• Searching in ordered data using structures like binary search trees

In a binary tree, each node can have at most two children. A balanced search tree can reduce search time compared to scanning a list one by one. For 15 ordered values, a balanced tree may find an item in about 4 comparisons, while linear search might take up to 15.

Choose trees when relationships, ordering, or divide-and-search behavior matter.