Linked List คือโครงสร้างข้อมูลแบบลำดับที่ประกอบด้วย node หลายตัวเชื่อมต่อกันด้วย pointer

Mental model: นึกภาพเป็นขบวนรถไฟที่แต่ละตู้รู้ว่าต่อกับตู้ถัดไปตู้ไหน

Recap: Linked List เก็บข้อมูลแบบเชื่อมโยงเป็นโหนด ไม่ใช่ช่องต่อเนื่องแบบ array

Linked List เหมาะกับงานที่เพิ่ม/ลบข้อมูลบ่อยโดยเฉพาะต้นรายการ เพราะไม่ต้อง shift สมาชิกจำนวนมาก

Mental model: จุดเด่นคือการปรับลิงก์ระหว่างโหนดแทนการขยับข้อมูลทั้งก้อน

Recap: ใช้ Linked List เมื่อ pattern งานเน้น insert/delete มากกว่า random access

Node คือหน่วยข้อมูลพื้นฐาน ประกอบด้วยค่า (value) และตัวชี้ไปโหนดถัดไป

Mental model: Node คือกล่องที่มีข้อมูลจริง + ที่อยู่ของกล่องถัดไป

type SinglyNode<T> = {
  value: T;
  next: SinglyNode<T> | null;
};

Recap: ถ้าเข้าใจ node จะเข้าใจ Linked List ทั้งระบบ

Head คือ reference ไปยังโหนดแรกของรายการ

Mental model: Head คือประตูเข้าหลัก ถ้าไม่มี head ก็เข้าถึงรายการไม่ได้

Recap: งานเกือบทุกอย่างใน linked list เริ่มจาก head

Tail คือโหนดสุดท้ายของรายการ โดยปกติ next ของ tail จะเป็น null

Mental model: Tail ช่วยให้ append ได้เร็วขึ้นถ้าเราถือ reference ไว้

Recap: เก็บ tail ไว้จะช่วยลดเวลาเพิ่มท้ายจาก O(n) เหลือ O(1)

Next pointer คือช่องที่เก็บตำแหน่งของโหนดถัดไป

Mental model: เหมือนลูกศรบอกเส้นทางเดินในรายการ

Recap: ถ้า pointer ขาดหรือชี้ผิด โครงสร้าง linked list จะเสียทันที

Array เข้าถึง index ได้เร็ว O(1) แต่ insert/delete กลางมัก O(n); Linked List เข้าถึง index ช้า O(n) แต่ insert/delete เมื่อรู้ตำแหน่งโหนดทำได้ดี

Mental model: Array = ช่องติดกัน, Linked List = โหนดเชื่อมกัน

Recap: เลือกโครงสร้างตาม workload จริง ไม่ใช่ตามความคุ้นเคย

โหนดใน linked list ไม่จำเป็นต้องอยู่ติดกันในหน่วยความจำ แต่เชื่อมกันผ่าน pointer

Mental model: เหมือนบ้านคนละซอยแต่มีแผนที่บอกทางไปบ้านถัดไป

Recap: โครงสร้างไม่ต่อเนื่องทำให้ยืดหยุ่นขึ้น แต่ cache locality มักแย่กว่า array

Singly linked list มี pointer เดียวคือ next ชี้ไปข้างหน้า

Mental model: เดินได้ทางเดียวจากหัวไปท้าย

Recap: โครงสร้างง่าย ใช้หน่วยความจำน้อยกว่า doubly

Doubly linked list มีทั้ง next และ prev ทำให้เดินหน้า/ถอยหลังได้

Mental model: เหมือนถนนสองทิศทาง

type DoublyNode<T> = {
  value: T;
  next: DoublyNode<T> | null;
  prev: DoublyNode<T> | null;
};

Recap: ยืดหยุ่นกว่า singly แต่ใช้หน่วยความจำต่อโหนดมากขึ้น

Traversal คือการเดินโหนดจาก head ไปจน null ทีละตัว

Mental model: ต้องเดินตามลูกศรทุกครั้ง ไม่สามารถกระโดด index ได้

function traverse(head: SinglyNode<number> | null) {
  let current = head;
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

Recap: traversal พื้นฐานใช้เวลา O(n)

การเข้าถึง index ที่ i ต้องเดินจากหัว i ก้าว จึงไม่ใช่ O(1)

Mental model: อยากได้ตำแหน่งที่ 8 ต้องเดินผ่าน 0..7 ก่อน

Recap: access by index ของ linked list เป็น O(n)

ค้นหาด้วยการเดินทีละโหนดและเทียบค่า

Mental model: linear search บน linked list

Recap: search โดยทั่วไปเป็น O(n)

สร้าง node ใหม่แล้วชี้ next ไป head เดิม จากนั้นเลื่อน head มาที่ node ใหม่

Mental model: เสียบตู้ใหม่หน้าแถว

Recap: prepend ทำได้ O(1)

ถ้ามี tail ทำ O(1), ถ้าไม่มี tail ต้องเดินหาโหนดสุดท้าย O(n)

Mental model: มี tail เหมือนมีทางลัดไปท้ายรายการ

Recap: เก็บ tail ช่วยให้ append เร็วขึ้นชัดเจน

หาตำแหน่งก่อนจุดแทรก แล้วปรับ pointer ให้ node ใหม่เชื่อมเข้ากลาง

Mental model: ผ่าลิงก์เดิม 1 เส้น แล้วเสียบโหนดใหม่ตรงกลาง

Recap: ต้นทุนหลักอยู่ที่การเดินไปตำแหน่งเป้าหมาย

ขยับ head ไปโหนดถัดไปของ head เดิม

Mental model: ปลดตู้แรกออกจากขบวน

Recap: delete head ทำได้ O(1)

ใน singly list ต้องหาโหนดก่อน tail ก่อนลบ จึงมัก O(n)

Mental model: ต้องเดินไปเกือบสุดก่อนถึงจะตัดท้ายได้

Recap: delete tail ใน singly list ไม่เร็วเท่า prepend

หาโหนดก่อนตำแหน่งลบ แล้วข้าม node เป้าหมายด้วยการปรับ next

Mental model: รีไวร์เส้นทางให้ข้าม node ที่จะลบ

Recap: ลบตรงกลางได้ดีเมื่อมี reference โหนดก่อนหน้า

เมื่อเดินเจอโหนดเป้าหมายสามารถแก้ value ได้ตรง ๆ

Mental model: แก้เนื้อหาในกล่อง ไม่เปลี่ยนโครงสร้างลิงก์

Recap: update value เร็วเมื่อรู้ reference ของ node แล้ว

แทรกหลังทำง่ายกว่าใน singly list เพราะมี reference node ปัจจุบัน; แทรกก่อนมักต้องหา previous

Mental model: after insert = ปรับ next ของ node ปัจจุบัน + node ใหม่

Recap: doubly list ช่วยแทรกก่อน/หลังสะดวกขึ้น

เดินนับทีละโหนดจนสุดรายการ หรือเก็บ size ไว้ในคลาสแล้วอัปเดตทุกครั้ง

Mental model: เลือกแลกเวลา query กับเวลา maintenance

Recap: ถ้าไม่เก็บ size ไว้ การหา length ทุกครั้งคือ O(n)

ตรวจว่า head เป็น null หรือไม่

Mental model: ไม่มีประตูเข้า = ลิสต์ว่าง

function isEmpty(head: SinglyNode<unknown> | null) {
  return head === null;
}

Recap: isEmpty check เป็น O(1)

เดินทีละโหนดและกลับทิศ pointer โดยใช้ prev/current/next

Mental model: หมุนลูกศรทุกเส้นให้ชี้กลับทาง

function reverse(head: SinglyNode<number> | null) {
  let prev: SinglyNode<number> | null = null;
  let current = head;

  while (current) {
    const nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }

  return prev;
}

Recap: reverse linked list ทำได้ O(n) และใช้พื้นที่เพิ่ม O(1)

ใช้ slow/fast pointers โดย fast เดิน 2 ก้าว slow เดิน 1 ก้าว

Mental model: เมื่อ fast จบทาง slow จะอยู่กลาง

Recap: middle node หาได้ O(n) โดยไม่ต้องนับ length ก่อน

ใช้ Floyd cycle detection: ถ้ามี cycle slow กับ fast จะเจอกัน

Mental model: คนเดินเร็วกว่าในสนามวนจะตามทันคนเดินช้า

Recap: cycle detection ทำได้ O(n) และพื้นที่ O(1)

เทคนิคใช้ pointer สองตัวความเร็วต่างกันเพื่อหา pattern โครงสร้าง

Mental model: หนึ่งตัวสแกนละเอียด อีกตัววิ่งนำเพื่อสร้างเงื่อนไขเจอกัน

Recap: เทคนิคนี้ใช้บ่อยกับ middle node, cycle, split list

access/search โดย index เป็น O(n), prepend O(1), append O(1) เมื่อมี tail, reverse O(n)

Mental model: งานที่ต้องเดินโหนดยาว ๆ จะโตตาม n

Recap: strength ของ linked list คือการแก้โครงสร้าง ไม่ใช่ random access

เพิ่ม/ลบโหนดตามตำแหน่งที่รู้ได้ดี, ขยายขนาดยืดหยุ่น, โครงสร้างต่อยอดได้ง่าย

Mental model: ดีเมื่อข้อมูลเปลี่ยนโครงสร้างบ่อย

Recap: เหมาะกับงานแก้ลำดับบ่อยมากกว่างานอ่านแบบสุ่ม

random access ช้า, ใช้ memory overhead จาก pointer, debug pointer ซับซ้อนกว่า

Mental model: ความยืดหยุ่นแลกมาด้วยต้นทุนโครงสร้าง

Recap: ถ้างานเน้นอ่าน index บ่อย array มักเหมาะกว่า

เช่น implementation ของ queue/deque, undo-redo, playlist ที่ insert/delete บ่อย

Mental model: ใช้เมื่อโครงสร้างข้อมูลต้องเปลี่ยนตำแหน่งบ่อย

Recap: workload เป็นตัวตัดสินหลัก

Singly ประหยัดกว่าแต่เดินย้อนกลับไม่ได้; Doubly ยืดหยุ่นแต่ใช้ pointer มากขึ้น

Mental model: เลือกจากความต้องการเดินย้อนและแก้โหนดรอบข้าง

Recap: ถ้าไม่ต้องย้อนบ่อย เริ่มจาก singly ก่อน

Array เด่น random access; Linked List เด่น insert/delete เมื่อมี node reference

Mental model: Array = เร็วในการอ่านตำแหน่ง, Linked List = คล่องในการจัดโครง

Recap: ไม่มีตัวไหนดีกว่าเสมอ ขึ้นกับโจทย์

เขียนได้ทั้งแบบ class เพื่อรวม behavior และแบบ object/function เพื่อความยืดหยุ่น

Mental model: class เหมาะกับ API ชัดเจน; object เหมาะกับโค้ดสั้นและทดลอง

class LinkedList<T> {
  head: SinglyNode<T> | null = null;
  tail: SinglyNode<T> | null = null;

  prepend(value: T) {
    const node: SinglyNode<T> = { value, next: this.head };
    this.head = node;
    if (!this.tail) this.tail = node;
  }
}

Recap: เลือกสไตล์ที่ทีมอ่านง่ายและดูแลง่าย

ลองสลับ preset และกด operation เพื่อดูการเปลี่ยนแปลงของโครงสร้าง linked list แบบทันที โดยแสดงความสัมพันธ์ head/tail, next และ prev ให้เห็นชัดเจน

next pointer อย่างเดียว

{
  "preset": "singly",
  "middleIndex": null,
  "linkedList": {
    "value": 10,
    "next": {
      "value": 20,
      "next": {
        "value": 30,
        "next": {
          "value": 40,
          "next": null
        }
      }
    }
  }
}

ชุด Lab นี้ออกแบบให้ฝึกตั้งแต่ prepend/append ไปจนถึง middle node และ cycle detection ด้วย runtime checks จริงหลายเคส

Recap: ถ้าต้องการยกระดับจากความเข้าใจสู่การลงมือทำ ให้เริ่ม Lab ตั้งแต่ข้อ 1 และไล่ต่อเนื่อง

ข้อผิดพลาดหลักคือลืมอัปเดต pointer ให้ครบทุกจุด, ไม่ handle null, และลืมอัปเดต tail/size หลังแก้โครงสร้าง

Mental model: ทุกครั้งที่แก้ลิงก์ ให้ตรวจ before/after ว่าเส้นทางยังต่อกันครบ

Recap: pointer safety คือหัวใจของ linked list