Apakah senarai terpaut tunggal dan bilakah anda akan menggunakannya?

Question

Accepted Answer

**Senarai terpaut tunggal** adalah rantaian **nod**, di mana setiap nod menyimpan nilai dan penunjuk ke nod **seterusnya**. Tidak seperti larik, nod-nod tidak bersebelahan — mereka boleh berada di mana saja dalam memori, dihubungkan oleh rujukan.

## Struktur

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

## Contoh

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

## Kerumitan

| Operasi | Masa |
|---|---|
| Sisip/padam di kepala | O(1) |
| Akses mengikut indeks | O(n) |
| Carian | O(n) |

## Pertukaran

- **Kekuatan:** O(1) sisip/padam di kepala; berkembang tanpa pengagihan semula; tiada kapasiti yang terbuang.
- **Kelemahan:** tiada akses rawak; setiap nod membawa overhead penunjuk; tempat kecil cache yang buruk (memori tersebar).

## Mengapa penting

Senarai terpaut bersinar ketika anda sering menambah atau mengeluarkan di hujungnya dan jarang mengindeks ke tengah — sebagai contoh, sebagai tulang belakang tindanan, baris gilir, dan senarai ketersebelahan.

Memahami manipulasi penunjuk di sini adalah asas untuk pokok, graf, dan banyak masalah temu duga.

Operasi	Masa
Sisip/padam di kepala	O(1)
Akses mengikut indeks	O(n)
Carian	O(n)