Understanding Linked Lists

What Is a Linked List?

A linked list is a linear data structure in which elements are stored in separate nodes, and each node points to the next node.

Unlike arrays, linked lists do not store elements in a continuous block of memory. Instead, each element (node) holds:

• The data

• A reference (pointer) to the next node

Example of a simple linked list:

[10] -> [20] -> [30] -> [40] -> null

Why Linked Lists Are Useful

Linked lists are helpful when you need:

• Fast insertion or deletion

• Dynamic memory usage

• Structures that grow and shrink frequently

In arrays, inserting at the beginning or middle requires shifting elements. In a linked list, you simply update pointers.

Types of Linked Lists

1. Singly Linked List

Each node has one pointer that points to the next node.

[A] -> [B] -> [C] -> null

2. Doubly Linked List

Each node has two pointers:

• One for the next node

• One for the previous node

null <- [A] <-> [B] <-> [C] -> null

3. Circular Linked List

The last node points back to the first node, forming a circle.

[A] -> [B] -> [C]
 ^                |
 |________________|

Structure of a Node

public class Node
{
    public int Data;
    public Node Next;
}

A linked list is made by connecting multiple nodes.

Basic Operations on Linked Lists

1. Insertion at the Beginning — O(1)

void InsertAtStart(int value)
{
    Node newNode = new Node { Data = value };
    newNode.Next = head;
    head = newNode;
}

2. Insertion at the End — O(n)

void InsertAtEnd(int value)
{
    Node newNode = new Node { Data = value };

    if (head == null)
    {
        head = newNode;
        return;
    }

    Node temp = head;
    while (temp.Next != null)
    {
        temp = temp.Next;
    }
    temp.Next = newNode;
}

3. Deleting a Node — O(n)

void DeleteNode(int value)
{
    if (head == null) return;

    // If deleting the head
    if (head.Data == value)
    {
        head = head.Next;
        return;
    }

    Node temp = head;
    while (temp.Next != null && temp.Next.Data != value)
    {
        temp = temp.Next;
    }

    if (temp.Next != null)
    {
        temp.Next = temp.Next.Next;
    }
}

4. Searching — O(n)

bool Search(int value)
{
    Node temp = head;
    while (temp != null)
    {
        if (temp.Data == value) return true;
        temp = temp.Next;
    }
    return false;
}

Advantages of Linked Lists

• Dynamic size

• Fast insertion and deletion

• No need for shifting elements

• Efficient memory usage

Disadvantages of Linked Lists

• Slower access (you must traverse from the start)

• More memory usage (due to extra pointer)

• Not cache-friendly

When to Use Linked Lists

Use a linked list when:

• You need frequent insertion or deletion

• Memory needs to grow dynamically

• You want to build stacks, queues, or graphs

Avoid linked lists when:

• You need fast indexing

• Random access is required

Real-Life Applications of Linked Lists

• Music playlists (next song, previous song)

• Browser history (back, forward navigation)

• Undo/redo operations

• Image viewers (next image, previous image)

Example: Traversing a Linked List

void PrintList()
{
    Node temp = head;
    while (temp != null)
    {
        Console.Write(temp.Data + " -> ");
        temp = temp.Next;
    }
    Console.WriteLine("null");
}

Time and Space Complexity Summary

Summary

Linked lists are a powerful data structure that provides flexibility and efficiency in situations where arrays fall short. Understanding how nodes and pointers work helps you build more advanced data structures later.

Key takeaways:

• Linked lists store data in nodes

• They provide fast insertion and deletion

• Access is slower than arrays

• They are used in queues, stacks, graphs, and many system features