सिङ्गली लिङ्क गरिएको सूची (singly linked list) के हो र कहिले यसलाई प्रयोग गर्नुहुन्छ?

Question

Accepted Answer

A **singly linked list** is a chain of **nodes**, where each node holds a value and a pointer to the **next** node. Unlike an array, the nodes are not contiguous — they can live anywhere in memory, connected by references.

## संरचना (Structure)

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## उदाहरण (Example)

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

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## जटिलता (Complexity)

| Operation | Time |
|---|---|
| Insert/delete at head | O(1) |
| Access by index | O(n) |
| Search | O(n) |

## ट्रेड-अफस् (Trade-offs)

- **शक्तिहरू:** O(1) insert/delete at the front; grows without reallocating; no wasted capacity.
- **कमजोरिहरू:** no random access; every node carries pointer overhead; poor cache locality (scattered memory).

## किन यो महत्त्वपूर्ण छ

Linked lists shine when you frequently add or remove at the ends and rarely index into the middle — for example, as the backbone of stacks, queues, and adjacency lists.

Understanding pointer manipulation here is foundational for trees, graphs, and many interview problems.