Çfarë është një listë e lidhur njëdrejtimisht dhe kur do ta përdornit?

Question

Accepted Answer

Një **listë e lidhur njëdrejtimisht** është një zinxhir i **nyjeve**, ku secila nyje mban një vlerë dhe një tregues në nyjen **tjetër**. Ndryshe nga një array, nyjet nuk janë të afuara — ato mund të jenë kudo në memorie, të lidhura nga referencat.

## Struktura

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

## Shembull

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

## Kompleksiteti

| Operacioni | Koha |
|---|---|
| Shtim/fshirje në kokë | O(1) |
| Aksesi sipas indeksit | O(n) |
| Kërkimi | O(n) |

## Kompromise

- **Pikat e forta:** O(1) shtim/fshirje në përpara; rritet pa ri-alokuar; pa kapacitet të humbur.
- **Pikat e dobëta:** pa aksese të rastësishme; çdo nyje mbart përqark treguesit; lokalitet i keq i cache-it (memorie e shpërndarë).

## Pse ka rëndësi

Listat e lidhura dritojnë kur shpesh shtoni ose hiqni në skajet dhe rrallë indeksoni në mes — për shembull, si shtylla vertebrale e stack-eve, radhëve, dhe listave të afërsisë.

Kuptuesi i manipulimit të treguesve këtu është themeli për pemë, grafe, dhe shumë problema të intervistës.

Operacioni	Koha
Shtim/fshirje në kokë	O(1)
Aksesi sipas indeksit	O(n)
Kërkimi	O(n)