Unlike arrays, where insertion in the middle takes O(N) time due to shifting elements, a Linked List allows insertion without shifting.

In this blog, we will use LL as short form for Linked List.

What is a Linked List?

A Linked List is a collection of individual nodes connected using memory addresses (references).

Each node contains:

• A value

• A reference (pointer) to the next node

We do not store elements in continuous memory like arrays.

Head of Linked List

Every linked list has a starting point called the Head.

• The head points to the first node.

• In most problems, the head is already given to you.

• All operations (traversal, insertion, deletion) start from the head.

Structure of a Node (Singly Linked List)

Here is the correct Python structure:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Explanation:

• val → stores the data.

• next → stores the reference to the next node.

• None means there is no next node (end of the list).

Traversal of Linked List

To traverse a linked list:

• Start from head

• Move until it becomes None

In Python, we use None instead of null.

def traverse(head):
    while head:
        print(head.val)
        head = head.next   # Move to next node

Time Complexity → O(N)

---

Types of Linked Lists

1️⃣ Singly Linked List

• Each node points to the next node only.

• Traversal is possible in one direction only.

2️⃣ Doubly Linked List

In a doubly linked list:

• Each node stores reference to:

  • Next node

  • Previous node

• We usually maintain both Head and Tail.

Structure:

class DoublyNode:
    def __init__(self, val, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

Advantages:

• Can traverse in both directions.

• Deletion becomes easier if node reference is given.

---

Reverse a Linked List

This is one of the most commonly asked DSA interview questions.

There are two ways to reverse a linked list:

1️⃣ Iterative Approach

def reverse_ll_iterative(head):
    prev = None
    current = head  # Always use a separate pointer for traversal

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

Time Complexity → O(N)

Space Complexity → O(1)

Why interviewers prefer this:

• Efficient

• No extra space

• Clear pointer manipulation understanding

2️⃣ Recursive Approach

Corrected version:

def reverse_ll_recursive(head):
    if not head or not head.next:
        return head

    new_head = reverse_ll_recursive(head.next)

    head.next.next = head
    head.next = None

    return new_head

Time Complexity → O(N)

Space Complexity → O(N) (because of recursion stack)

⚠️ Important:
In interviews, mention that recursion uses extra stack space.

---

Linked lists are used in:

• Stack and Queue implementation

• LRU Cache

• Hash collisions (chaining)

• Graph adjacency list

• Merge Two Sorted Lists

• Detect Cycle (Floyd’s Algorithm)

If you understand pointer manipulation clearly, many advanced problems become easier.