Apa itu linked list tunggal dan kapan Anda akan menggunakannya?

Question

Accepted Answer

Sebuah **linked list tunggal** adalah rantai **node**, di mana setiap node memegang nilai dan pointer ke node **berikutnya**. Berbeda dengan array, node tidak berdekatan — mereka dapat berada di mana saja dalam memori, terhubung oleh referensi.

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

## Kompleksitas

| Operasi | Waktu |
|---|---|
| Penyisipan/penghapusan di kepala | O(1) |
| Akses berdasarkan indeks | O(n) |
| Pencarian | O(n) |

## Pertukaran

- **Kekuatan:** O(1) penyisipan/penghapusan di depan; tumbuh tanpa realokasi; tidak ada kapasitas terbuang.
- **Kelemahan:** tidak ada akses acak; setiap node membawa overhead pointer; lokalitas cache buruk (memori tersebar).

## Mengapa ini penting

Linked list bersinar ketika Anda sering menambah atau menghapus di ujung dan jarang mengindeks ke tengah — misalnya, sebagai tulang punggung stack, antrian, dan daftar adjacency.

Memahami manipulasi pointer di sini merupakan dasar untuk pohon, grafik, dan banyak masalah interview.

Operasi	Waktu
Penyisipan/penghapusan di kepala	O(1)
Akses berdasarkan indeks	O(n)
Pencarian	O(n)