Linked list Vs array : Difference


Difference Between array and Linked List : Array Vs Linked List

Difference between Array and Linked List

1. Access :Random / Sequential

  • Stack 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.

2 . Memory Structure :

  • Stack is stored in contiguous Memory Locations , i.e Suppose first element is Stored at 2000 then Second Integer element will be stored at 2002 .
  • But It is not necessary 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.

3 . Insertion / 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 List 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 Stack . i.e at the time when Programmer is Writing Program
  • In Linked list memory can be allocated at Run-Time , i.e After executing Program
  • Stack uses Static Memory Allocation and Linked List Uses Dynamic Memory Allocation
  • Dynamic Memory allocation functions – malloc,calloc,delete etc…