Difference Between Array and Linked List

Arrays and Linked Lists are linear data structures that store data in memory. An array stores data elements in contiguous memory locations, thus allowing faster access using array indexes.

In contrast, a Linked list contains a sequence of data elements where each element is linked to its next element with the help of pointers. In this article, we will study the difference between Array and Linked List.

What is Array ?

• An array is a data structure that stores elements of the same data type in contiguous memory locations.
• Arrays are index-based data structures where each data element is associated with an index.
• An array is a big block of memory divided into smaller chunks, where each chunk stores some value.

For example, if we have to create an array to store 5 integer values, then each block will only keep the value of an integer type. If we try to store a value of anything other than an integer, we will get a compile-time error.

What is a Linked List ?

A linked list is a linear and non-primitive data structure in which each data element is allocated dynamically and points to the next element. Linked lists consist of nodes where each node contains a data field and a reference (link) to the next node in the list.

• A Linked List is made up of a sequence of elements called Nodes.
• Each node consists of two fields : one field stores data, and the second field (Pointer), stores an address that keeps a reference to the next node.
• Pointer (or Reference) to the next node, connects one node to an address of another node

Examples

Reading and Writing of an Array

As we discussed earlier, an array can contain only a single type of data, i.e., all integers, characters, or floating-point numbers. An array named arr having 10 integers can be declared as follows :

int arr[10];

We can read and write an array using for loop. In the case of a one-dimensional array, we require only one loop for reading or writing while another for traversing the array to print the elements.

The below program demonstrates the reading and writing of the array :

#include<stdio.h>

void main () {

    int a[5], i;

    // writing an array
    printf("Enter the array \n");
    for ( i= 0 ; i <= 4 ; i++) {
        scanf ( "%d", &a[ i ] ) ;
    }

    // reading an array
    printf( "Reading the array \n" );
    for (i = 0 ; i <= 4 ; i++) {
        printf ( "%d\n", a[ i ] ) ;
    }

}

Output :

Enter the array
1
2
3
4
5
Reading the array
1
2
3
4
5

Creating a Linked List

Every data element in a linked list points to the next element, where each data element is called a Node which has two fields, the data field, and the pointer. The Data field stores the value/information while the pointer stores the reference to the next Node. The first node of a linked list is known as Head Node.

Linked Lists are of multiple types that include a Singly-linked List, Doubly Linked List, Circular Linked List, and Circular double-linked List.

Creation, Traversing, Insertion, Deletion, Searching, Concatenation, and Flattening are some operations that can be performed on a linked list.

The below program demonstrates the reading and writing of the linked list:

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// to print the contents of the linked list
void printList(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}

int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // allocating 3 nodes
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 5; // assigning data in first node
    head->next = second; // Linking first node with second

    second->data = 6; // assign data to second node
    second->next = third; // Linking second node with third

    third->data = 7; // assign data to third node
    third->next = NULL; // setting pointer of third node to NULL

    printList(head);

    return 0;
}

Output :

 5  6  7

Key Difference Between Array and Linked List

The main difference between an array and a linked list is in their data storage and manipulation methods. Arrays allocate a fixed-size, contiguous block of memory at compile time, providing efficient indexing for direct access to elements. Linked lists, on the other hand, allocate memory dynamically at runtime, allowing for flexible size adjustments. While arrays excel in fast element access and are ideal for scenarios where size remains constant, linked lists shine in dynamic data scenarios, enabling efficient insertion and deletion operations. However, linked lists consume more memory due to node overhead, and their elements are interdependent, making them less suitable for scenarios where direct element access is crucial.

Array vs Linked List

Let’s summarize the differences between an array and a linked list in the table below :

Conclusion

• A linked list is a linear data structure containing nodes chained together, but those nodes may not be allocated sequentially in the memory.
• An array is a data structure that stores data elements of the same data type in contiguous memory locations.
• A significant difference between array and linked list is that array has a fixed size required to be declared prior, but a linked list is not restricted to size, expansion, and contract during execution.
• Hence, the main difference between array and linked list lies in the storage schema, which helps the user decide which data structure will be more suitable for a given problem.