What are the differences between a Linked List and an Array?

Interview question: What are the differences between a Linked List and an Array?


Both Arrays and Linked Lists are data structures which allow for storage of data. They each have their own set of advantages and disadvantage and knowing when to use one versus the other is quite important.

Arrays:

1. Arrays are fixed in size, meaning you need to know how many elements ahead of time that the array can store. If the array has to grow above its maximum capacity, a new array will have to be allocated in memory, which can be quite expensive.

2. Arrays provide constant time access to any of its elements. It is possible to retrieve any element within an Array very quickly and efficiently.

3. Inserting new elements into a sorted Array is quite expensive. You have to find the index to insert into and then shift all the elements to the right, one position to the right, in the Array.

4. Deleting elements in a sorted Array is also quite expensive. Similar to adding new elements into the Array, you must find the index to delete and shift all the elements to the right, one position to the left.

Linked List:

1. Linked Lists are dynamic in size, and new elements can be added relatively inexpensively.

2. Linked Lists do no provide random access to its elements. You must traverse the list to find the element you are searching for. This contrasts to Arrays where elements can be retrieved in constant time. It also means you cannot perform a binary search on a Linked List.

3. Inserting or deleting elements from a Linked List is pretty trivial. You just have to update the prior node and next node references.

4. Compared to Arrays, Linked Lists also have additional memory overhead because each node has to keep track of a pointer to the next node in the list for singly linked lists, and pointers to the next and previous nodes for doubly linked lists.