UNDERSTANDING LINKED LISTS…

What is a Linked List?

A Linked List is a linear data structure where elements are stored in separate objects called nodes.

Each node contains:

1. Data
2. Address (or reference) of the next node

Unlike arrays, linked lists do not store data in continuous memory locations.

So you can imagine it like a chain ⛓ where every part is connected to the next one.

1️⃣ Single Linked List

Structure

In a Single Linked List, each node contains:

• Data
• Pointer to the next node

The last node points to NULL.

Example

If we store:
10 → 20 → 30 → 40

Each node points to the next one.

Basic Operations

1. Insertion
2. Deletion
3. Traversal (printing all elements)
4. Searching

Algorithm Example (Insertion at Beginning)

Steps:

1. Create new node
2. Make new node’s next point to head
3. Update head to new node

Time Complexity:

• Insertion at beginning → O(1)
• Searching → O(n)

Advantages

✔ Dynamic size
✔ Easy insertion and deletion

Disadvantages

❌ Cannot move backward
❌ Extra memory for pointer

2️⃣ Doubly Linked List

Structure

In a Doubly Linked List, each node contains:

• Data
• Pointer to next node
• Pointer to previous node

So we can move forward and backward.

Example:
NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL

Basic Operations

1. Insert at beginning
2. Insert at end
3. Delete a node
4. Traverse forward and backward

Algorithm Example (Deletion)

Steps:

1. Find node
2. Change previous node’s next pointer
3. Change next node’s prev pointer

Time Complexity:

• Insertion → O(1) (if position known)
• Searching → O(n)

Advantages

✔ Can move in both directions
✔ Easy deletion

Disadvantages

❌ More memory used
❌ More pointer handling

3️⃣ Circular Linked List

Structure

In a Circular Linked List, the last node points back to the first node.

There is no NULL.

Example:
10 → 20 → 30 → 40
↑________________|

Types

• Circular Singly Linked List
• Circular Doubly Linked List

Algorithm Example (Traversal)

1. Start from head
2. Print data
3. Move to next
4. Stop when you reach head again

Time Complexity:

• Traversal → O(n)

Advantages

✔ Good for round-robin scheduling
✔ Continuous looping

Disadvantages

❌ Risk of infinite loop
❌ Harder to debug

Real Life Examples of Linked List

Now let’s see how companies use Linked Lists in real life.

1️⃣ Music Playlist (Spotify)

Companies like Spotify use linked lists to manage playlists.

Get Parv Methi’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

When you press:

• Next
• Previous

It works like a Doubly Linked List.

Algorithm Used:

• Traversal
• Insert at end
• Delete song

2️⃣ Web Browser History (Google Chrome)

In browsers like Google Chrome, history works like a Doubly Linked List.

You can:

• Go back
• Go forward

Each page is connected to previous and next page.

Algorithm Used:

• Stack + Doubly Linked List
• Navigation traversal

3️⃣ Operating System Scheduling

Operating systems like Linux use Circular Linked Lists in process scheduling.

Round Robin Scheduling uses Circular Linked List.

Algorithm Used:

• Round Robin Algorithm
• Queue implementation

4️⃣ Undo/Redo in Applications

Apps like Microsoft Word use Doubly Linked List for:

• Undo
• Redo

Each action is stored as a node.

Algorithm Used:

• Insert at head
• Move backward for undo
• Move forward for redo

5️⃣ Image Viewer / Slideshow

Image viewers allow:

• Next image
• Previous image
• Loop slideshow

This works like a Circular Linked List.

Used in companies like Adobe in their image tools.

Common Algorithms Used in Linked Lists

1. Traversal
2. Insertion
3. Deletion
4. Searching
5. Reversal Algorithm
6. Floyd’s Cycle Detection Algorithm (for circular detection)

Floyd’s Cycle Detection Algorithm

Also called:

• Tortoise and Hare Algorithm

Steps:

1. Use two pointers
2. One moves slow (1 step)
3. One moves fast (2 steps)
4. If they meet → cycle exists

Time Complexity: O(n)

Conclusion

Linked Lists are very powerful data structures.

• Single Linked List is simple and memory efficient.
• Doubly Linked List is flexible.
• Circular Linked List is useful for continuous processes.

Many big companies use linked lists in:

• Music apps
• Browsers
• Operating systems
• Editing software

Even though arrays are simple, linked lists are better when we need dynamic memory and frequent insertions or deletions.

Understanding linked lists will help you in:

• Coding interviews
• Competitive programming
• System design
• Real software development

If you understand Linked List clearly, many other data structures like stacks, queues, and graphs will also become easy.

Keep learning and keep coding 🚀