Singly linked list คืออะไรและคุณจะใช้มันเมื่อไร?

Question

Accepted Answer

**Singly linked list** คือสายโซ่ของ **nodes** โดยที่แต่ละ node มีค่าและ pointer ไปยัง **next** node ต่างจาก array nodes ไม่ได้อยู่ติดกัน — พวกเขาสามารถอยู่ได้ที่ไหนก็ได้ในหน่วยความจำ เชื่อมต่อกันด้วย references

## โครงสร้าง

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

## ตัวอย่าง

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

## ความซับซ้อน

| การดำเนินการ | เวลา |
|---|---|
| Insert/delete ที่ head | O(1) |
| Access โดย index | O(n) |
| ค้นหา | O(n) |

## ข้อดีข้อเสีย

- **จุดแข็ง:** O(1) insert/delete ที่ด้านหน้า; เติบโตโดยไม่ต้องจัดสรรใหม่; ไม่มีความจุเสียเปล่า
- **จุดอ่อน:** ไม่มีการเข้าถึงแบบสุ่ม; แต่ละ node มีค่าใช้จ่าย pointer; locality ของ cache ไม่ดี (หน่วยความจำกระจัดกระจาย)

## เหตุใดจึงสำคัญ

Linked lists ทำงานได้ดีเมื่อคุณบ่อยครั้งที่เพิ่มหรือลบที่ปลายสุด และไม่ค่อยจัดทำ index เข้าไปตรงกลาง — เช่น เป็นกระดูกสันหลังของ stacks queues และ adjacency lists

การทำความเข้าใจการจัดการ pointer ที่นี่เป็นพื้นฐานสำหรับ trees graphs และปัญหา interview มากมาย

การดำเนินการ	เวลา
Insert/delete ที่ head	O(1)
Access โดย index	O(n)
ค้นหา	O(n)