X'inhu lista magħqudin waħdiet u meta tuża waħda?

Question

Accepted Answer

**Lista magħqudin waħdiet** hija katina ta' **nodi**, fejn kull nodu jżomm valur u pointer għan-**nodu** li ġej. Bħala differenza minn array, in-nodi mhumiex kontigu — jistgħu jkunu kull mekka fil-memorja, konnessi b'referenzi.

## Istruttura

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

## Eżempju

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

## Komplettezza

| Operazzjoni | Ħin |
|---|---|
| Dħul/ħasil fil-kapo | O(1) |
| Aċċess b'indeks | O(n) |
| Tfittxija | O(n) |

## Trade-offs

- **Qawwiet:** O(1) dħul/ħasil fil-kapo; tikber mingħajr riallokazjoni; l-ebda kapaċità miħmuxa.
- **Dgħajfiet:** l-ebda aċċess każwali; kull nodu jdum overhead ta' pointer; cache locality ħażin (memorja mxeħħa).

## Għaliex huwa importanti

Listat magħqudin jixrqu meta ta' spiss iżżid jew tneħħi fi n-nuhaat u rari indiksi lejn nofs — pereżempju, bħala l-issokkor ta' stacks, queues, u listi ta' ġirien.

Il-fehim tal-manipulazzjoni ta' pointers hawn hija fundamentali għal siġar, graffs, u ħafna problemi ta' intervista.