# Linked Lists in DSA

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:

```python
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`.

```python
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:

```python
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

```python
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:

```python
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.