Introduction to Linked Lists

Linked list is a linear collection of data elements called nodes. It can be considered as a series of nodes, with each node storing data as well as the address of the next node.

Linked lists contain a pointer variable HEAD that stores the address of the first node. Also, we store NULL in the address part of the last node because it has no next node connected to it.

Difference between Array and Linked List

Arrays store elements in contiguous memory locations. The size of the array is fixed and cannot be changed at runtime. We must know the number of elements in advance. Normally the allocated memory is equal to the upper limit of the array and In practice, however, the highest limit is rarely attained.

In a linked list nodes can exist at non-contiguous addresses. This permits the linked list’s size to be changed at runtime.

Array elements can be accessed directly with its index. But in the case of a linked list, random access is not possible. To access any element, all previous items must be traversed.

Inserting and deleting elements in an array is expensive because we have to shift the elements to preserve the order. Ease of insertion and deletion is a notable advantage of linked lists at the cost of extra space required for storing the address pointers.

Representation of Linked List

A linked list is a series of nodes in which the address of the first node is stored in a pointer called HEAD. Each of the nodes in the linked list consists of two parts:

• A data item.
• An address that points to another node.

In C, we can represent nodes using structures as:

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

Each struct node contains a data item as well as a pointer to another struct node. The following example creates a basic Linked List with three items and displays its elements.

Example: Creating a simple Linked List

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

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

int main()
{
    // Create and initialize nodes
    struct node *head;
    struct node *one = NULL;
    struct node *two = NULL;
    struct node *three = NULL;
    struct node *current = NULL;

    // Allocate memory for the nodes
    one = (struct node*) malloc(sizeof(struct node));
    two = (struct node*) malloc(sizeof(struct node));
    three = (struct node*) malloc(sizeof(struct node));

    // Assign data to nodes
    one->data = 1;
    two->data = 2;
    three->data = 3;

    // Connect first node
    // with the second node
    one->next = two;
    
    // Connect second node
    // with the third node
    two->next = three;

    // make next pointer of
    //third node to NULL
    //indicates last node
    three->next = NULL;

    // Save address of first node in head
    head = one;
    current = head;

    // print the linked list values
    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }

    return 0;
}

Now we’ve made a simple linked list with three nodes.

Output

1 2 3

Applications of Linked List

• To implement other data structures such as Queues, Stacks, Trees, Graphs, etc.
• Used for dynamic memory allocation.
• For manipulating polynomials, representing sparse matrice, etc.
• In undo functionality of softwares.
• Previous and next page navigation on web browsers.

Linked List Operations

Like any other data structure, we can perform insertion, deletion and traversal operations in a linked list. In the next tutorial, let’s learn Algorithms for insertion, deletion and traversal operations in a linked list.