Course contentsShow
← Computer Science
Lesson 310 of 2,8727. Introduction to Complexity AnalysisFree lesson

Space Complexity of Common Data Structures

Comparing space requirements of arrays, linked lists, trees, and hash tables.

Space Complexity of Common Data Structures

What you'll learn: How arrays, linked lists, trees, and hash tables differ in their memory requirements.

Now that you understand space complexity notation, let's compare how much memory different data structures actually consume to store the same amount of data.

Arrays

Arrays store elements in contiguous memory blocks. For n elements, an array requires O(n) space—just enough room for the elements themselves. No extra pointers or metadata needed per element. This makes arrays extremely memory-efficient.

Analogy: Like parking cars bumper-to-bumper in a lot—you only need space for the cars.

Linked Lists

Linked lists store elements in separate nodes, where each node holds both the data and a pointer to the next node. For n elements, you need O(n) space, but with higher constant factors than arrays. Each element carries extra "baggage" (the pointer).

Analogy: Like parking cars with a sign on each car pointing to the next one—you need space for cars plus signs.

Trees

Binary trees store elements in nodes with pointers to left and right children. For n nodes, space is O(n), but each node now carries two pointers. More complex trees (like B-trees) may have even more pointers per node, increasing the constant factor further.

Hash Tables

Hash tables use an array plus linked lists (or other structures) to handle collisions. For n elements, they typically require O(n) space, but the underlying array is often larger than n to maintain efficiency. If the table is 50% full, you're actually using 2n space—still O(n), but with a notable constant multiplier.

Key Takeaway: Arrays are the most space-efficient at O(n) with minimal overhead, while linked lists, trees, and hash tables also use O(n) space but with higher constant factors due to storing additional pointers or maintaining extra capacity.