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

บทที่ 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

เหมือนเช่นเคยเมื่อการเขียนคลาสใหม่ เราจะเริ่มด้วยการเขียน 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

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

การที่จะแสดงถึง 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

ไม่มีสิ่งใดที่ป้องกัน 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

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

มีอยู่สองทางที่จะแก้ไข 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

1. make the first node refer to the third

first.next = second.next

1. separate the second node from the rest of the list

second.next = None

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

มันเป็นประโยชน์ที่จะแบ่ง 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

มีปัญหาที่แทบจะมองไม่เห็นจำนวนหนึ่งในการ 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

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

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).