Mi az egyszeresen kapcsolt lista és mikor használnál egyet?

Question

Accepted Answer

Az **egyszeresen kapcsolt lista** a **csomópontok** lánca, ahol minden csomópont egy értéket és egy mutatót tartalmaz a **következő** csomópontra. Az array-tól eltérően a csomópontok nem összefüggők — bárhol lehetnek a memóriában, referenciák által összekapcsolódva.

## Szerkezet

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

## Példa

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

## Bonyolultság

| Operáció | Idő |
|---|---|
| Beszúrás/törlés az elején | O(1) |
| Hozzáférés index alapján | O(n) |
| Keresés | O(n) |

## Kompromisszumok

- **Erősségek:** O(1) beszúrás/törlés az elején; növekedés újrafoglalás nélkül; nincs pazarolt kapacitás.
- **Gyengeségek:** nincs véletlen hozzáférés; minden csomópont mutatóra vonatkozó terhelést hordoz; rossz cache lokalitás (szétszórt memória).

## Miért fontos

A kapcsolt listák akkor ragyognak, amikor gyakran adnak hozzá vagy távolítanak el a végeken, és ritkán indexelnek a közepébe — például stackek, sorok és szomszédossági listák alapjaként.

A mutató-manipuláció megértése itt alapvető a fák, gráfok és sok interjúkérdés számára.

Operáció	Idő
Beszúrás/törlés az elején	O(1)
Hozzáférés index alapján	O(n)
Keresés	O(n)