Question - How will you explain a linked list and an array?
Answer -
An array is a datatype which is widely implemented as a default type, in almost all the modern programming languages. It is used to store data of a similar type.
But there are many use-cases where we don't know the quantity of data to be stored. For such cases, advanced data structures are required, and one such data structure is linked list.
There are some points which explain how the linked list is different from an array:
| ARRAY | LINKED LIST |
- An array is a group of elements of a similar data type.
| - Linked List is an ordered group of elements of the same type, which are connected using pointers.
|
- Elements are stored consecutively in the memory.
| - New elements can be stored anywhere in memory.
|
- An Array supports Random Access. It means that the elements can be accessed directly using their index value, like arr[0] for 1st element, arr[5] for 6th element, etc.
As a result, accessing elements in an array is fast with constant time complexity of O(1). | - Linked List supports Sequential Access. It means that we have to traverse the complete linked list, up to that element sequentially which element/node we want to access in a linked list.
To access the nth element of a linked list, the time complexity is O(n). |
- Memory is allocated at compile time as soon as the array is declared. It is known as Static Memory Allocation.
| - Memory is allocated at runtime, whenever a new node is added. It is known as Dynamic Memory Allocation.
|
- Insertion and Deletion operation takes more time in the array, as the memory locations are consecutive and fixed.
| - In case of a linked list, a new element is stored at the first free available memory location.
Thus, Insertion and Deletion operations are fast in the linked list. |
- Size of the array must be declared at the time of array declaration.
| - Size of a Linked list is variable. It grows at runtime whenever nodes are added to it.
|