Arrays & Strings
Beginner · 14 min read · Data Structures Basics, Linear Structures
Contiguous memory, O(1) indexing, dynamic arrays that double, 2D arrays and immutable strings.
The array is the simplest data structure and the one everything else is built on. Stacks, queues, heaps and hash tables are arrays underneath. It's a row of numbered boxes, side by side in memory. Understand three facts about it and most of DSA's cost analysis follows:
Picture it
How it works
When you write new int[7], Java reserves one contiguous block big enough for 7 ints (4 bytes each) and fills it with zeros. The variable holds the block's starting address. Element i is at:
Types of array
ArrayList keeps a backing array with some spare capacity. When it's full, it allocates a bigger array and copies everything over:
Operations and their cost
Patterns that use arrays and strings
Interview questions
- Why is accessing an array element O(1)?
- ArrayList sometimes copies its whole array when you add an element. Why is add still considered O(1)?
Further reading
Key takeaways
- An array is one contiguous block, so a[i] is an address calculation: O(1).
- Inserting or deleting in the middle shifts elements: O(n). Appending at the end is O(1) (amortised for ArrayList).
- Dynamic arrays grow by a constant factor, so total copying stays O(n).
- Strings are immutable: build them with StringBuilder, and compare with equals.
- Stacks, queues, heaps and hash tables are all arrays underneath.