Linked Lists: How They Work (Types and Operations)

In the previous articles, we learned how arrays and strings store data. Arrays allow us to access elements directly using indexes, but inserting or deleting elements can require shifting other elements.

What if we want a data structure that can grow or shrink without shifting all the existing elements?

This is where linked lists become useful.

1. What Is a Linked List?

A linked list is a linear data structure made up of smaller units called <span class=”tooltip-term” data-tooltip=”A node is an individual unit of a linked list. It stores data and a link to another node.”>nodes</span>.

Each node contains two things:

• Data: The actual value we want to store.
• Pointer: A link that stores the address of the next node.

For example, consider a linked list containing three numbers:

+------+-----+     +------+-----+     +------+------+
|  10  |  •------->|  20  |  •------->|  30  | NULL |
+------+-----+     +------+-----+     +------+------+

Here:

• The first node stores 10.
• The second node stores 20.
• The third node stores 30.
• The last node points to NULL, indicating the end of the list.

The first node is accessed through a pointer commonly called head.

2. How Does a Linked List Work?

Unlike arrays, linked-list nodes do not need to be stored in consecutive memory locations.

Each node can be stored wherever memory is available. The pointer inside each node connects it to the next one.

For example:

Memory Location:       100       450       220

                     +------+  +------+  +------+
Data:                | 10   |  | 20   |  | 30   |
Next:                | 450  |  | 220  |  | NULL |
                     +------+  +------+  +------+

The first node stores the address of the second node, and the second stores the address of the third.

This is how the nodes remain connected even when they are stored at different memory locations.

3. Creating a Node in C

In C, we can create a node using a struct.

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

Let’s understand its parts:

• data stores the actual value.
• next stores the address of the next node.

We can create a new node dynamically using malloc():

struct Node *newNode;

newNode = malloc(sizeof(struct Node));

newNode->data = 10;
newNode->next = NULL;

Here, malloc() allocates memory for a new node, while -> allows us to access its members through a pointer.

We also need to include the following header:

#include <stdlib.h>

4. Basic Operations on Linked Lists

Like arrays, linked lists support several operations.

A. Traversal

<span class=”tooltip-term” data-tooltip=”Traversal means visiting each node one by one to access or process its data.”>Traversal</span> means visiting every node in the list, starting from the first node.

For example, consider:

10 → 20 → 30 → NULL

We start at head, visit the first node, and follow its pointer to the next node until we reach NULL.

B. Insertion

Insertion means adding a new node to the linked list.

A new node can be added at the beginning, at the end, or between existing nodes.

For example, inserting 15 between 10 and 20:

Before:

10 → 20 → 30 → NULL

After:

10 → 15 → 20 → 30 → NULL

We connect the new node to the next node and update the previous node’s pointer.

C. Deletion

Deletion means removing an existing node from the linked list.

For example, deleting 20:

Before:

10 → 20 → 30 → NULL

After:

10 → 30 → NULL

We update the pointer of the previous node so that it points directly to the next node, skipping the node being deleted.

D. Searching

Searching means finding a particular value in the linked list.

For example, if we want to find 30, we start from the first node and check each node until we find the value or reach NULL.

5. Linked Lists vs. Arrays

Both arrays and linked lists are linear data structures, but they organise data differently.

Neither structure is always better. The right choice depends on how a program needs to store and access its data.

6. Types of Linked Lists

There are different ways to connect nodes in a linked list.

The three commonly studied types are:

1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both the previous and next nodes.
3. Circular Linked List: The last node connects back to the first node instead of pointing to NULL.

We’ll explore their structures, differences, and operations in detail in the next article.

A linked list stores data in nodes connected through pointers. Unlike arrays, its nodes do not need consecutive memory locations, and the list can grow or shrink dynamically.

Its basic operations include traversal, insertion, deletion, and searching.

Understanding linked lists is important because they also help us understand how other data structures, such as stacks and queues, can be implemented.