Singly linked list ni nini na utaweza kutumiwa lini?

Question

Accepted Answer

A **singly linked list** ni mlolongo wa **nodes**, ambapo kila node ina thamani na pointer kwa node inayofuata (**next**). Tofauti na array, nodes sio karibu — zinaweza kuwa mahali popote katika memory, zikiungana kwa references.

## Muundo

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

## Mfano

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

## Muundo wa Wakati

| Operesheni | Wakati |
|---|---|
| Ingiza/ondoa kwenye kichwa | O(1) |
| Kufikia kwa index | O(n) |
| Utaftaji | O(n) |

## Maamuzi

- **Nguvu:** O(1) ingiza/ondoa kwenye mwanzo; kukua bila kuweka upya; hakuna uwezo uliopoteza.
- **Udhaifu:** hakuna ufikiaji wa nasibu; kila node inabeba mzigo wa pointer; mahali mabaya ya cache (memory iliyosambazwa).

## Kwa nini ina muhimu

Linked lists huangaza wakati unajumlisha au kuondoa mara kwa mara kwenye ncha na nadra tu kuindeksa katikati — kwa mfano, kama msingi wa stacks, queues, na adjacency lists.

Kuelewa pointer manipulation hapa ndio msingi wa miti, grafu, na matatizo mengi ya mahojiano.

Operesheni	Wakati
Ingiza/ondoa kwenye kichwa	O(1)
Kufikia kwa index	O(n)
Utaftaji	O(n)