วิธีคิดแบบนักวิทยาการคอมพิวเตอร์/Linked lists

บทที่ 17 Linked lists
17.1 Embedded references
บทที่ 17 Linked lists.
17.1 Embedded references.
เราเคยได้เห็นตัวอย่างของ attributes ที่อ้างอิงถึง objects อื่นๆ ซึ่งเราเรียกว่า embedded references (ดูได้จาก 12.8) โครงสร้างข้อมูล linked list ใช้ประโยชน์จากความสามารถนี้
Linked lists เกิดขึ้นจากการประกอบกันของ nodes ซึ่งในแต่ละ node จะเก็บข้อมูลอ้างอิงตำแหน่งเพื่อชี้ไปยัง node ถัดไป นอกจากนี้ในแต่ละ node ยังบรรจุข้อมูลไว้ภายในซึ่งจะเรียกส่วนนี้ว่า cargo
Linked lists ถูกพิจารณาให้เป็นโครงสร้างข้อมูลแบบ recursive (ข้อมูลที่เชื่อมกันเป็นทอดๆ) เพราะว่ามันมีคำนิยามแบบ recursive
A Linked list จะมีลักษณะดังนี้
• List ที่ว่างเปล่าจะถูกแสดงด้วยข้อมูล None หรือ
• แต่ละ Node จะต้องมี cargo และข้อมูลอ้างอิงตำแหน่ง
โครงสร้างข้อมูลแบบ recursive มี method แบบ recursive ในตัวของมันเอง
17.2 The Node class
17.2 The Node class.
เหมือนเช่นเคยเมื่อการเขียนคลาสใหม่ เราจะเริ่มด้วยการเขียน initialization และ __str__ methods เพื่อให้เราสามารถทดสอบกลไกพื้นฐานของ class ที่สร้างขึ้น และการแสดงผลของ class เช่น
class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next
def __str__(self):
return str(self.cargo)
ค่า parameters สำหรับ initialization method กำหนดเป็นแบบ option โดยกำหนดค่า default ไว้ ให้ cargo และ link มีค่าเป็น None
ค่า string ที่แสดงค่าของ node ก็คือค่า string ที่แสดงค่าของ cargo เพราะว่าฟังก์ชัน str สามารถรับค่าใดๆก็ได้ เราจึงสามารถเก็บค่าใดๆก็ได้ใน list
เพื่อทดสอบสิ่งที่ได้เตรียมไว้ เราสามารถสร้าง Node และลองสั่ง print ดู
»> node = Node("test")
»> print node
เพื่อทำให้น่าสนใจ เราต้องการ list มากกว่าหนึ่ง node
»> node1 = Node(1)
»> node2 = Node(2)
»> node3 = Node(3)
จาก code นี้จะมีการสร้าง node ขึ้นมา 3 nodes แต่เรายังไม่ได้ list เพราะแต่ละ nodes ยังไม่มีการสร้าง linked โดยจะได้ state diagram ดังนี้
เพื่อเชื่อม nodes เราจะต้องทำให้ node แรกอ้างอิงไป node ที่ 2 และ node ที่ 2 อ้างอิงไปยัง node ที่ 3
»> node1.next = node2
»> node2.next = node3
Node ที่ 3 จะอ้างอิงไปที่ None ซึ่งเป็นจุดที่บอกถึงจุดจบของ list โดยตอนนี้จะมี state diagram ดังนี้
ในตอนนี้คุณก็รู้วิธีสร้าง nodes และ link พวกมันให้กลายเป็น list แล้ว ซึ่งอาจจะทำให้คุณหายสงสัยได้เล็กน้อย
17.3 Lists as collections
17.3 Lists as collections.
List มีประโยชน์การใช้งานมากเนื่องจากสามารถรวม object หลายๆ object ให้เป็น entity เดียวกันได้ ซึ่งบางครั้งจะเรีกว่า collection เช่น node แรกของ list ใช้สำหรับอ้างอิงถึง list ทั้งหมด
เมื่อใช้ list เป็น parameter ในการส่งผ่านค่า เราจะใช้เฉพาะ node แรกของ list ในการผ่านรายการ เป็นต้นว่า ในฟังก์ชัน printList จะรับค่า argument เป็นค่า node หนึ่ง node เริ่มต้นจากหัวของ list (head) พิมพ์ค่า node แต่ละอันไปจนถึง node สุดท้าย
def printList(node):
while node:
print node,
node = node.next
print
เพื่อเรียกใช้ฟังก์ชันนี้ เราจะส่งค่า node แรกของ list เข้าไป
»> printList(node1)
1 2 3
ใน printList เรามีตัวที่อ้างอิงถึง node แรกใน list แต่ไม่มีตัวแปรที่อ้างอิงถึง node อื่นๆใน list เราจะต้องใช้ค่า next จาก node แต่ละอันเพื่อไปยัง node ถัดไป
เพื่อดูการทำงานภายใน linked list เราจะใช้ตัวแปรแทน node ในการวน loop เพื่อเข้าถึง nodes แต่ละอันที่เชื่อมต่อกัน
Diagram นี้แสดงให้เห็นถึง nodes ที่อยู่ภายใน list และค่าที่ node นั้นเก็บไว้
เป็นข้อตกลงกันแล้วว่าค่าของ list จะถูกพิมพ์ออกมาจะอยู่ในรูปแบบ [1, 2, 3] ดังนั้นจึงเป็นแบบฝึกหัดของคุณที่จะต้องทำการแก้ไข printList เพื่อให้มันสร้างผลลัพธ์ในรูปแบบนี้
17.4 Lists and recursion
17.4 Lists and recursion.
การที่จะแสดงถึง operations ต่างๆของ list จะต้องใช้ recursive method เป็นต้นว่าการจะพิมพ์ค่าใน list ออกมาแบบย้อนหลังจะต้องใช้ recursive algorithm ดังนี้
1. แบ่ง list ออกเป็น 2 ส่วน ส่วนแรกคือให้ node ที่หนึ่งเป็น head ส่วนที่ 2 ให้ node ถัดไปเป็น tail
2. พิมพ์ค่าจาก tail ก่อน
3. พิมพ์ค่า head
ในขั้นตอนที่ 2 จะมี recursive call ซึ่งนั่นทำให้เราสันนิษฐานได้ว่าสามารถพิมพ์ค่าย้อนหลังได้ แต่ถ้าเราสันนิษฐานว่า recursive call นั้นถูกต้องแล้ว --the leap of faith-- เราก็สามารถเชื่อใน algorithm ที่เราคิดขึ้นว่าสามารถใช้งานได้
ทั้งหมดที่เราต้องการคือการใช้การพิสูจน์ base case เพื่อให้สามารถใช้กับ list ใดๆก็ได้เพื่อติดตามถึงผลลัพธ์สุดท้ายในที่นี้จะทำการกำหนดให้เมื่อมีการใส่ค่า list ที่ว่างเปล่าก็จะมีการแสดงค่าเป็น None
def printBackward(list):
if list == None: return
head = list
tail = list.next
printBackward(tail)
print head,
 ในบรรทัดแรกจะจัดการกับ base case โดยการไม่มีการทำงานใดๆเกิดขึ้น สองบรรทัดต่อมาจะทำการแบ่ง list ใส่ใน head และ tail สองบรรทัดสุดท้ายจะทำการพิมพ์ค่า list จุดจุลภาคที่จุดจบของบรรทัดสุดท้ายเป็นการบอกให้พิมพ์บรรทัดใหม่หลังจากพิมพ์ node ทุกอันแล้ว
 เราเรียกใช้ฟังก์ชันนี้เหมือนตอนเรียกใช้ printList
 »> printBackward(node1)
3 2 1
ผลลัพธ์ที่ได้คือการพิมพ์ค่าใน list ย้อนหลัง
คุณอาจจะรู้สึกสงสัยว่าทำไม printList และ printBackward คือฟังก์ชัน และไม่ใช่ methods ในคลาส Node เหตุผลก็คือเราต้องการใช้ None แสดงรายการว่างเปล่า และมันไม่มีวิธีที่จะเรียก method บนค่า None ข้อจำกัดนี้ทำให้มันไม่สะดวกที่จะเขียน code จัดการ list ในสไตล์ clean object-oriented
เราจะพิสูจน์ว่า printBackward สามารถทำงานได้สิ้นสุดตลอดหรือไม่ กล่าวอีกอย่างหนึ่งคือมันสามารถครอบคลุม base case ทั้งหมดหรือไม่ ในความเป็นจริงแล้วคำตอบคือไม่ list บางอันจะทำให้ฟังก์ชันนี้ล้มเหลวได้
17.5 Infinite lists
17.5 Infinite lists.
ไม่มีสิ่งใดที่ป้องกัน node ไม่ให้อ้างอิงไปยัง node ก่อนหน้ารวมถึงตัวมันเองด้วย ดังเช่นตัวอย่างตามภาพนี้ แสดงให้เห็นว่ามี list ที่ข้างในมี nodes 2 อันมีอยู่หนึ่งอันที่อ้างอิงมายังตัวมันเอง
ถ้าเราเรียกใช้ printList หรือ printBackward กับ list นี้จะทำให้เกิดการวน loop แบบไม่มีที่สิ้นสุด เพราะพฤติกรรมนี้ทำให้ยากที่จะทำงานกับมัน
 แต่ทว่าในบางครั้งพวกมันก็มีประโยชน์ เช่น เราอาจต้องการแสดงตัวเลขเป็น list ของ digits ทำให้ต้องใช้ infinite list ในการแสดงเศษส่วนซ้ำ
 โดยไม่คำนึงว่ามันสร้างปัญหาเราไม่สามารถพิสูจน์ได้ว่า printList และ printBackward จะทำงานได้สิ้นสุด ที่ดีทีสุดที่เราสามารถทำได้คือการใช้สมมุติฐานว่า “ ถ้า list ไม่มีการใช้ loop ฟังก์ชันเหล่านี้ก็จะทำงานได้สิ้นสุด ” ซึ่งเราจะเรียกสิ่งนี้ว่า precondition มันกำหนดข้อจำกัดบน parameters และอธิบายพฤติกรรมของฟังก์ชัน ถ้าข้อจำกัดเป็นที่พอใจ ซึ่งจะได้เห็นตัวอย่างมากกว่านี้ในไม่ช้านี้
17.6 The fundamental ambiguity theorem
17.6 The fundamental ambiguity theorem.
Code ส่วนนี้ใน printBackward อาจทำให้คุณสงสัยได้
 head = list
tail = list.next
หลังจาก assignment แรก ค่า head และ list มีชนิดของข้อมูลและค่าเดียวกัน แล้วเหตุใดเราจึงสร้างตัวแปรใหม่ขึ้นมา
เหตุผลก็เพื่อให้ตัวแปรทั้งสองตัวเล่นบทบาทที่แตกต่างกัน โดยเราคิดให้ head อ้างอิงไปที่ node เดียว และเราคิดให้ list อ้างอิงไปยัง node แรกของ list ซึ่ง “ บทบาท ” เหล่านี้ไม่ใช่ส่วนหนึ่งของโปรแกรม แต่อยู่ในความคิดของโปรแกรมเมอร์
โดยทั่วไปเราไม่สามารถบอกได้ว่าตัวแปรแต่ละตัวเล่นบทบาทอะไรโดยดูแค่ตัวโปรแกรม การเขียนโปรแกรมที่มีความหมายที่คลุมเครือนี้อาจมีประโยชน์ แต่มันทำให้อ่านได้ยาก เราใช้ตัวแปรที่ตั้งชื่อเป็น node และ list ในเอกสารนี้เป็นการตั้งใจที่จะทำให้ตัวแปรที่ใช้อยู่ และตัวแปรที่สร้างขึ้นมาใหม่ลดความคลุมเครือลง
เราสามารถเขียน printBackward โดยไม่ใช้ตัวแปร head และ tail ก็ได้ ซึ่งทำให้มันสั้นกว่าแต่ทำให้เมื่ออ่านแล้วเข้าใจยาก
def printBackward(list) :
if list == None : return
printBackward(list.next)
print list,
 ดูที่การเรียกใช้ฟังชันสองครั้ง เราจำได้ว่า printBackward รับค่าที่เป็น collection และพิมพ์ค่าออกมาเป็น single object
 The fundamental ambiguity theorem จะอธิบายถึงความคลุมเครือในการซึ่งมีอยู่ในการอ้างอิงถึง node
 ตัวแปรที่อ้างอิงถึง node นั้นเก็บ node ไว้เป็น single object หรือ node แรกของ list
17.7 Modifying lists
17.7 Modifying lists.
มีอยู่สองทางที่จะแก้ไข linked list ได้ ที่ชัดเจนที่สุดคือเราสามารถเปลี่ยนข้อมูลใน cargo ของ node หนึ่งในหลายๆ nodes ได้ แต่ operations ที่ต้องการมากกว่านั่นคือการ add, remove หรือ reorder
 เพื่อเป็นตัวอย่างเราลองมาเขียนฟังก์ชันที่ remove node ที่สองและ returns ค่า node ที่ทำการremove ออกมา
 def removeSecond(list):
if list == None: return
first = list
second = list.next

make the first node refer to the third


separate the second node from the rest of the list

return second
 อีกครั้งที่เราใช้ตัวแปรชั่วคราวที่ทำให้อ่านได้ง่ายมากยิ่งขึ้น และการใช้ฟังก์ชันทำได้ดังนี้
 »> printList(node1)
1 2 3
»> removed = removeSecond(node1)
»> printList(removed)
2
»> printList(node1)
1 3
State diagram นี้แสดงถึงผลการทำงานของฟังก์ชันนี้
จะเกิดอะไรขึ้นถ้าเรียกฟังก์ชันนี้โดยใส่ค่า list ที่มีสามาชิกเพียงตัวเดียว (a singleton) เข้าไป จะเกิดอะไรขึ้นถ้าใส่ list ที่ว่างเปล่าเข้าไป ทั้งสองคำถามนี้คือการ precondition ของฟังก์ชันนี้ ดังนั้นเราจึงต้องทำให้ฟังก์ชันนี้รองรับกับสองสิ่งนี้ตามความเหมาะสม 
17.8 Wrappers and helpers
17.8 Wrappers and helpers.
มันเป็นประโยชน์ที่จะแบ่ง operation ของ list ที่ใช้บ่อยๆเป็นสองฟังก์ชัน เป็นต้นว่าต้องการพิมพ์ค่าย้อนหลังในรูปแบบ [3 2 1] เราสามารถใช้ printBackward เพื่อพิมพ์ค่า 3 2 1 แต่เราต้องการแบ่งฟังก์ชันในการพิมพ์วงเล็บออกมา ซึ่งจะเรียกมันว่า printBackwardNicely
 def printBackwardNicely(list) :
print "[",
printBackward(list)
print "]",
 และอีกครั้งหนึ่งมันเป็นการดีที่จะตรวจสอบว่าฟังก์ชันนี้สามารถใช้งานได้กับ list ที่ว่างเปล่า หรือ singleton ได้หรือไม่
 เมื่อเราใช้ฟังก์ชันนี้ภายในโปรแกรม เราสามารถเรียก printBackwardNicely ได้โดยตรง ซึ่งมันจะเรียก printBackward เอง ซึ่งจะเรียก printBackwardNicely ว่าทำงานเป็น wrapper และใช้ printBackward เป็น helper
17.9 The LinkedList class
17.9 The LinkedList class.
มีปัญหาที่แทบจะมองไม่เห็นจำนวนหนึ่งในการ implementing lists ในการหาสาเหตุ และผลกระทบ เราต้องวางแผนในการเลือก implement ก่อนแล้วจึงอธิบายเอาไว้ว่ามันแก้ปัญหาอะไร
 อันดับแรกเราจะสร้างคลาสชื่อ LinkedList โดยมี attributes เป็น integer เก็บค่าขนาดของ list และอ้างอิงไปยัง node แรก LinkedList objects ใช้สำหรับจัดการ lists ของ Node objects
 class LinkedList :
def __init__(self) :
self.length = 0
self.head = None
 สิ่งหนึ่งที่ดีสำหรับคลาส LinkedList คือการที่มันสมารถใส่ wrapper อย่าง printBackwardNicely ได้อย่างเป็นธรรมชาติ โดยเราสามารถสร้างเป็น method ของคลาส LinkedList
 class LinkedList:
def printBackward(self):
print "[",
if self.head != None:
self.head.printBackward
print "]",
 class Node:
def printBackward(self):
if self.next != None:
tail = self.next
tail.printBackward
print self.cargo,
 เพื่อทำให้สับสนเล็กน้อยเราได้ทำการเปลี่ยนชื่อ printBackwardNicely ในตอนนี้จะมี method ที่ชื่อ printBackward อยู่สองตัว ตัวแรกในคลาส Node (the helper) และอีกตัวในคลาส LinkedList (the wrapper) เมื่อ wrapper ถูกเรียกใช้ self.head.printBackward มันก็จะไปเรียก helper เพราะ self.head เป็น Node object
 ประโยชน์อีกอย่างของคลาส LinkedList คือมันทำให้ง่ายในการ add และ remove สมาชิกตัวแรกของ list เช่น addFirst คือ method สำหรับคลาส LinkedList การทำงานคือมันจะรับค่าของ cargo แล้วใส่มันลงในจุดเริ่มต้นของ list
 class LinkedList:
def addFirst(self, cargo):
node = Node(cargo)
node.next = self.head
self.head = node
self.length = self.length + 1
 และก็เหมือนเดิมคุณควรตรวจสอบให้มันรองรับกรณีพิเศษต่างๆที่อาจจะเกิดขึ้นได้ เช่น การใส่ลงใน list ที่ว่างเปล่าตั้งแต่ต้น
17.10 Invariants
17.10 Invariants.
List บางอันมีรูปแบบที่ดี บางอันก็ไม่ เป็นต้นว่าถ้า list นั้นมีการวนซ้ำมันก็จะทำให้ method ของเราจำนวนมากใช้งานไม่ได้ ดังนั้นเราจึงต้องการ list ที่ไม่มีการวนซ้ำ และสิ่งที่ต้องการอีกสิ่งหนึ่งคือค่า length ใน LinkedList object จะต้องมีค่าเท่ากับจำนวน nodes ใน list
 สิ่งที่เราต้องการเหล่านี้เรียกว่า invariants เพราะในความคิดแล้วค่าเหล่านี้ควรจะถูกต้องในทุกๆ object ตลอดเวลา การระบุ invariants สำหรับ object ถือเป็นแนวทางปฏิบัติที่มีประโยชน์ในการเขียนโปรแกรม เพราะว่ามันทำให้ง่ายในการพิสูจน์ความถูกต้องของ code ความสมบูรณ์ของโครงสร้างข้อมูล และการตรวจสอบข้อผิดพลาด
 สิ่งหนึ่งที่บางครั้งอาจทำให้สับสนเกี่ยวกับ invariants คือการเรียงลำดับการทำงานไม่ถูกต้องทำให้เกิดการละเมิด เช่น ในส่วนกลางของ addFirst ถ้าเราเพิ่มค่า length หลังจากนั้นจึงพิ่ม node ถือเป็นการเรียงที่ผิดทำให้เกิดการละเมิด แต่เราสามารถยอมรับให้มันเกิดขึ้นได้ มันเป็นไปไม่ได้ที่จะแก้ไข object โดยปราศจากการละเมิด invariants อย่างน้อยที่สุดมันจะต้องเกิดขึ้นเล็กน้อย
 ตามปกติเราต้องการให้ทุกๆ method ที่มีการละเมิด invariant จะต้องได้รับการแก้ไข
 ถ้ามีบางส่วนที่สำคัญของ code มีซึ่งไม่ต้องการให้เกิดการละเมิด invariant จึงควรทำ comment เอาไว้บอกให้ชัดเจน ดังนั้นจึงไม่มี operations ใดๆที่ขึ้นกับ invariant
17.11 Glossary
17.11 Glossary.
embedded reference: A reference stored in an attribute of an object.
linked list: A data structure that implements a collection using a sequence of linked nodes.
node: An element of a list, usually implemented as an object that contains a reference to another object of the same type.
cargo: An item of data contained in a node.
link: An embedded reference used to link one object to another.
precondition: An assertion that must be true in order for a method to work correctly.
fundamental ambiguity theorem: A reference to a list node can be treated as a single object or as the first in a list of nodes.
singleton: A linked list with a single node.
wrapper: A method that acts as a middleman between a caller and a helper method, often making the method easier or less error-prone to invoke.
helper: A method that is not invoked directly by a caller but is used by another method to perform part of an operation.
invariant: An assertion that should be true of an object at all times (except perhaps while the object is being modified).