Data-Structures

An array stores items of one type in equal slots next to each other in memory, but a Python list can grow and hold items of any type. In this chapter, we start from memory as one long row of bytes and build up arrays, the stack and the heap, pointers, dynamic arrays like Java’s ArrayList, CPython’s list, and linked lists. Then we reason through what each operation costs in an array, a list, and a linked list, and how those costs add up in a coding interview.

A function with one loop removes duplicates from a thousand items in 2.5 ms and from a hundred thousand in 27 seconds. In this chapter, we count steps instead of seconds to find out why: the growth rates from constant to factorial, the time and space complexity of every line, Big-O, Big Omega, and Big Theta with best, worst, and average cases, and amortized cost. We also turn a coding problem’s input size into a time budget.