Linked List

รู้จัก Doubly Linked List — มี pointer สองทาง

Doubly Linked List คือ linked list ที่ node แต่ละตัวมี pointer สองทาง: **next** (ชี้ไป node ถัดไป) และ **prev** (ชี้กลับไป node ก่อนหน้า) — ทำให้เดินหน้า-ถอยหลังได้อย่างอิสระ เปรียบเหมือนถนนสองทิศทางที่วิ่งได้ทั้งไปและกลับ

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

// ต่างจาก SinglyNode: เพิ่ม prev pointer เพื่อเดินย้อนกลับ

const node_a = { value: "A", next: null, prev: null };
const node_b = { value: "B", next: null, prev: null };
const node_c = { value: "C", next: null, prev: null };

node_a.next = node_b;
node_b.prev = node_a;
node_b.next = node_c;
node_c.prev = node_b;

const head = node_a;
const tail = node_c;
// head → A ⇄ B ⇄ C ← tail

Doubly Linked List: เดินไปข้างหน้าผ่าน next และเดินกลับหลังผ่าน prev

• เดินสองทิศทาง — forward ผ่าน next, backward ผ่าน prev ไม่ต้องเริ่มจาก head ใหม่
• insert/delete สะดวกกว่า — มี reference node ก่อนหน้าเสมอผ่าน prev ไม่ต้องเดินจาก head
• ใช้ memory เพิ่มต่อ node — ต้องเก็บทั้ง next (4-8 bytes) และ prev (4-8 bytes)
• delete tail เร็วขึ้น — มี prev ชี้ไป node ก่อนท้ายทันที ทำให้ delete tail ทำได้ O(1)

ข้อดีของ prev pointer — เมื่อรู้ทั้งก่อนหน้าและถัดไป

ใน singly linked list ถ้าต้องการลบ node ตรงกลาง คุณต้องหา node ก่อน node เป้าหมาย — ซึ่งหมายความว่าต้องเดินจาก head มาทั้งแถว แต่ใน doubly linked list เมื่อคุณมี reference ไปยัง node เป้าหมายแล้ว คุณรู้ทันทีว่า node ก่อนหน้าคือตัวไหนผ่าน `node.prev` — ไม่ต้องเดินจาก head ใหม่

• **Delete node โดยไม่ต้องรู้ previous:** ใน singly list คุณต้องรู้ node ก่อนหน้าเพื่อรีไวร์ next ให้ข้าม node ที่ถูกลบ — ใน doubly list คุณใช้ node.prev.next = node.next ได้ทันที
• **Insert ก่อน node เป้าหมาย:** ใน singly list ต้องเดินหาตำแหน่งก่อน node นั้น — ใน doubly list ใช้ node.prev เท่านั้นก็รู้แล้วว่าต้องแทรกตรงไหน
• **Reverse traversal:** ย้อนกลับเพื่อตรวจสอบค่าหรือหาของก่อนหน้า — ไม่ต้อง reverse ทั้ง list เหมือน singly

Traversal — เดินหน้าและถอยหลัง

การ traverse ใน doubly linked list ทำได้สองแบบ: forward traversal (จาก head → tail ผ่าน next) และ backward traversal (จาก tail → head ผ่าน prev)

// Forward traversal (head → tail) — เหมือน singly
function printForward(head) {
  let current = head;
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

// Backward traversal (tail → head) — ใช้ prev เพื่อย้อนกลับ
function printBackward(tail) {
  let current = tail;
  while (current !== null) {
    console.log(current.value);
    current = current.prev;
  }
}

// ตัวอย่าง
const head = makeDoublyList(["A", "B", "C"]);
const tail = head.next.next; // node_c
printForward(head);  // A  B  C
printBackward(tail); // C  B  A

ความสามารถในการเดินย้อนกลับทำให้ doubly linked list มีประโยชน์มากในสถานการณ์ที่ต้อง undo, backtracking, หรือเดินดูข้อมูลสองทิศทาง เช่น browser history (เดินหน้า-ถอยหลัง)

ดูโค้ดทำงานทีละขั้น — Doubly Traversal

ลองลงมือ — ฝึก Doubly Linked List

ลงมือสร้างและจัดการ doubly linked list — เริ่มจากฝึกสร้างและเชื่อม node สองทิศทาง

เปรียบเทียบ Singly vs Doubly Linked List

กฎสำคัญที่ต้องจำ — Doubly Linked List

ทบทวนความเข้าใจ