Array vs Linked List

Arrays and Linked Lists both are linear data structures, but they both have some advantages and disadvantages over each other.

One advantage of the linked list is that elements can be added to it indefinitely, while an array will eventually get filled or have to be resized (a costly operation that isn’t always possible).

Elements are also easily removed from a linked list whereas removing elements from an array leaves empty spaces that are a waste of computer memory.

This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences.

Array

The simplest type of data structure is Array which is used to store set of similar data in continuous blocks of memory under a common heading or variable name. With its simplicity comes some barriers like it need continuous block of memory and if free memory is not available in contiguous block it becomes inefficient to use arrays.

Array-Representation

 

Arrays indexing starts with 0, and every element of the array can be accessed using its index. Operation on array is very fast as any element can accessed directly using array indexing. Name of array is the base address of the array and all other elements can be accessed using the base address because the memory allocated to array is consecutive.

Linked List

On the other hand, a simple yet very useful data structure which doesn’t need contiguous blocks of memory is Linked List. They are used in situations when there is need to allocate memory dynamically that is during runtime of a program. It can be visualized like a train where we have an Engine (Head) and all the carriages(nodes) are linked to the train engine either directly or indirectly through other carriages.

Linked list is user-defined data type where all the nodes of the list are linked using pointers. To access any node of the list, we must traverse the list linearly unlike array where we can directly access the elements.

 

Array vs Linked List – Difference between Array and Linked List:

Parameters Array Linked List
Definition It is a collection of elements having same data type with a common name. It is an ordered collection of elements which are connected by links or pointers.
Size Fixed, once declared cannot be changed. Variable, can be changed during run-time.
Memory Allocation Require Contiguous blocks of memory. Random memory can be allocated.
Access Direct or randomly accessed, i.e., Specify the array index or subscript. Sequentially accessed, i.e., Traverse starting from the first node in the list by the pointer.
Insertion and Deletion Relatively slow, as to insert or delete any element, other elements need to be shifted to occupy the empty space or make space. Faster, Easier and Efficient as just linking or unlinking of node is required.
Searching Binary search and Linear search Linear search
Extra Space Extra space is not required. To link nodes of list, pointers are used which require extra Space.
Memory Utilization Inefficient Efficient
Types It can be single dimensional, two dimensional or multi-dimensional. It can be singly, doubly or circular linked list.

 

Array Implementation in C++

#include

using namespace std;

int main()
{
	int arr[5];  // declaration an integer array of size 5
	
	arr[0]=5;  // assigning values to the array elements
	arr[1]=4;  //  notice that array indexing starts from 0 and ends at size-1
	arr[2]=3;
	arr[3]=2;
	arr[4]=1;
	
	for(int i=0;i<5;i++)
	cout<<arr[i]<<" ";    // printing array elements
	
	return 0;
}

Output

5 4 3 2 1

 

Linked List Implementation in C++

#include
 
using namespace std;
 
/* Creating user defined structure for storing data in linked list */
struct Node 
{ 
   int data; 
   struct Node *next;  // pointer to link nodes of the list
}; 
 
struct Node* head = NULL;   // Initially their is no element in list, so head point nowhere 
 
/* function to insert and link nodes to the list */
void insert(int new_data) 
{ 
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));  // allocating memory dynamically
   new_node->data = new_data; 
   new_node->next = head; 
   head = new_node; 
} 
 
/* function to display data of the list */
void display() 
{ 
   struct Node* ptr;
   ptr = head;
   while (ptr != NULL) 
   { 
      cout<< ptr->data <<" "; ptr = ptr->next; 
   } 
} 
 
int main() 
{ 
   insert(5);  // inserting data in the list
   insert(1);
   insert(4);
   insert(6);
   insert(7);
   
   cout<<"The linked list is: ";
   display(); 
   return 0; 
}

Output

The linked list is: 7 6 4 1 5

 

I hope you will enjoy the Array vs Linked List. I would like to have feedback from my blog readers. Your valuable feedback, question, or comments about this article are always welcome.

Leave a Reply

Your email address will not be published. Required fields are marked *