DES231 · Lab 3 · Singly Linked List

Lab 3 · SList — ต่อของเป็นสายโซ่ แล้วทำใบงานให้ครบห้าข้อ

สามข้อพอครับ — ตัวชี้คือป้ายที่แปะไว้ ไม่ใช่กล่องที่ใส่ของ · จะเร็วหรือช้าดูที่ว่าต้องเดินไหม · ล็อกให้แตะได้ปลายเดียวก็ได้สแตกมาฟรี จบตอนนี้น้องจะเขียนเมธอดของ SList ได้เองทุกตัวและบอก Big-O ได้โดยไม่ต้องท่อง

ประมาณ 35 นาที ของที่น้องมีแล้ว: Java · ลูป · อาเรย์ · การเรียกตัวเอง · การเรียงลำดับ · แฮช · Big-O คำถามให้กดตอบ 22 จุด ใบงาน Lab 3 ครบทั้งห้าข้อ

1ทำไมอาเรย์ไม่พอ

คำที่ต้องจำโหนด = ช่องเก็บค่า (element) + ช่องเก็บที่อยู่ของตัวถัดไป (next) · SList = โหนดต่อกันทางเดียว ตัวท้าย next เป็น null · เก็บแค่ที่อยู่ ไม่ได้เก็บตัวถัดไปไว้ข้างใน เลยย้อนกลับไม่ได้

2ตัวชี้คือป้าย ไม่ใช่กล่อง

ข้อเดียวที่พาผ่านทั้งตอนfirst เหมือนโพสต์อิทที่แปะว่า "เริ่มตรงนี้" — ย้ายป้ายไม่ได้ย้ายของ โหนดที่ไม่มีใครชี้ยังอยู่ที่เดิม แต่เดินไปหาไม่เจอแล้ว · meta data สามช่อง first｜size｜last เก็บไว้หยิบใช้ทันที · T คือช่องว่างที่ยังไม่กรอก ถ้าไม่มีต้องก๊อปทั้งคลาสหนึ่งชุดต่อหนึ่งชนิด

3addFirst แล้วกฎลำดับบรรทัด

กฎที่พลาดกันบ่อยที่สุดต่อสายให้เสร็จก่อนย้ายป้ายเสมอ — newNode.next = first; ต้องมาก่อน first = newNode; สลับเมื่อไหร่ โหนดใหม่จะชี้ตัวเอง แล้วของเดิมทั้งลิสต์ไม่มีใครชี้ถึง หายไปพร้อมกันหมด

4removeFirst แล้วอีกหกเมธอด

ไม่ต้องท่องแปดอย่างทุกเมธอดใช้ท่าเดียวกัน ต่างแค่ หยุดที่โหนดไหน — แก้ลิงก์ตรงไหนต้องจับตัวก่อนหน้าให้ได้ก่อนเสมอ · removeFirst ต้องจำของไว้ใน tmp ก่อนขยับป้าย เพราะต้องคืนค่ากลับไป

5Big-O จากคำถามเดียว

คำถามเดียวตอบได้ทั้งตารางต้องเดินไหม — ไม่ต้องเดิน = O(1) (AddFirst · AddLast · RemoveFirst) · ต้องเดิน = O(n) (RemoveLast · AddAtIndex · RemoveAtIndex · GetElementAtIndex · SetElementAtIndex) · กับดักคือ removeLast ที่เป็น O(n) ทั้งที่มี last ชี้อยู่ เพราะต้องเดินหาตัวก่อนหน้ามาเป็น last ตัวใหม่

6ใบงาน Lab 3 — ห้าข้อ ทำให้ดูทีละข้อ

โค้ดมาจากสามที่ อ่านป้ายให้ดีจากใบงาน (ชีทให้ครบ): addFirst addLast addAtIndex removeFirst  ·  เติมช่องว่างเอง (ชีทเว้นช่องไว้): reverse 4 ช่อง · search 3 ช่อง  ·  เราเขียนเอง (ชีทมีแต่ภาพ): removeLast removeAtIndex
คำตอบที่ต้องตรงกับใบงานคำถามแถมในข้อ addLast — บรรทัดที่ตัดทิ้งได้คือ newNode.next = null; เพราะคอนสตรักเตอร์ของ Node ตั้งให้แล้ว · ช่องว่างของ reverse = first ｜ current != null ｜ previous ｜ current · ช่องว่างของ search = first ｜ current.element.equals(item) ｜ current = current.next · โปรแกรมทดสอบ addFirst 9 แล้ว 4 แล้ว 7 ต้องได้ 7 4 9

7ของแถม — สแตกจากชีทบรรยาย

จับคู่กับ SListpush = addFirst · pop = removeFirst · peek = first.element — ทั้งสามเป็น O(1) เพราะแตะแค่ป้าย first และได้คุณสมบัติ "ใส่ทีหลังออกก่อน" มาฟรี  (สแตกอยู่ใน Topic 7 ของชีทบรรยาย ไม่ได้อยู่ในใบงาน Lab 3)

8งานที่สแตกทำให้ง่ายขึ้น

คำตอบที่ต้องตรงกับชีทแปลง 8 เป็นฐานสองได้ 1000 · ABCDBA ไม่ใช่พาลินโดรม (ตกที่คู่ที่สาม D กับ C) · postfix 4 5 + 6 3 / - ได้ 7 โดยตัวที่ป็อปทีหลังเป็นตัวตั้ง · infix 5 + (1 + 2) * 4 - 3 ได้ 14 โดยเคลียร์เฉพาะเครื่องหมายที่สำคัญกว่าหรือเท่ากับตัวใหม่

9สรุป — สามข้อที่เอาไปใช้ต่อได้

สามข้อ ที่เหลือคิดเอาได้

1. ตัวชี้คือป้ายที่แปะไว้ ไม่ใช่กล่องที่ใส่ของ — ต่อสายก่อนย้ายป้ายเสมอ  ·  2. ต้องเดินไหม — ไม่ต้องเดิน O(1) ต้องเดิน O(n)  ·  3. ล็อกให้แตะได้ปลายเดียวก็ได้สแตก — ได้ LIFO มาฟรี เอาไปพลิกลำดับได้ทุกงาน