Difference Between Array and Linked List

Difference Between Array and Linked List : There are so many advantages and disadvantages between array and linked list and based on those factors I am trying to summarize the difference between array and linked list which are described as :

Basis Arrays Linked Lists
Insertion/Deletion in array and Linked List :
Easy or Difficult Insertions and deletions in array are difficult. Insertions and deletions in linked list can be done easily.
Movement of number of Elements It needs movements of elements for
insertion and deletion.
Insertion/Deletion at a particular index
requires shifting all elements after that
index by 1 position.
Linked list does not need movement of nodes for insertion and deletion as insertion/deletion at a particular index requires just changing the pointers.
Expensive Inserting a new element in an array of elements
is expensive as it requires shifting of all elements.For example, in a sorted list of array x[7]x[] = {2, 6, 10, 50, 90}

If you want to insert “7” in sorted order, then it
requires movements of all elements after
index[2] by 1 position.

 Difference Between Array and Linked List

Similarly, the same process for deletion is done
and therefore, it is also expensive.

Inserting a new element in linked list is not expensive in case of linked lists.

Consider the same scenario,

 Difference Between Array and Linked List

So, it requires just changing of 2 pointers, so not as expensive as arrays.

Similarly, deletion also requires changing of 2 pointers again, and therefore not as expensive as arrays.

Memory allocation of Array and Linked List :
Nature or way of Memory allocations – Consecutive memory allocations Elements of arrays are stored in consecutive memory locations. Nodes of linked lists may or may not be stored in consecutive memory locations.
Independency of elements Each element of array is independent of each other positions. Each node in the linked list is connected with its previous node by means of pointers.
Static/Dynamic memory allocation Array follows static memory allocation.
means memory is assigned to the particular
element in advance/compile time.
Linked list follows dynamic memory allocation means memory is assigned to the particular element at run-time..
Compile time/Run Time Memory is allocated at compile time in Stack means at the time when Programmer is Writing Program. The memory may be allocated at Run-Time in linked list means during execution of program. The functions used to allocate or deallocate dynamic memory  – malloc,calloc,delete etc…
Space required for storing data or payload :
Wastage of space In it space is wasted. In it space is not wasted.
Less/more space Array requires less space as only information or data is stored. Linked List requires more space as pointers are also stored along with information.
Fixed/Variable Its size is fixed and it cannot be extended or
reduced according to requirements.
Its size is not fixed and therefore can be extended or reduced according to requirements.
Requirement of lower/upper limit There is a need to know the upper limit on
the number of elements in advance in the array. The allocated memory is equal to the upper limit irrespective of the usage.Array is addressed by a 0-based index. So, the first object address is represented by index 0, the second object address is represented index 1 and so on.
There is a need to know only the starting address of linked list. No need of upper limit.
Access of elements/node :
Random / Sequential : Random Access is allowed in array because, to reach a particular element, you can reach there directly through index. Random access is not allowed as to reach a particular node, you have to sequentially traverse all the nodes that come before that node.
Time for Access elements Same amount of time is required to access
each element.Accessing an element at a particular index
takes O(1) time.
Different amount of time is required to access each element.
Accessing an element at a particular index takes O(n) time.
Complexity of insert, delete, search and space usage
Insert Delete Search Space Usage
Unsorted array O(1) O(1) O(n) O(n)
Value-Indexed Array O(1) O(1) O(1) O(n)
Sorted Array O(n) O(n) O(log n) O(n)
Insert Delete Search Space Usage
Unsorted linked list O(n) O(n) O(n) O(n)
Sorted linked list O(n) O(n) O(n) O(n)
Modification of Elements : Elements of array can be modified easily by identifying the index value only. It is a complex process for modifying the node in a linked list.
Caching effects Arrays have better cache locality that can
make a pretty big difference in performance.
Because As per  Spatial Locality principle, if
the data in location ‘n’ is accessed, then there’s a high chance that the data in location ‘n+1’
will be accessed soon. Therefore, several
contiguous memory blocks are loaded onto
the machine’s cache to speed up the data access. Since arrays are stored in a contiguous manner, they are best suited for this and thereby improving performance
It is not possible with linked list which are stored in random fashion in physical memory.
Linear/Non Linear Data Structures Arrays are linear data structures. Linked lists are linear and non-linear data structures.

Reference : http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

     

Incoming search terms:

  • difference between array and linked list
  • difference between array and linked list pdf
  • difference between array nd structure
  • compare between array and linked list
  • differentet btw array and link list
  • different between arry and linked list
  • difference between array nd linked list
  • difference between array and linked list in data structure
  • diff bw array and linked list
  • how linked list is differ from array in data structure

This article has 2 comments

Leave a Reply