Linked List vs Array

Difference between Linked List vs Array

An array is defined as a list of values or set of elements with the same data type of each element in it. An array is a data structure that is stored in continuous memory allocation with the initialization of the fixed size of the array is defined at the time of declaration. A linked list is also a data structure which is defined as a collection of elements with the same data type which is an ordered set of elements that are not in any consecutive memory locations and each element is considered as a node in which it stores data and the address to the next node which is said to be a pointer to the next node and hence these elements are connected using these pointers.

Head to Head Comparison between Linked List vs Array (Infographics)

Below are the top 10 differences between Linked List vs Array:

Key Differences between Linked List vs Array

Some of the key differences between Linked List vs Array are given below:

Insertion of Elements

In Array, the insertion of elements is very simple and easy as it uses array indices which starts the indexing with 0, and hence it allows random access to the elements for example if in the array we want to insert an element at 3rd location where the index will be “2” so we just need to move the elements from 3rd element which was in index “2” ad becomes index “3” after insertion of the new element. Whereas in the linked list also the insertion is simple and easy if we know the pointers to each element or the addresses for example if we are inserting an element at 3rd location then we need to change the addresses of the element at the 2nd location which should now contain the address of the new element and the new element address should contain the address of the element of 4th location which was previously in 3rd location.

Time and Space Consumption

In Array, the time taken for inserting and deleting elements is more as it uses contiguous memory location which is always fixed in size at the initialization where it cannot be changed later and therefore the space used is to store the entire array and not single elements which require less space. Whereas, the time taken by the linked list for inserting and deleting elements is faster than the array as it stores any new element in the first free space which is available in memory and uses separate memory to store its pointers also and hence the space utilization is more compared to the array.

Access and Execution Time

An Array uses array indices as addresses ad continuous memory location in storing elements it can be accessed randomly and hence modifying certain elements can be faster which makes faster execution time. Whereas, linked list uses pointers or it stores the reference to the next element it needs to traverse all the before elements to access any element which uses sequential access as it cannot be stored in the contiguous memory location and therefore sometimes there may be a delay in executing the linked lists. But still, it depends on the operations which we are applying to which data structure because some are faster in an array and some are faster in linked lists.

Linked List vs Array Comparison Table

Comparison between Linked List vs Array is given below:

S. NO	Linked list	Array
1	It is a data structure of the set of elements that contain two parts in it such as data and address which is a pointer to the next element and each element is of the same data type, unlike simple lists which are generic.	It is also a data structure that stores a collection of elements with the same data type and it only stores values unlike a linked list it does not have any data and address as its values.
2	In the Linked list each element is considered as one single node where these nodes are connected using pointers which are the address value of the next node and other than address it also stored data for each node.	In Array, there is no such node concept as it contains only a set of values in it and is hence used as a default data structure in many modern programming languages.
3	Linked lists cannot store elements in a contiguous memory location as they are less rigid in storage structure than Array ad therefore they use references to next elements additionally when storing the elements in Linked lists.	Arrays can store their elements in a contiguous memory location which each element are indicated using indices which can be said as addresses for each element and this makes it simple to access the elements using these array indices.
4	In a linked list random access to the elements is impossible as it uses the pointers which are connected to the elements sequentially.	In Array, random access is possible as it uses array indices as addresses to access instead of pointers.
5	The liked list uses dynamic memory allocation as it can allocate memory at the run time.	The array uses static memory allocation as it can allocate memory at compile time.
6	In the linked list the elements or nodes can be added or deleted whenever required and even after the declaration of the linked list.	In array the declaration of elements once done cannot be changed and hence it has a fixed size during initialization.
7	It can use small blocks of free space as it stores different elements at a different location and also the space consumption is more as it needs to store pointer also.	It uses large blocks of free space to store the entire array and not single elements and hence the space consumption is less overall than the linked list.
8	Linked lists can be defined as a simple liked lists, circular linked lists,s or doubly-linked lists.	Arrays can be defined in a one-dimensional array, two-dimensional array, or multidimensional array.
9	In the linked list there is no need to specify the size at the initialization as it grows with run-time allocation.	In Array, the size of the array is defined at the initialization which is fixed as it cannot be changed as in the linked list.
10	In linked lists, the memory is usually allocated in a heap section manner.	In Array, the memory is allocated in a stack section manner.

Conclusion

In this article, we conclude that array and liked lists both are types of data structure and both are linear data structures. It cannot be said that a linked list is best than an array or vice versa as each has different methods and operations which are better in their types. Therefore it all depends on developers to check with advantages and disadvantages of implementation over each concept and also look at memory utilization, requirements used in each of these concepts.

Recommended Articles

This is a guide to Linked List vs Array. Here we also discuss the Linked List vs Array key differences with infographics and a comparison table. You may also have a look at the following articles to learn more –

1. Array vs ArrayList
2. jQuery array length
3. Java Vector vs ArrayList
4. C# Array vs List