Have you ever wondered how data is stored in the computer’s memory?
It’s not very smart to just “throw” data into the memory without having a proper structure of data.
To provide a well-organized structure for the said data to get stored is something crucial when programming. This way, we can use and manage the stored data more efficiently. To provide this, we use Data Structures.
Every programming language provides fundamental data structures like:
to store primitive type values.
But with the use of user-defined data types, we can now create data structure as required.
In this guide, you will see two of the most commonly used user define data types: Arrays and Linked List, the difference between them and their implementation.
The most simple type of data structure is called an Array.
An array is used to store a set of similar data in a contiguous block of memory under a heading or variable name. With its particular simplicity comes barriers like the need for a contiguous block of memory, or if free memory is available. If not, the block becomes inefficient to use arrays.
Arrays indexing starts at 0, and every element can be accessed using its index.
Operations on arrays are very fast, as any element can be accessed using array indexing. The name of the array is the base address and all its elements can be accessed using the base address. That’s because the memory allocated to array is consecutive.
On the other hand, a very simple and yet useful data structure that doesn’t need a contiguous block is the Linked list.
The Linked lists are used in situations where there is no need to allocate memory dynamically during the runtime of a program.
It can be visualized like a train – the Engine (head) and all the carriages (nodes) are linked to the train engine either directly or indirectly.
A linked list is a user-defined data type, and all the nodes of the list are linked using pointers. To access any node, you must traverse the list linearly – unline an array where you can have direct access to elements.
Difference between Arrays and Linked lists
|Definition||It is a collection of elements having the same data type with a common name.||It is an ordered collection of elements that 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 an 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 the node is required.|
|Searching||Binary search and Linear search||Linear search|
|Extra Space||Extra space is not required.||To link nodes of the list, pointers are used which require extra space.|
|Types||It can be single-dimensional, two dimensional or multi-dimensional.||It can be singly, doubly or circular linked list.|
Array implementation in C++
using namespace std;
int arr; // declaration an integer array of size 5
arr=5; // assigning values to the array elements
arr=4; // notice that array indexing starts from 0 and ends at size-1
cout<<arr[i]<<” “; // printing array elements
5 4 3 2 1
Linked List Implementation in C++
using namespace std;
/* Creating user-defined structure for storing data in linked list */
struct Node *next; // pointer to link nodes of the list
struct Node* head = NULL; // Initially there is no element in the 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 */
struct Node* ptr;
ptr = head;
while (ptr != NULL)
cout<< ptr->data <<” “;
ptr = ptr->next;
insert(5); // inserting data in the list
cout<<“The linked list is: “;
The linked list is: 7 6 4 1 5