Linked Collection: มีและไม่มีปมหัว

นึกภาพก่อน

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

ทั้งสองแบบใช้ interface Collection ตัวเดิม โปรแกรมที่ใช้งานจึงไม่ต้องเปลี่ยน

ปม (Node)

private static class LinkedNode {
  Object element;
  LinkedNode next;
  LinkedNode(Object e, LinkedNode next) {
    this.element = e;
    this.next = next;
  }
}

แต่ละปมมีสองส่วน: element อ้างอิงข้อมูล และ next อ้างอิงปมถัดไป (เป็น null ถ้าไม่มี)

แบบไม่มีปมหัว

public class LinkedCollection implements Collection {
  private LinkedNode first;
  private int size;
  public int size() { return size; }
  public boolean isEmpty() { return size == 0; }
}

ตัวแปร first เก็บตัวโยงไปปมแรก

add: แทรกหน้าสุด

public void add(Object e) {
  first = new LinkedNode(e, first);
  ++size;
}

บรรทัดเดียวทำสองอย่าง: สร้างปมใหม่ที่ next ชี้ปมแรกเดิม แล้วให้ first ชี้ปมใหม่ ใช้เวลา Θ(1)

เหตุผลที่แทรกหน้า: มีตัวโยงไปปมแรกอยู่แล้ว ถ้าจะต่อท้ายต้องเดินไปหาปมสุดท้ายก่อน

การท่องปม และ contains

public boolean contains(Object e) {
  LinkedNode node = first;
  while (node != null) {
    if (node.element.equals(e)) return true;
    node = node.next;
  }
  return false;
}

รูปแบบ node = first; while (node != null) { ...; node = node.next; } คือวิธีมาตรฐานในการไล่ทุกปม ใช้เวลา O(n)

remove

การลบปมทำโดยให้ปม ก่อนหน้า ข้ามปมที่จะลบไป:

p.next = p.next.next;

จึงต้องให้ตัวชี้ p หยุดที่ปมก่อนหน้าตัวที่จะลบ ปัญหาคือ ปมแรกไม่มีปมก่อนหน้า จึงต้องเขียนเป็นกรณีพิเศษ:

public void remove(Object e) {
  if (first == null) return;
  if (first.element.equals(e)) {
    first = first.next; --size;
  } else {
    LinkedNode p = first;
    while (p.next != null && !p.next.element.equals(e))
      p = p.next;
    if (p.next != null) { p.next = p.next.next; --size; }
  }
}

แบบมีปมหัว (header node)

ทางแก้กรณีพิเศษคือเพิ่มปมหลอกหนึ่งปมไว้หน้าสุดเสมอ เรียกว่า ปมหัว:

private LinkedNode header = new LinkedNode(null, null);

• อยู่หน้าสุดตลอด ไม่ถูกลบ
• ไม่เก็บข้อมูล
• ปมข้อมูลตัวแรกคือ header.next

ตอนนี้ ทุกปมข้อมูลมีปมก่อนหน้า โค้ดจึงสั้นลง:

public void add(Object e) {
  header.next = new LinkedNode(e, header.next);
  ++size;
}
public void remove(Object e) {
  LinkedNode p = header;
  while (p.next != null && !p.next.element.equals(e))
    p = p.next;
  if (p.next != null) { p.next = p.next.next; --size; }
}

ไม่ต้องตรวจ first == null และไม่ต้องแยกกรณีปมแรก

toArray

public Object[] toArray() {
  Object[] arr = new Object[size];
  LinkedNode p = header.next;
  int k = 0;
  while (p != null) {
    arr[k++] = p.element;
    p = p.next;
  }
  return arr;
}

ใช้เวลา Θ(n) เพราะต้องผ่านครบทุกปมเสมอ

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

จากสไลด์ (แบบมีปมหัว): add A, B, C, D แล้ว remove B

toArray() คืน [D, C, A] ความยาว 3 สังเกตว่าลำดับ กลับกับลำดับที่ add เพราะแทรกหน้าทุกครั้ง

ขั้นตอนของ remove("B"): p เริ่มที่ header → ดู p.next (D) ไม่ใช่ เลื่อน → ดู p.next (C) ไม่ใช่ เลื่อน → ดู p.next (B) ใช่ จึงทำ p.next = p.next.next ให้ C ชี้ไป A

ลองสลับระหว่างสองแบบใน simulation แล้วดูว่าโค้ดของ remove ต่างกันอย่างไร

public void add(Object e) {
  header.next = new LinkedNode(e, header.next);
  ++size;
}

เวลาการทำงาน

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

1. เขียนเงื่อนไขลูปของ remove สลับลำดับ

while (p.next != null && !p.next.element.equals(e)) ต้องตรวจ p.next != null ก่อน ถ้าสลับกันจะเกิด NullPointerException เมื่อถึงปมสุดท้าย

2. ให้ p ชี้ปมที่จะลบ แทนปมก่อนหน้า

รายการโยงเดี่ยวเดินถอยหลังไม่ได้ ถ้า p ชี้ปมที่จะลบ จะแก้ next ของปมก่อนหน้าไม่ได้ จึงตรวจที่ p.next.element

3. คิดว่าปมหัวเก็บข้อมูลตัวแรก

ปมหัวไม่เก็บข้อมูล ข้อมูลตัวแรกอยู่ที่ header.next และ size ไม่นับปมหัว

4. คิดว่า add ต่อท้าย

LinkedCollection แทรกหน้า ผลของ toArray() จึงกลับลำดับ

5. ลืม --size หรือ ++size

size ไม่ได้นับจากปมจริง ต้องปรับเองทุกครั้งที่เพิ่มหรือลบ

6. คิดว่ารายการโยงทำให้ contains เร็วขึ้น

ยังเป็น O(n) และเข้าถึงปมที่ k โดยตรงไม่ได้ ต้องเดินจากปมแรก

ที่มา: COLLECTION_3(LINKED).pdf หน้า 1–49 และ 53