Array vs Linked List: Data Structure

Data structure: Difference Between Array and Linked List

What is Array?

An array is a linear data structure that can store similar data items for further processing. The similar data items mean all data items have same data type like int, char, string etc. We can say an array is the collection of homogeneous elements and these homogeneous elements are stored in contiguous memory location. In arrays, we can access any element directly because an array works on indexes so they are quite efficient, they take constant time for lookups and insertions. The total number of data items or elements in an array is called the length of an array.

What is Linked List?

The linked list is well defined collection of objects called nodes. In linked list, nodes are randomly stored in the memory and the pointers are used to connect these nodes to each other. The last node of the linked list contains null or it doesn’t point to any node. In linked list, nodes are stored randomly so direct access is not possible in the linked list we have to access the list sequentially.

Comparison Table

Parameters		Array	Linked List
Structure		An array is a linear data structure that can store similar data items for further processing. The similar data items mean all data items have same data type like int, char, string etc. Arrays are an index-based data structure where each element is associated with an index.	The linked list is well defined collection of objects called nodes. In linked list, nodes are randomly stored in the memory and the pointers are used to connect these nodes to each other. In linked list, nodes are stored randomly so direct access is not possible in the linked list so we have to access the list sequentially.
Size		Arrays have fixed size; we have to assign the size at time of array declaration means that we can’t change the size of the array at the run time.	The linked lists are dynamic and flexible. We can grow or shrink linked list at the time of execution.
Memory Required		Arrays are memory efficient as compared the linked list.	The linked lists take more memory over arrays because extra memory is used to store the addresses of the next node.
Storage Allocation		In arrays, we assign the memory at the time of declaration or we can say at the compile time.	We assign the memory to linked list at time of execution or at runtime.
Accessing Time		An array takes constant time for accessing the element because they work on indexes so we can directly access any element of it.	In linked list, direct or random access is not possible because it doesn’t work on indexes. So linked list takes linear time for accessing the element.
Memory Utilization		Arrays are not able to utilize the memory efficiently because we have to declare the size at the time of compilation.	Linked lists utilize the memory efficiently.
Insertion or Deletion		These operations take more time to perform in arrays because shifting of elements are required.	These operations perform fast and efficiently in the linked list.