Kas yra vienpusė susieta sąrašai ir kada jį naudotum?

Question

Accepted Answer

**Vienpusė susieta sąrašai** yra **mazgų** grandinė, kurioje kiekvienas mazgas turi reikšmę ir nuorodą į **kiti** mazgą. Skirtingai nuo masyvo, mazgai nėra nuoseklūs — jie gali būti bet kur atmintyje, susieti nuorodomis.

## Struktūra

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

## Pavyzdys

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

## Sudėtingumas

| Operacija | Laikas |
|---|---|
| Įterpimas/trynimas pradžioje | O(1) |
| Prieiga pagal indeksą | O(n) |
| Paieška | O(n) |

## Kompromisai

- **Pranašumai:** O(1) įterpimas/trynimas pradžioje; auga be perskirstymo; nėra švaistomosios talpos.
- **Trūkumai:** nėra atsitiktinės prieigos; kiekvienas mazgas turi nuorodos papildomą svorį; prasta cache lokalybė (išsklaidyta atmintis).

## Kodėl tai svarbu

Susietieji sąrašai yra puikūs, kai dažnai pridedate arba šalinate iš galų ir retai indeksuojate vidurį — pavyzdžiui, kaip stekai, eilutės ir gretimybės sąrašai.

Supratimas, kaip manipuliuoti nuorodomis čia, yra pagrindinis medžiams, grafams ir daugeliui pokalbio problemų.

Operacija	Laikas
Įterpimas/trynimas pradžioje	O(1)
Prieiga pagal indeksą	O(n)
Paieška	O(n)