Cad is liosta nasctha singil ann agus cathain a d'úsáidfeá ceann?

Question

Accepted Answer

Is **liosta nasctha singil** a bhíonn ann slabhra de **nódanna**, agus i ngach nód a bhíonn luach agus pointeoir chuig an **chéad nód eile**. Murab ionann agus array, níl na nódanna in aontacht — is féidir leo a bheith i bhfolach in aon áit sa chuimhne, ceangailte le tagairtí.

## Struchtúr

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

## Sampla

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

## Castacht

| Oibríochta | Am |
|---|---|
| Ionchur/scriosadh ag an cheann | O(1) |
| Rochtain de réir innéacs | O(n) |
| Cuardach | O(n) |

## Malartuithe

- **Éifeachtaí:** O(1) ionchur/scriosadh ag an tús; fás gan ath-dhíochlaonadh; gan acmhainn dhíobhálach.
- **Laigí:** gan rochtain randamach; tá ráchairt pointeoir ar gach nód; drochthreorú tasc (cuimhne scaipthe).

## Cén fáth a bhíonn sé tábhachtach

Tá listí nasctha go hiontach nuair a chuireann tú nó a scriosann tú go minic ag na foircinn agus go tréigean tú an lár — mar shampla, mar bhunús stáichí, scuaine, agus liostaí comharsanachta.

Tá tuiscint ar ionramháil pointeoir anseo bunúsach do chrainn, ghraif, agus go leor fadhbanna agallamh.

Oibríochta	Am
Ionchur/scriosadh ag an cheann	O(1)
Rochtain de réir innéacs	O(n)
Cuardach	O(n)