What is the difference between Array List and Linked List ?

Article by: Manish Methani

Last Updated: October 12, 2021 at 8:04am IST
5 min 5 sec read

Till now we have studied the arrays, right? Arrays are used to store data of the same type. In arrays, we must know the size of the array. That's why an array size is fixed every time.

For example,

Assume there is an array like this,

Now suppose you want to add element 20 at the first index after 10. Now to insert 20 after 10 you have to shift everything one position towards the right. So a shifted array looks like this,

Now think for a while, how expensive an operation of shifting an element of the array is. Now suppose you have to remove element 30 from the given array. So you have to shift all the elements towards the left. The solution to this shifting operation is a well-known Data Structure known as the Linked list in Data Structures.

ArrayList vs Linked List

The difference between Array List and the Linked List is explained here by the advantages of Linked List over Arrays.

1) Dynamic size 
2) Insertion/Deletion is easy in Linked List.

What is Linked List?

The linked list is a linear data Structure used to store the elements dynamically. No need to know the actual size. In the case of arrays, you must know the size of an array. Linked List in Data Structure gives better advantages than arrays.

Linked List looks like this

    Head
     |
     |
     V
    +---+-----+------       +----+----+------         +----+----+-----
    | Data | Pointer|-----> | Data | Pointer| ------> | Data  | NULL |  
    +---+-----+------       +----+----+------         +----+----+-----

Linked List is created using nodes. Each node contains Data and Pointer. And each Pointer is attached with Next pointer. And the end Pointer contains NULL to indicate that the linked list is finished. The first Node is HEAD always.

Program to introduce Linked List

C program to understand the concept of the linked list in Data Structures

           head        first             Second
             |            |                |
             |            |                |
             V            |                |
        +---+---+     +---+---+       +----+------+
        | 1  | o----->|  2  | o-----> |  3 | NULL |
        +---+---+     +---+---+       +----+------+    

// A simple C program to introduce a linked list in DataStructures
#include 
 
struct node 
{
  int data;
  struct node *next;
};

/* Program to create a simple linked list with 3 nodes */
int main()
{
  struct node* head = NULL;
  struct node* first = NULL;
  struct node* second = NULL;
   
/* allocate 3 nodes in the heap  */
  head = (struct node*)malloc(sizeof(struct node)); 
  first = (struct node*)malloc(sizeof(struct node));
  second = (struct node*)malloc(sizeof(struct node));
 
   
  head->data = 1;       //assign data in head node
  head->next = first;  // Link head node with the first node
   

  first->data = 2;      //assign data to first node
  first->next = second; // Link first node with the second node
    
   
  second->data = 3;      //assign data to second node
  second->next = NULL;    
 
  return 0;
}

Note, firstly head is pointing to the head node. Then head node to the first node and the first node to the second node.

The comments given are self-explanatory. What we did is first we have allocated the three Nodes using the malloc() function. We named it as the head, first, the second node. We added the data in the head node and then linked it with the first node. Then we added data to the first node and linked it with the second node. Then we added data to the second node and then added NULL to indicate the end of the linked list.

It's easy if you looked at the program carefully. Just three boxes. Add data into it and link it to the next node. Now you can create any number of nodes you want.

I hope you have got the concept of how to create a node in the linked list with the C Program. Tada! Also, check out the related articles which you might love to read. They are given in the below section.