سنگل لنکڈ لسٹ کیا ہے اور آپ اسے کب استعمال کریں گے؟

Question

Accepted Answer

ایک **singly linked list** **nodes** کی ایک زنجیر ہے، جہاں ہر node ایک value اور **next** node کے لیے ایک pointer رکھتا ہے۔ Array کے برعکس، nodes متصل نہیں ہوتے — وہ memory میں کہیں بھی رہ سکتے ہیں، references کے ذریعے منسلک۔

## ڈھانچہ

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

## مثال

```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 front میں؛ بغیر دوبارہ allocate کیے بڑھتا ہے؛ کوئی ضائع شدہ گنجائش نہیں۔
- **کمزوریاں:** کوئی random access نہیں؛ ہر node pointer overhead رکھتا ہے؛ خراب cache locality (بکھرا ہوا memory)۔

## یہ کیوں اہم ہے

Linked lists اس وقت شاندار ہوتے ہیں جب آپ اکثر آخر میں شامل یا ہٹاتے ہیں اور شاذ و نادر درمیانے میں index کرتے ہیں — مثال کے طور پر، stacks، queues، اور adjacency lists کی بنیاد کے طور پر۔

یہاں pointer manipulation کو سمجھنا trees، graphs، اور بہت سے interview مسائل کے لیے بنیادی ہے۔