LinkedList: โยงคู่แบบวนมีปมหัว

นึกภาพก่อน

รายการโยงเดี่ยวเดินได้ทางเดียว จะลบปมใดต้องรู้ปมก่อนหน้า ซึ่งต้องเดินหาจากปมหัว ถ้าทุกปมมีตัวโยงถอยหลังด้วย เมื่อยืนอยู่ที่ปมใดก็รู้ทั้งปมก่อนหน้าและปมถัดไปทันที

และถ้าต่อปลายทั้งสองเข้าหากันเป็นวงผ่านปมหัว จะไม่มีตัวโยงใดเป็น null อีกเลย ทุกปมมีเพื่อนบ้านสองข้างเสมอ โค้ดจึงไม่มีกรณีพิเศษ นี่คือ รายการโยงคู่แบบวนที่มีปมหัว (circular doubly linked list with header)

โครงสร้าง

public class LinkedList implements List {
  private static class LinkedNode {
    Object element;
    LinkedNode prev, next;
    LinkedNode(Object e, LinkedNode p, LinkedNode n) {
      this.element = e;
      this.prev = p;
      this.next = n;
    }
  }
  private LinkedNode header;
  private int size;

  public LinkedList() {
    header = new LinkedNode(null, null, null);
    header.prev = header.next = header;
  }
}

รายการว่าง: ปมหัวโยงกลับมาหาตัวเองทั้ง prev และ next

ในรายการที่มีข้อมูล:

• header.next คือปมข้อมูลตัวแรก
• header.prev คือปมข้อมูล ตัวสุดท้าย (เพราะวน)
• next ของปมสุดท้ายคือปมหัว

คำสั่งกำหนดค่าแบบต่อกัน

a = b = c; ทำจากขวาไปซ้าย: กำหนด c ให้ b ก่อน แล้วกำหนดให้ a ทั้งสองจึงมีค่าเท่ากับ c

เมท็อดที่เหมือนกับ SinglyLinkedList

size(), isEmpty(), indexOf(e), contains(e), nodeAt(i), get(i), set(i, e) เขียนเหมือนเดิม

เมท็อดที่ต่าง เพราะต้องจัดการ prev ด้วย: add(e), add(i, e), remove(e), remove(i)

addBefore

private void addBefore(LinkedNode q, Object e) {
  LinkedNode p = q.prev;
  LinkedNode x = new LinkedNode(e, p, q);
  p.next = q.prev = x;
  ++size;
}
public void add(Object e) { addBefore(header, e); }
public void add(int i, Object e) { addBefore(nodeAt(i), e); }

แทรกปมใหม่ x ไว้ ก่อน ปม q:

1. p = q.prev — ปมที่อยู่ก่อน q
2. สร้าง x โดยให้ x.prev = p และ x.next = q ตั้งแต่ใน constructor
3. p.next = q.prev = x — ให้ทั้งสองข้างชี้มาที่ x

addBefore ใช้เวลา Θ(1)

• add(e) = addBefore(header, e): ตัวที่อยู่ก่อนปมหัวคือปมสุดท้าย การแทรกก่อนปมหัวจึงเป็นการ ต่อท้าย → Θ(1)
• add(i, e) = addBefore(nodeAt(i), e): ต้องหา nodeAt(i) ก่อน → O(n)

removeNode

private void removeNode(LinkedNode q) {
  LinkedNode p = q.prev;
  LinkedNode x = q.next;
  p.next = x;
  x.prev = p;
  --size;
}
public void remove(int i) { removeNode(nodeAt(i)); }
public void remove(Object e) {
  LinkedNode q = header.next;
  while (q != header) {
    if (q.element.equals(e)) { removeNode(q); break; }
    q = q.next;
  }
}

เปลี่ยนตัวชี้ทั้งคู่ให้ข้ามปมที่จะลบไป removeNode ใช้เวลา Θ(1) เพราะมีตัวโยง prev จึงไม่ต้องเดินหาปมก่อนหน้า ส่วน remove(i) และ remove(e) เป็น O(n) จากการหาปม

สังเกตเงื่อนไขลูป: while (q != header) ไม่ใช่ q != null เพราะรายการวน ไม่มี null

ตัวอย่างไล่ทีละขั้น

รายการมี ⟨A, B⟩ เรียก add(1, "Z") ซึ่งคือ addBefore(nodeAt(1), "Z")

private void addBefore(LinkedNode q, Object e) {
  LinkedNode p = q.prev;
  LinkedNode x = new LinkedNode(e, p, q);
  p.next = q.prev = x;
  ++size;
}

โจทย์เติมโค้ดในสไลด์

addFirst(e) เพิ่มข้อมูลเป็นตัวแรก:

public void addFirst(Object e) {
  LinkedNode q = header.next;
  LinkedNode x = new LinkedNode(e, header, q);
  header.next = q.prev = x;
  ++size;
}

removeLast() ลบตัวสุดท้าย:

public void removeLast() {
  if (size == 0) throw new IllegalStateException();
  LinkedNode p = header.prev;
  LinkedNode pp = p.prev;
  pp.next = header;
  header.prev = pp;
  --size;
}

ทั้งสองเป็น Θ(1) เพราะเข้าถึงทั้งตัวแรก (header.next) และตัวสุดท้าย (header.prev) ได้ทันที

เวลาการทำงาน เทียบสามคลาส

จุดที่มักพลาด

1. เขียนลำดับตัวโยงผิด

สไลด์ชี้ไว้ว่า p.next = x; q.prev = x; ถูก ส่วน p.next = x.prev; q.prev = x.next; ผิด เพราะ x.prev คือ p และ x.next คือ q จะกลายเป็น p.next = p กับ q.prev = q

2. คิดว่า add(i, e) และ remove(i) เป็น Θ(1)

เฉพาะ addBefore และ removeNode ที่เป็น Θ(1) การหาปมด้วย nodeAt(i) ยังเป็น O(n)

3. ใช้ != null เป็นเงื่อนไขหยุด

รายการวนไม่มี null ต้องหยุดเมื่อวนกลับมาถึง header

4. คิดว่า addBefore(header, e) แทรกหน้าสุด

แทรกก่อนปมหัว = ต่อท้าย ถ้าจะแทรกหน้าสุดต้อง addBefore(header.next, e)

5. ลืมแก้ตัวโยงข้างใดข้างหนึ่ง

ทุกการแทรกหรือลบต้องแก้ทั้ง next ของปมซ้ายและ prev ของปมขวา

6. คิดว่าปมหัวของรายการว่างมีตัวโยงเป็น null

header.prev และ header.next ชี้ตัวเอง

ที่มา: LIST_4.pdf หน้า 28–45 และโจทย์เติมโค้ดหน้า 49–53