List และ ArrayList

นึกภาพก่อน

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

List (รายการ) คือ Collection ที่ข้อมูลแต่ละตัว มีอันดับ เขียนเป็น ⟨a₀, a₁, ..., aₙ₋₁⟩ ข้อมูลซ้ำได้ ความแตกต่างจาก ArrayCollection คือ ต้องรักษาลำดับ จึงใช้ลูกเล่น "ย้ายตัวท้ายมาแทน" ไม่ได้อีกแล้ว

Interface

public interface List extends Collection {
  public void add(int index, Object e);
  public void remove(int index);
  public Object get(int index);
  public void set(int index, Object e);
  public int indexOf(Object e);
}

List extends Collection จึงมี add(e), remove(e), contains, size, isEmpty ด้วย และเพิ่มเมท็อดที่ใช้ตำแหน่ง

ArrayList

ข้อมูลตัวที่ i อยู่ในช่อง elementData[i] เรียงติดกันตั้งแต่ช่อง 0

เมท็อดที่เร็ว

public Object get(int index) { return elementData[index]; }      // Θ(1)
public void set(int index, Object e) { elementData[index] = e; }  // Θ(1)
public void add(Object e) { add(size, e); }                       // ต่อท้าย

add(index, e)

public void add(int index, Object e) {
  ensureCapacity(size + 1);
  for (int i = size; i > index; i--)
    elementData[i] = elementData[i - 1];
  elementData[index] = e;
  size++;
}

เลื่อนข้อมูลตั้งแต่ตำแหน่ง index ไปทางขวาหนึ่งช่อง เริ่มจากตัวท้ายสุด แล้วจึงใส่ข้อมูลใหม่ ใช้เวลา O(n)

• add(0, e) ช้าที่สุด (เลื่อนทุกตัว)
• add(size, e) เร็วที่สุด (ไม่เลื่อนเลย)

remove(index)

public void remove(int index) {
  for (int i = index + 1; i < size; i++)
    elementData[i - 1] = elementData[i];
  size--;
  elementData[size] = null;
}

เลื่อนข้อมูลที่อยู่หลัง index มาทางซ้ายหนึ่งช่อง เริ่มจากตัวที่ติดกับช่องที่ลบ ใช้เวลา O(n)

• remove(0) ช้าที่สุด
• remove(size - 1) เร็วที่สุด

remove(e) และ indexOf

public void remove(Object e) {
  int i = indexOf(e);
  if (i >= 0) remove(i);
}

indexOf ไล่หาจากช่อง 0 ใช้ O(n) แล้วเรียก remove(i) ที่เขียนไว้

ช่วง index ที่ถูกต้อง

สไลด์มี quiz สองข้อเรื่องนี้:

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

จากสไลด์:

จบแล้ว x.size() ได้ 3

Simulation แสดงการเลื่อนทีละตัวพร้อมนับจำนวนครั้ง ลองตัวอย่าง "เพิ่มหน้า vs เพิ่มท้าย" เพื่อเทียบ

public void add(int index, Object e) {
  ensureCapacity(size + 1);
  for (int i = size; i > index; i--)
    elementData[i] = elementData[i - 1];
  elementData[index] = e;
  size++;
}

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

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

1. เลื่อนผิดทิศตอน add

ลูปของ add ต้องเริ่มจากท้าย (i = size ลดลง) ถ้าเริ่มจากหน้า ค่าในช่องถัดไปจะถูกเขียนทับก่อนได้ย้าย ทุกช่องจะกลายเป็นค่าเดียวกัน

2. คิดว่า add ใช้ index ได้ถึง size − 1

add(size, e) ใช้ได้และหมายถึงต่อท้าย

3. คิดว่า remove ใช้ index ได้ถึง size

ไม่ได้ ช่อง size ไม่มีข้อมูล

4. สับสน remove(int) กับ remove(Object)

remove(2) ลบตำแหน่ง 2 ส่วน remove("A") ลบข้อมูล A ตัวแรกที่พบ

5. ใช้ลูกเล่นของ ArrayCollection กับ ArrayList

การย้ายตัวท้ายมาแทนช่องที่ลบทำให้ลำดับเสีย List จึงต้องเลื่อนทีละตัว

6. คิดว่า set เปลี่ยนขนาด

set แทนที่ข้อมูลเดิม size ไม่เปลี่ยน ต่างจาก add(i, e) ที่แทรกและทำให้ size เพิ่ม

ที่มา: LIST_4.pdf หน้า 1–16