Linked lists vs Arrays -Algorithms
Both Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime.
Let’s take a simplified took at what that means ,…
What are arrays?
An array can be simply defined as an ordered series or arrangement. From mathematicians to programmers use arrays for different purposes. But the main objective here is to store data. And that too in a way which is arranged so that its easier to access and get information through that stored data.
So the general idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value.
The base value is index 0 and the difference between the two indexes is the offset. which in other words , when we count the position of an array we start 0,1,2,3,4….. and not 1,2,3,4 .
For simplicity, we can think of an array as a group of children in a class where they are seated according to their index numbers of the register. where on each chair is placed a value (let’s say one of those children). Here, you can identify the location of any of those children by simply knowing the count of the chair they are seated on.
What are Linked Lists?
Linked List is a linear data structure which consists of group of nodes in a sequence. Each node holds its own data and the address of the next node hence forming a chain like structure.
Or
In simple words we can say in a linked list the elements contain the data for its own location and also for the next location in the list.
The best example for a linked list is a train. In a train in order to go from beginning of train carriage to the end, we have to pass through each and every carriage. And the doorway to each carriage lies on the previous one. hence each and every carriage in linked and cannot be accessed unless we pass through all linked carriages in order.
And this is the principal behind linked lists too. And there are 3 different implementations of Linked List available, they are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List,
We wont go through each of those linked lists types because our purpose here is to compare arrays with linked lists.
Linked List vs. Array
Array is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar types in a single place which makes it easier to find and access.
But there are many cases, like the one where we don’t know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is linked list.
Advantages of Arrays
- Array supports Random Access, which means elements can be accessed directly using their index
- Unlike linked lists we do not have to go through each and every element to access the element we need.
- Accessing elements in an array is fast with a constant time complexity of 0(1).
Disadvantages of Arrays
- In array, Insertion and Deletion operation takes more time, as the memory locations are consecutive and fixed.
- Size of the array must be specified at time of array declaration.
- Also if we want to add more data after we made the array and there is no space left for the new data, we will have to move the whole array to another place.
Advantages of Linked Lists
- In a linked list, new elements can be stored anywhere in the memory.
- Insertion and Deletion operations are fast in linked list.
- Size of a Linked list is variable. It grows at runtime, as more nodes are added to it.
Disadvantages of Linked Lists
- To access nth element of a linked list we have to sequentially traverse the complete linked list, up to that element.
- To access nth element of a linked list, time complexity is 0(1).
Both of these data types are useful in its own way and functionality. And is used in different scenarios where the specific functionality of one another is required.
