Array vs Linked List

Photo by Shubham Dhage on Unsplash

Data structures are one of the most fundamental concepts in computer science, yet most programmers put little time into thinking about how to best utilize the many different data structures. Be honest, how many times have you said “Screw it, just put it in a list.”? In some use cases, this kind of thinking is fine, especially if the list will never contain very many elements. At scale though, this thinking can cause massive slowdowns. It’s important to use the right tool for the job. Today, we will be looking at the two most basic data structures: arrays and linked lists. Both are ordered collections of items, where elements can be accessed by their index (sort of). Furthermore, the techniques used in both structures are foundational to more complex data structures as well. It’s hard to overstate the importance of understanding these two data structures.

Note: If you’re thinking “What the heck is an array?”, you may be more familiar with the list interface, which is often a higher-level abstraction of either an array or linked list, like in Python.

Arrays

You probably learned how to use an array when you first began to code but did you ever think about how they work under the hood? Depending on the language you use, the implementation may vary, but they all share the same core concepts under the hood:

1. Array elements are stored sequentially in memory.
2. Elements in an array must all be of the same type.
3. The size of an array is fixed upon creation.*

These three properties allow us to access any element in the array directly regardless of the size of the array. The process of accessing elements in a data structure based on their position in an ordered list is called “indexing”. Indexing arrays directly is extremely efficient and is the primary benefit of using arrays. However, arrays have a major downside. In order to achieve direct indexing, arrays must have fixed length and type. What happens if you need the array to hold more elements or shirk to conserve memory? Well, you have to allocate a new array, then transfer all of the elements. This is a very costly operation.

Array Doubling

To minimize the number of times we reallocate an array, we use a technique called array doubling. This technique involves expanding or shrinking an array by a factor of two whenever the array is full, or half-full respectively. This means that small arrays will be reallocated more often than large ones, but that’s okay because small arrays are much less costly to reallocate.

Linked Lists

Simply put, a linked list is a chain of elements such that each element is linked to the next element by holding a reference (pointer) to the next element in the sequence. Confused? Don’t worry, I was too when I first learned about linked lists. Hopefully this illustration will help.

To access any element in a linked list, we hold a reference to the first element, then walk down the chain until we reach the element that we want. This pattern makes adding or removing elements very efficient, especially at the beginning or end. The problem with linked lists, though, is that they aren’t very good at accessing elements in the list. In fact, the cost of accessing an element in the list is directly proportional to the number of elements in the list, on average. What happens if we want to access the very last element in the list? We have to walk through every other item in the list first. This is very expensive. We have an imperfect but valuable solution to this: doubly-linked lists.

Doubly Linked Lists

In a doubly-linked list, we hold a reference to both the beginning and end of the list and can traverse the list in both directions. This cuts the time to index an element nearly in half. While this is a huge improvement, it doesn’t change the fact that indexing an element is still very slow compared to an array.

Conclusion

Both arrays and linked lists are fundamental data structures that excel in different ways. Arrays are very fast when indexing, but can be inefficient when adding or removing elements. Linked lists are extremely fast when adding or removing elements, but not when indexing. Both data structures work well with smaller data sets, but when creating applications at scale, it's important to choose the structure that best fits your use case.

Please subscribe for more computer science content!