Monday, 26 August 2013

Differences between arrays and linked lists

1) Major difference lies in the Memory Structure:
Arrays-contiguous memory allocation and if contiguous memory available is less than the total array requirement, then the array cant be allotted the memory.

But It is not necessary in the case of linked list to store next element at the Consecutive memory Location .
Element is stored at any available Location , but the Pointer to that memory location is stored in Previous Node.

2) Accessing the elements:
Array elements can be randomly Accessed using Subscript Variable
e.g a[0],a[1],a[3] can be randomly accessed
While in Linked List We have to traverse through the Linked List for Accessing Element. So O(n) Time required for Accessing Element .
Generally in linked List, elements are accessed Sequentially.

3) Insertion and Deletion
As the Array elements are stored in Consecutive memory Locations, so While Inserting elements ,we have to create space for Insertion. So, more time required for Creating space and Inserting Element. Similarly, we have to Delete the Element from given Location and then Shift All successive elements up by 1 position.

In Linked Lists, we have to Just Change the Pointer address field (Pointer),So Insertion and Deletion Operations are quite easy to implement.

4) Memory Allocation :
Memory Should be allocated at Compile-Time in array. i.e at the time when Programmer is Writing Program. => fixed size
In Linked list, memory can be allocated at Run-Time , i.e after executing Program.

-> Arrays uses Static Memory Allocation and Linked List Uses Dynamic Memory Allocation.

Join me on Facebook