Embedded Prep

Linked List Data Structure : Are you new to data structures and wondering what a Linked List is all about? This beginner-friendly guide explains the Linked List data structure in simple terms, with easy examples and clear visuals.

What You’ll Learn Linked List Data Structure :

• What a linked list is and how it works
• Advantages and disadvantages of using linked lists compared to arrays
• How linked lists store data using nodes and pointers
• How to create a linked list in C++ step by step
• How to traverse (print) a linked list
• How to insert new nodes anywhere in the list
• How to delete nodes from the list
• Types of linked lists like singly, doubly, and circular linked lists

This guide is perfect for students, beginner programmers, or anyone looking to strengthen their data structure skills. Whether you’re preparing for coding interviews or learning for fun, this article makes Linked Lists easy to understand.

Dive in and learn how to build flexible, dynamic data structures that go beyond the limits of arrays. Let’s make Linked Lists simple and fun!

Let’s break it down step by step.

What is a Linked List?

A linked list is a way to store a collection of data.

• Imagine a chain of boxes connected by strings.
• Each box holds:
  • A piece of data
  • A link (or pointer) to the next box in the chain

So, instead of storing everything next to each other in memory like an array, linked lists store data scattered around, connected by these links.

Why Use Linked Lists?

Linked lists are useful because:

• Flexible Size: They can grow or shrink easily. You don’t need to decide how big it should be ahead of time.
• Easy Insertions/Deletions: You can add or remove items in the middle without shifting everything around, like in arrays.

But:

• They use more memory (because of the extra links)
• Accessing items is slower (you have to follow the links one by one)

How a Linked List Looks

Let’s say you want to store numbers: 10 → 20 → 30

In memory, a linked list might look like this:

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

• Each box is called a Node.
• The first node is the Head.
• The last node points to NULL (meaning there’s nothing after it).

How Do We Create a Linked List?

Let’s see how to build one in C++ (but the idea is similar in any language).

Define a Node:

struct Node {
    int data;        // The value we store
    Node* next;      // Pointer to the next node
};

Create Nodes and Link Them:

Node* first = new Node();
Node* second = new Node();
Node* third = new Node();

first->data = 10;
first->next = second;

second->data = 20;
second->next = third;

third->data = 30;
third->next = nullptr;

This gives you:

10 → 20 → 30 → NULL

Traversing a Linked List

To print the list, we start at the head and follow the links:

Node* temp = first;

while (temp != nullptr) {
    cout << temp->data << " ";
    temp = temp->next;
}

Output:

10 20 30

Inserting a Node

Suppose we want to insert 15 after 10:

1. Create a new node: Node* newNode = new Node(); newNode->data = 15;
2. Point new node’s next to where 10 was pointing: newNode->next = first->next;
3. Update 10’s next to the new node: first->next = newNode;

Now the list looks like:

10 → 15 → 20 → 30

Deleting a Node

Suppose we want to delete 20:

1. Find the node before 20 (which is 15).
2. Make 15’s next point to 20’s next (which is 30).
3. Delete node 20.

In code:

Node* prev = first->next;   // points to 15
Node* toDelete = prev->next; // points to 20

prev->next = toDelete->next;
delete toDelete;

List becomes:

10 → 15 → 30

Types of Linked Lists

• Singly Linked List
  • Links go one way.
• Doubly Linked List
  • Each node has links in both directions.
• Circular Linked List
  • Last node links back to the first.

When to Use Linked Lists?

Use linked lists when:

• You don’t know how many elements you’ll need.
• You often add/remove elements from the middle.

Arrays are better when:

• You need fast random access (like getting the 10th item quickly).

Conclusion

Linked lists might seem tricky at first, but they’re simply a chain of nodes pointing to each other.

They’re powerful when you need flexibility in size and frequent insertions or deletions.

Keep practicing and try writing simple code to:
✅ Create a linked list
✅ Print it
✅ Insert nodes
✅ Delete nodes

You can also Visit other tutorials of Embedded Prep 

• What is eMMC (Embedded MultiMediaCard) memory ?
• Top 30+ I2C Interview Questions
• Bit Manipulation Interview Questions
• Structure and Union in c
• Little Endian vs. Big Endian: A Complete Guide
• Merge sort algorithm

Special thanks to @mr-raj for contributing to this article on Embedded Prep