Data Structures and Algorithms · Linear structures

Arrays

A fixed-layout, contiguous block of memory where any index is reached in constant time.

Also known as: dynamic arrays, static arrays, index access.

Start a lesson on Arrays

Learn first

• Complexity analysis: Describing how an algorithm's running time or memory grows as input size grows, using Big-O.

Leads to

• Linked lists: Nodes scattered in memory, each pointing to the next, trading fast indexing for cheap insertion.
• Binary search: Repeatedly halving a sorted range to find a target in logarithmic time.
• Elementary comparison sorts: The simple O(n squared) sorts, bubble, insertion, selection, that compare and swap pairs of elements.
• Graph representations: Storing a graph's vertices and edges as an adjacency matrix or adjacency list.
• Fenwick trees: A compact array-based structure that answers prefix-sum queries in logarithmic time.
• Two pointers: Walking two indices through a sequence at once to avoid a nested loop.
• String matching algorithms: Finding all occurrences of a pattern inside a larger text faster than checking every position.

Related topics

• Two pointers: Walking two indices through a sequence at once to avoid a nested loop.
• Binary search: Repeatedly halving a sorted range to find a target in logarithmic time.