Arrays vs. Linked Lists
A classic tradeoff in computer science is whether to implement your data structure using an array or a linked data structure. Let's remind ourselves of some of the space and time tradeoffs between the two, since we will continue to use them in building new data structures in the coming weeks.
Watch the following video to remind yourself of the similarities and differences between arrays and linked lists:
To summarize:
Arrays
- Allow random (
O(1)) access to elements, which makes them amenable to techniques like binary search (since it requires jumping to specific points in the array) - Need to be stored in contiguous memory, so they are typically not resizable
- If you need to add more items to the array than its capacity would allow, you would need to create a new, larger array and copy all of the elements over (
O(n))
Linked lists
- Linked lists don't allow random access to elements; to find an item in the list, you generally must start at the head of the list and traverse as far as needed (
O(n)) - Doesn't need to be stored in contiguous memory. Instead, individual nodes can be stored anywhere on the memory heap, with pointers connecting nodes. Therefore, linked lists are not fixed-length
- Adding to the head or tail of the list is generally
O(1)