What is the difference between an array and a linked list? When would you use one over the other?

Question

Accepted Answer

An array and a linked list are two fundamental data structures with different characteristics.

An array stores elements contiguously in memory. Each element has an index and can be accessed directly in constant time, meaning O of one. The size is generally fixed at creation. Insertion or deletion in the middle of the array is costly because all subsequent elements must be shifted, giving a complexity of O of n.

A linked list stores elements in nodes scattered throughout memory. Each node contains a value and a pointer to the next node. Accessing a specific element requires traversing the list from the beginning, so the complexity is O of n. However, insertion or deletion is fast if you already have a reference to the node, as you only need to modify pointers.

Use an array when you need frequent access by index, when the size is known in advance, or when you traverse data sequentially. Arrays are also more efficient in terms of memory cache.

Use a linked list when you perform many insertions or deletions in the middle of the collection, when the size varies frequently, or when you do not need random access.

In practice, modern languages like Python or Java often use hybrid structures like ArrayList that offer the best of both worlds.