Linked Lists — Data Structures

Posted on by

Linked Lists – A Friendly Introduction

Imagine you’re making a chain out of paper clips.
You start with one clip, then connect another to it, then another, and so on.
Each clip holds the next one — that’s how the chain grows.

A Linked List works in a very similar way.
It’s a chain of elements (called nodes) that are linked together, one after another.

💡 What Is a Linked List?

A linked list is a way to store a collection of data where each piece of data knows where the next one is.
Unlike an array, where all elements sit side-by-side in memory, the parts of a linked list can be scattered anywhere — they’re just connected by links.

Each element (node) in a linked list has two parts:

  1. Data – the actual value you want to store.
  2. Pointer (or Link) – the address of the next node in the list.

Here’s how it looks visually:

[Data | Next] → [Data | Next] → [Data | Next] → NULL

The NULL at the end means “this is the last node — no more links ahead.”

🧱 The Structure of a Node

Let’s break down what a node looks like in memory:

+----------------+     +----------------+     +----------------+
| Data: 10       | --> | Data: 20       | --> | Data: 30       |
| Next: Address2 |     | Next: Address3 |     | Next: NULL     |
+----------------+     +----------------+     +----------------+

Here:

  • The first node contains data (10) and a link to the second node.
  • The second node links to the third.
  • The third node’s link points to NULL, showing the end of the list.

This entire chain is our Linked List!

🧠 Why Do We Need Linked Lists?

You might wonder — why not just use arrays?

Good question!
Arrays are great, but they have a small problem: fixed size.
Once you create an array of size 5, you can’t easily make it hold 6 or 7 items.

Linked lists solve this by being dynamic — you can add or remove nodes whenever you want.
There’s no need to shift elements or resize the structure. You just change the links!

Example:
If you have a to-do list and want to add a new task between two existing tasks — in an array, you’d have to shift everything.
But in a linked list, you simply link the new task’s node in between the two — easy and neat!

🔁 Types of Linked Lists

There are several kinds of linked lists, depending on how the nodes are connected.

1. Singly Linked List

Each node links to the next one only.

[10 | •] → [20 | •] → [30 | •] → NULL

You can move forward, but not backward.

2. Doubly Linked List

Each node has two pointers — one to the next node and one to the previous node.

NULL ← [10 | • | •] ↔ [20 | • | •] ↔ [30 | • | •] → NULL

This allows you to move in both directions.

3. Circular Linked List

In this type, the last node doesn’t point to NULL.
Instead, it points back to the first node — forming a circle.

[10 | •] → [20 | •] → [30 | •]
   ↑                         |
   └─────────────────────────┘

Circular lists are useful in situations like implementing round-robin scheduling in operating systems.

⚙️ Basic Operations on a Linked List

You can perform several operations on linked lists:

  1. Traversal: Go through each node to read data.
  2. Insertion: Add a new node (at the beginning, middle, or end).
  3. Deletion: Remove a node from any position.
  4. Searching: Find a node with a particular value.

All these operations involve updating the links carefully to keep the chain unbroken.

🎯 Advantages of Linked Lists

✅ Dynamic size — no need to predefine how many elements you’ll have.
✅ Easy insertion and deletion — just change pointers, no shifting needed.
✅ Efficient memory use — grows and shrinks as needed.

⚠️ Disadvantages of Linked Lists

❌ Extra memory for pointers.
❌ Slower access — you must start from the head and follow links one by one.
❌ Harder to reverse or traverse backward (in singly linked lists).

📘 Real-Life Analogy

Think of a treasure hunt!
Each clue (node) tells you where the next clue is.
To find the final treasure, you must follow the links in order — you can’t just skip ahead.
That’s exactly how a linked list works.

🧩 Simple Diagram of a Singly Linked List

   Head
    ↓
+--------+     +--------+     +--------+ 
| 10 | * | --> | 20 | * | --> | 30 | * | --> NULL
+--------+     +--------+     +--------+

Here:

  • The head is the starting point of the list.
  • Each node holds data and a pointer to the next one.
  • The last node points to NULL, marking the end.