11. Arrays and Linked Lists (Comparison)

These are fundamental data structures that algorithms operate upon.

Arrays (Static or Dynamic)

• Concept: A collection of elements stored in contiguous (next to each other) memory locations.
• Pros: Fast lookups/access (O(1)) because the computer knows exactly where the element is based on the starting address and index.
• Cons: Adding or deleting elements in the middle is slow (O(N)) because all subsequent elements must be shifted.

Linked Lists

• Concept: A collection of nodes where each node contains the data and a reference (pointer) to the next node.
• Pros: Fast insertions and deletions (O(1)) once you have a pointer to the previous node, as you just update a pointer.
• Cons: Slow lookups/access (O(N)) because you must start at the beginning and traverse the list sequentially to find the N-th item.

Choosing the right structure is the first step in designing an efficient algorithm.