Linked lists and arrays are two commonly used data structures. Each has its own advantages and disadvantages, and is suitable for specific scenarios than others. In this article we will compare the two data structures on various basis.
Definitions
An array is a data structure that stores a fixed-size collection of elements of the same type. The elements are stored contiguously in memory and each element can be accessed using an index. Lists in Python are implemented through arrays.
arr = [‘Java’, ‘Python’, ‘Ruby’, ‘C++’] # an array
#get an element at specific index
print(arr[2]) # the element at the third position
On the other hand, a linked list is a linear data structure in which elements are connected through references. Each element, also known as a node , contains a data field and a reference to the next node in the list. Basically, a node in a linked list will look as shown below:
class Node:
def __init__ (self, element, nxt):
self.data = element #Users element
self.next = nxt #The next node in the list
The data instance attribute keeps the value of the element stored by the node, while the nextattribute stores a reference to the next node in the list.
Insertion and Deletion
Arrays
Insertion and deletion in an array can be expensive, especially if the size is large and the element is inserted or deleted from the beginning or middle of the array.
When you insert or delete an element at an arbitrary position in an array, each elements after that position shifts.
In case with insertion, the elements shifts to the right, creating a gap for the new element to be inserted. The following figure illustrates this better.
With deletion, the elements shifts to the left to occupy the space that has been left by the removed element.
Insertion and deletion in arrays have a worst case time complexity of O(n), as all the elements after the insertion or deletion shifts.This can be costly for large arrays with a lot of elements.
The only exception is when insertion or deletion happens at the end of the array, as there is no need to shift any elements. Insertion and deletion at the last position has a time complexity of O(1). This makes the end of an array the best place to insert or delete elements if possible
Linked list
Insertion and deletion in a linked list is easier and much more efficient compared to in array. In a linked list, both insertion and deletion have a constant time complexity, O(1).
With insertion, the new element can be inserted at any position by just updating the relevant nodes to reference the new node. While with deletion, an element can simply be dereferenced and removed from the list without affecting the references of other nodes. This is because each node only has a reference to the next node, so removing one node does not affect the references of other nodes.
Accessing elements
Accessing elements in an array is much more efficient compared to in a linked list. The elements in arrays are stored in contagious memory locations, we can, therefore, directly access an element using its index. This ensures a constant time complexity(O(1)) regardless of the size of the array or the location of the element to be accessed.
On the other hand, elements in linked list are scattered throughout the memory, thus we have to traverse the entire list to access a specific element. Since the elements are not stored contiguously we cannot use index to access an element, we have to traverse the list starting from the head node until we reach the desired element Thus, accessing elements has a worst case time complexity of O(n).
Memory allocation and efficiency
Arrays are more memory-efficient as they only require memory for the individual elements, and not for any additional references. However, they also have a fixed size that cannot be changed, this makes them less flexible and not very suitable for representing dynamic data.
A linked list requires extra memory to store the references, which can be disadvantageous if the list contains a large number of elements. On the better side, memory allocation for a linked list is dynamic, meaning new nodes can be allocated as and when needed. This makes linked lists flexible for adding or removing elements.
Summary
Array
Linked list
A collection of homogeneous items in which an item can be accessed using its index
A sequence of nodes where each node references the next node in the list.
Have a fixed size that is defined at declaration.
Are of dynamic size.
Faster access to elements as each element can be accessed with its index at a time complexity of O(1).
Accessing elements is inefficient and has a worst time complexity of O(n).
Insertion and deletion operations become more inefficient the closer you move to the beginning of the array. Both has a worst time complexity of O(n)
Very efficient insertion and deletion operations. Both operations have a time complexity of O(1) at any position.
Relatively less memory footprint as only the elements are stored.
More memory footprint, as references to other nodes have to be stored in addition to the actual element.
Related articles
Complexity Functions in algorithm analysis
Implement Stack data structure in Python
Implement Queue data structure in Python
