Interview Query | Linked Lists VS. Arrays - Data Structures and Algorithms Interview

Back to Data Structures and Algorithms Interview

Data Structures and Algorithms Interview

0 of 20 Completed

Linked Lists VS. Arrays

Both arrays and linked lists are sequential data structures that utilize similar operations. As such, most operations parallel each other—and ignoring the naming differences can be interchangeable, as long as we consider only the essential function and not the internal implementation.

If both data structures serve similar purposes, then why would we choose one over the other? Simply put, despite their similarities in function, each data structure incurs different costs, both in time and space, due to their inherently different implementations.

Let’s consider the add_first and emplace_front operations for example. Both append an element at the beginning of the list. However, while the linked list simply creates a ListNode and reassigns it as the new head, the array needs to move all the elements of the array by an offset of one before placing the new element at index zero.

Essentially, adding an element at the start of the list incurs different costs. The array, needing to offset all the elements of the list, effectively has an $O(n)$ time complexity. On the other hand, the linked list will have an $O(1)$ time complexity.

Now, let’s consider deletions at the end of the list. For an array, we can simply decrement the size. For a singly linked list, because we need to identify the new tail, we have to iterate through the entire list and assign as the new tail that node which falls before the current tail. On the other hand, for a doubly linked list, we can identify the new tail by simply accessing the previous element of the tail, i.e., tail.prev and set it as the new tail, we can have a total cost of $O(1)$ .

Let’s review the following table as a guide for the time complexities.

	add_first	add_last	add	pop_first	pop_last	pop	get
Array	amortized $O(n)$	amortized $O(1)$	amortized $O(n)$	amortized $O(n)$	amortized $O(1)$	amortized $O(n)$	$O(1)$
Singly Linked List	$O(1)$	$O(1)$	$O(n)$	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Doubly Linked List	$O(1)$	$O(1)$	$O(n/2)$	$O(1)$	$O(1)$	$O(n/2)$	$O(n/2)$

In this table, you might notice that Doubly Linked Lists have $O(n/2)$ operations. This is because we can start iterating from the start or end and we can choose which path to take depending on what operation needs to be performed. At most, this takes $n/2$ operations.

Another observation is that except for index access (get), doubly linked lists seem to be better in all aspects. If that’s the case, then why shouldn’t we opt for doubly linked lists all the time?

Well, aside from the computing cost, we also need to consider space as a cost.

Space as a Consideration

Arrays are incredibly light in space. An array can be fully functional with just the following attributes:

A contiguous chunk of memory to store the elements.
The size attribute (not necessary, but is common).
The capacity attribute (not necessary for fixed-length arrays).

Because of this, arrays can have a very light memory requirement in comparison to linked lists. However, they do carry significant overhead, especially when we have a dynamic array, since we need to have an overhead capacity (dynamic arrays tend to over-allocate).

On the other hand, because linked lists are dynamically allocated, they can seem cheaper in space (only allocating memory when needed). However, linked lists also need a place to store their neighbors.

As an example, a singly linked list needs to store the reference of the next neighbor. On the other hand, a doubly linked list takes this a step further and stores the reference of the prev neighbor as well.

Not only that, but because linked lists are dynamically allocated, the processor needs to assign new memory every time a new node is created which can make linked lists have higher constant overhead.

A Key Point For Interviewees

Use arrays as much as possible, especially if indexing is an important operation. However, for tasks that require frequent addition or deletion of elements, linked lists may be a better option.

Additional Reading: Cache Locality

Because arrays are stored contiguously, when we access an element in an array, there is a good chance that most of the elements in the array are stored inside the CPU as cache. Cache memory is orders of magnitude faster compared to the main memory (RAM). As such, for most modern devices, an array is almost always the correct data structure to use.

Well, aside from the computing cost, we also need to consider space as a cost.

Space as a Consideration

Arrays are incredibly light in space. An array can be fully functional with just the following attributes:

A contiguous chunk of memory to store the elements.
The size attribute (not necessary, but is common).
The capacity attribute (not necessary for fixed-length arrays).

Not only that, but because linked lists are dynamically allocated, the processor needs to assign new memory every time a new node is created which can make linked lists have higher constant overhead.

A Key Point For Interviewees

Use arrays as much as possible, especially if indexing is an important operation. However, for tasks that require frequent addition or deletion of elements, linked lists may be a better option.

Additional Reading: Cache Locality

Assessment 2: Pop Tail!

Assessment 3: Cyclic Detection

0%

Completed

You have 20 sections remaining on this learning path.