Array vs Linked List – Difference between Array and Linked List

Ever wondered, How data is stored inside the computer’s memory? You can’t just throw data into the memory without making proper structure for the data.

To provide a organised structure for the data to get stored inside the computer’s memory so that we can use and manage the stored data in the most efficient way possible, we use Data Structures.

All programming languages provide fundamental data structures like int, char, float etc. to store the primitive type values. But with the use of user defined data types we can create data structure as required. It is like creating our home with bricks, we can make any type of structure we want.

Here in this article we will see two most commonly used user defined data types: Arrays and Linked List, Difference between Array and Linked List and their implementation.

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 (Source)

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 Representation (Source)

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

Array Implementation in C++

#include<iostream>

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<iostream>

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

Video Tutorial

Comment below if you have queries related to difference between array and linked list.