🔁Data Structures Unit 2 Review

Arrays and linked lists are the two foundational data structures you'll compare everything else against. Arrays give you fast random access but come with rigid sizing and costly insertions. Linked lists offer flexible sizing and cheap insertions but force you to traverse sequentially. Understanding the trade-offs between them is the key to picking the right structure for a given problem.

Arrays vs Linked Lists

Arrays store elements in contiguous memory, which means every element sits right next to the previous one. This layout is what makes index-based access so fast.

Access any element directly by its index in $O(1)$ time
Size is fixed at creation. You can't grow or shrink an array without allocating a new one and copying elements over.
Inserting or deleting in the middle is expensive. Removing the 5th element from a 100-element array means shifting the remaining 95 elements down one position, costing $O(n)$ time.

Linked lists store elements as individual nodes scattered across memory. Each node holds its data plus a pointer to the next node (and in doubly-linked lists, a pointer to the previous node too).

Accessing the $k$ th element requires traversing from the head, one node at a time: $O(n)$
Size grows and shrinks dynamically. You allocate a new node only when you need one.
Inserting or deleting a node is $O(1)$ once you already have a reference to the correct position, since you're just updating pointers. Finding that position still costs $O(n)$ if you have to search for it.
Each node carries extra memory overhead for its pointer(s).

Time and Space Complexity Comparison

Operation	Array	Linked List
Access by index	$O(1)$	$O(n)$
Search (unsorted)	$O(n)$	$O(n)$
Search (sorted)	$O(\log n)$ (binary search)	$O(n)$ (binary search not possible)
Insert/Delete at known position	$O(n)$ (shifting required)	$O(1)$ (pointer update only)
Insert/Delete at end	$O(1)$ (if space available)	$O(1)$ (with tail pointer)
Memory layout	Contiguous, fixed allocation	Non-contiguous, per-node allocation
Space trade-offs: An array of size 100 that only holds 50 elements wastes half its allocated memory. A linked list with 50 nodes uses exactly 50 nodes' worth of memory, but each node is larger than a plain array element because it also stores pointer(s). For a singly-linked list, that's one extra pointer per node; for a doubly-linked list, it's two.

Data Structure Selection

Choose an array when:

The data size is known in advance and doesn't change much
You need random access (e.g., jumping directly to the 10th element)
The data is dense and insertions/deletions in the middle are rare

Choose a linked list when:

The data size is unknown or changes frequently
Sequential access is sufficient (e.g., processing every element from start to finish)
You need frequent insertions or deletions at arbitrary positions, such as maintaining a sorted list with constant additions and removals

Arrays vs linked lists, ASIC-System on Chip-VLSI Design: June 2013

Adapting Algorithms Between Data Structures

Sometimes you'll need to swap one structure for the other. Here's a systematic approach:

Identify the problem's requirements. What are the access patterns (random vs. sequential)? How often do insertions and deletions happen? What are the memory constraints?
Analyze the current algorithm. Which operations dominate the runtime? Where are the bottlenecks?
Modify the algorithm for the new structure:
- Array → Linked list: Replace index-based access with pointer traversal. Handle dynamic node allocation. Swap element-shifting logic for pointer updates.
- Linked list → Array: Replace traversal with direct indexing. Determine an appropriate array size upfront. Add shifting logic for insertions and deletions.
Evaluate the complexity trade-offs. Switching from an array to a linked list might speed up insertions from $O(n)$ to $O(1)$ but slow down access from $O(1)$ to $O(n)$ . Make sure the trade-off actually helps your use case.
Test for correctness and benchmark performance to confirm the change was worthwhile.

Algorithmic Efficiency

How Data Structure Choice Affects Efficiency

The data structure you pick shapes the performance of every algorithm that uses it. Two things to keep in mind:

Time-space trade-off. Arrays generally give faster access but can waste memory with fixed-size allocation. Linked lists use memory more precisely but pay for it with slower traversal and extra pointer storage. The right choice depends on which resource matters more for your problem.

Asymptotic analysis with Big O notation is how you compare these trade-offs formally. Focus on the dominant term and the worst-case scenario. An algorithm running in $O(n)$ on an array will outperform one running in $O(n^2)$ on a linked list for large inputs, even if the linked list version is simpler to implement. Always consider how performance scales as input size grows.

A common mistake: assuming linked list insertion is always $O(1)$ . It's $O(1)$ only if you already have a pointer to the insertion point. If you need to find that point first, the search adds $O(n)$ , making the total operation $O(n)$ .

🔁Data Structures Unit 2 Review