Arrays and Lists
Indexing, traversal and dynamic arrays.
An array stores a sequence of values in consecutive memory, so any element can be reached instantly by its index. Most languages count from 0, so an array of length has indices to . Reading or writing `a[i]` takes constant time, which is the array's great strength.
The cost comes with inserting or deleting in the middle, which shifts every later element. Dynamic arrays (Python lists, Java ArrayList, JavaScript arrays) grow automatically by allocating a larger block and copying, which keeps appends fast on average. Linked lists make insertion cheap but give up instant indexing.
Key ideas
- Index access: ; search an unsorted array: .
- Insert or delete in the middle: because of shifting.
- Appending to a dynamic array is amortised.
- Traverse with a loop over indices to .
Worked example
An array holds `[4, 9, 2, 7, 5]`. What are `a[1]`, `a[4]` and the sum of all elements?
- Indices start at 0: `a[0] = 4`, so `a[1] = 9`.
- The last index is : `a[4] = 5`.
- Sum: .
Answer: `a[1] = 9`, `a[4] = 5`, sum
Common mistakes
- Accessing index , one past the end.
- Modifying a list while looping over it.
- Assuming insertion at the front is as cheap as appending.
Practice questions
Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.
1.What is the last valid index of an array of length 12?
Show answer
2.Average of `[3, 8, 10, 15]`.
Show answer
3.Inserting at index 0 of a 1000-element array shifts how many elements?
Show answer