🔁Data Structures Unit 2 Review

Arrays store elements in contiguous memory locations, meaning each element sits right next to the previous one in memory. This layout is what gives arrays their biggest advantage: you can jump directly to any element using its index, without scanning through everything before it.

Static arrays have fixed sizes set at compile time, while dynamic arrays can grow or shrink at runtime. One-dimensional arrays store simple lists, and multi-dimensional arrays represent grids, matrices, or tables.

Basic Array Operations

Access is the simplest operation. Because elements are stored contiguously, the computer can calculate exactly where any element lives using the formula:

$\text{address} = \text{base\_address} + \text{index} \times \text{element\_size}$

This makes access $O(1)$ , regardless of array size.

Insertion adds an element at a specific index. To make room, every element from that index onward must shift one position to the right.

For example, inserting 3 at index 2 in [1, 2, 4, 5]:

Shift 5 from index 3 to index 4
Shift 4 from index 2 to index 3
Place 3 at index 2
Result: [1, 2, 3, 4, 5]

Worst-case time complexity: $O(n)$ , because inserting at index 0 requires shifting all $n$ elements. Inserting at the end, though, is $O(1)$ since no shifting is needed.

Deletion removes an element at a specific index. Elements after the deleted one shift left to fill the gap.

For example, deleting index 2 in [1, 2, 3, 4, 5]:

Shift 4 from index 3 to index 2
Shift 5 from index 4 to index 3
Result: [1, 2, 4, 5]

Worst-case time complexity: $O(n)$ , for the same shifting reason. Deletion at the end is $O(1)$ .

Traversal visits each element sequentially, typically with a loop like for (int i = 0; i < n; i++). Since every element is visited once, this is always $O(n)$ .

Time Complexity Summary

Operation	Best Case	Worst Case	Notes
Access by index	$O(1)$	$O(1)$	Direct calculation from base address
Search (unsorted)	$O(1)$	$O(n)$	Linear search; element might be first or last
Search (sorted)	$O(1)$	$O(\log n)$	Binary search halves the search space each step
Insert/Delete (end)	$O(1)$	$O(1)$	No shifting required
Insert/Delete (arbitrary)	$O(1)$	$O(n)$	Shifting elements dominates the cost
Traversal	$O(n)$	$O(n)$	Must visit every element

The key tradeoff with arrays: you get fast random access but pay for it with slow insertions and deletions in the middle.

Array Types and Applications

Basic array operations, Delete From Array function - LabVIEW Wiki

Static vs. Dynamic Arrays

Static arrays have a fixed size determined at compile time (e.g., int arr[10] in C++). Memory is allocated on the stack, which is fast but inflexible. If you need more space than you declared, you're out of luck.

Dynamic arrays can resize at runtime. Languages provide built-in implementations like vector in C++ and ArrayList in Java. Memory is allocated on the heap, which allows resizing but adds some overhead.

When a dynamic array runs out of capacity, it typically:

Allocates a new, larger block of memory (often double the current size)
Copies all existing elements to the new block
Frees the old block

That copy step is $O(n)$ , but it happens infrequently enough that appending to a dynamic array averages out to $O(1)$ per insertion. This is called amortized $O(1)$ .

One-Dimensional and Multi-Dimensional Arrays

One-dimensional arrays store a flat list of elements of the same type, accessed with a single index. Example: storing student grades as [85, 92, 78, 90], where arr[2] gives you 78.

Multi-dimensional arrays add extra dimensions. A 2D array is the most common, representing grids or matrices like a chessboard. For a 2D array [[1, 2], [3, 4]], you access elements with two indices: arr[1][0] returns 3 (second row, first column). Higher dimensions (3D, 4D) exist but are less common.

Common Array Applications

Searching: linear search on unsorted data, binary search on sorted data
Finding min/max: single traversal through the array
Sorting: algorithms like bubble sort, quicksort, and mergesort all operate on arrays
Building other data structures: stacks, queues, and hash tables are frequently implemented with arrays as the underlying storage

🔁Data Structures Unit 2 Review