Kaj je enosmerno povezan seznam in kdaj bi ga uporabili?

Question

Accepted Answer

**Enosmerno povezan seznam** je veriga **vozlišč**, pri kateri ima vsako vozlišče vrednost in kazalec na **naslednje** vozlišče. Za razliko od niza vozlišča niso sosednja — lahko se nahajajo kjerkoli v pomnilniku, povezana s sklici.

## Struktura

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

## Primer

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

## Zahtevnost

| Operacija | Čas |
|---|---|
| Vstavljanje/brisanje na glavi | O(1) |
| Dostop po indeksu | O(n) |
| Iskanje | O(n) |

## Kompromisi

- **Prednosti:** O(1) vstavljanje/brisanje na sprednji strani; raste brez prerazdelitve; ni izpraznjene zmogljivosti.
- **Slabosti:** brez naključnega dostopa; vsako vozlišče nosi splošne stroške kazalca; slaba lokalnost predpomnilnika (razpršen pomnilnik).

## Zakaj je to важно

Povezani seznami sijejo, ko pogosto dodajate ali odstranjujete na koncih in redko indeksirate v sredino — na primer kot osnova skladi, čakalnih vrst in seznamov sosednosti.

Razumevanje manipulacije kazalcev je tu temelj za drevesa, grafe in mnogo intervjuskih problemov.

Operacija	Čas
Vstavljanje/brisanje na glavi	O(1)
Dostop po indeksu	O(n)
Iskanje	O(n)