By Arnon Puitrakul - 04 กุมภาพันธ์ 2021
จากตอนก่อน เราคุยกันในเรื่องของ Built-in Data Structure ใน Python ทั้งแต่ Array, List, Dict, Set และ Tuple วันนี้เรามาดู Data Structure ที่ Advance ขึ้นไปอีก และ ไม่มีมาให้ Python เราจะต้อง Implement เองอย่าง Linked List, Stack, Queue, Tree และ Graph เราลองเขียนแล้วพบว่ามันยาวมาก ๆ วันนี้เราจะเอา Linked List มาเล่าก่อน แล้วสัปดาห์ต่อ ๆ ไป เราค่อยมาดูเรื่องที่เหลือกัน
Linked List เป็น Data Structure ประเภทหนึ่งที่มีลักษณะเป็นเส้นตรง ของข้อมูลต่อ ๆ กัน โดยส่วนประกอบของแต่ละ Node เราจะแบ่งเป็น 2 ส่วนคือ Data สำหรับเก็บข้อมูล และ Next สำหรับ Reference ของ Node ต่อไป
ใน Node แรก เราจะเรียกว่า Head จากนั้นใน Next ของ Head จะชี้ไปที่ Node ต่อไป ทำแบบนี้ไปเรื่อย ๆ จนถึง Node สุดท้าย ก็จะชี้ไปที่ None เป็นอันจบ เข้าใจ Concept แล้ว เราลองมาเขียนใน Python กัน
class Node :
def __init__ (self, data) :
self.data = data
self.next = None
class LinkedList :
def __init__ (self):
self.head = None
จาก Code ด้านบน เราสร้าง Class ขึ้นมา 2 Class คือ Node และ LinkedList โดยที่ใน Class Node จะแทน Node ตามชื่อถึงอย่างที่เราเล่า มันจะมีส่วนประกอบทั้งหมด 2 อย่างด้วยกันคือ Data และ Next ใน Consturctor เราจะเริ่มต้นให้เป็น None ไปก่อน ไว้ เราจะต่อ เราค่อยกำหนดค่าให้มันได้
และ Class LinkedList เป็น Class สำหรับสร้างเป็น Instance ของ Linked List ซึ่งแน่นอนว่า เราจะต้องเก็บหัวของมัน
first_node = Node(1)
second_node = Node(2)
third_node = Node(3)
ในตัวอย่างนี้ เราจะเริ่มต้นจากการสร้าง Node 3 ตัวขึ้นมาก่อน โดยที่ ปลายทางเราต้องการให้ต่อเป็น 1 -> 2 -> 3
linked_list = LinkedList()
linked_list.head = first_node
เราเริ่มจากสร้าง LinkedList ขึ้นมา พร้อมกับบอกมันว่า Head จะเป็น first_node
second_node.next = third_node
linked_list.head.next = second_node
ในขั้นตอนต่อไป เราจะทำการต่อ second_node และ third_node เข้ากับ first_node ที่เป็น Head ใน Linked List ที่เราสร้างเอาไว้แล้ว เราเริ่มจาก ต่อ second_node และ third_node เข้าด้วยกันก่อน โดยบอกว่า next ของ second_node เป็น third_node และขั้นตอนต่อไป เราก็เอา second_node และ thrid_node ที่ต่อแล้ว ต่อเข้ากับ first_node ก็เป็นอันจบ
เราลองมาดูกันบ้างดีกว่า ว่าถ้าเราอยากจะ Traversal เราจะทำยังไง เราต้องอย่าลืมนะว่า Linked List ไม่ใช่ List ที่เราจะเข้าถึงข้อมูลจาก Index ตรง ๆ ได้ เราจะต้องเข้าถึงจาก Head แล้วชี้ไปที่ Element ต่อไปเท่านั้น
def __str__ (self) :
final_string = ''
current_node = self.head
while current_node != None :
final_string += str(current_node.data)
if current_node.next != None :
final_string += str(current_node.data) + ' -> '
current_node = current_node.next
ในตัวอย่างนี้เราจะมาเขียน Method ที่เมื่อเราเรียก str() กับ Object เราจะให้มันออกมาหน้าตาเป็นอย่างไร อันนี้ลองไปอ่านเพิ่มเติมในเรื่อง Class ใน Python ได้ ซึ่งเป้าหมายที่เราต้องการให้มันออก คือ "1 -> 2 -> 3"
เราเลยเขียนง่าย ๆ เลย จุดเริ่มต้น เราจะต้องเริ่มจาก Head ก่อน ใน Linked List เราหยิบ Node Head มาก่อน ให้เป็น current_node จากนั้น เราก็ While Loop ไป โดยที่เรารู้ว่า Node สุดท้าย Next มันต้องเป็น None แน่ ๆ เราก็ Loop ไปเรื่อย ๆ จน กว่าเราจะเจอว่า current_node เป็น None ก็จบแล้ว
ใน Loop เราก็ให้มัน Append ค่าของ Node ปัจจุบันเข้าไป จากนั้นเราจะเอาลูกศรใส่เข้าไป แต่ปัญหาคือ ถ้าเราใส่เข้าไปตรง ๆ เลย เราจะได้ออกมาเป็น "1 -> 2 -> 3 ->" จะเห็นว่าอันสุดท้าย มันมีลูกศรเกินมาตัวนึง
คิดเร็ว ๆ เราก็แก้ง่าย ๆ เขียนเงื่อนไขขึ้นมาเพิ่มว่า ถ้า Node ต่อไป ไม่ใช่ None หมายความว่า มันมี Node ต่อไปแน่ ๆ เราก็ใส่ลูกศร เพื่อให้ Data ของ Node ต่อไปมา มันจะได้มีลูกศรคั่นก่อนนั่นเอง
อีกหนึ่ง Application ของ Traversal คือการทำ Search เพื่อหาว่าใน Linked List มันมี Data ที่เราต้องการรึเปล่า ใช้วิธีการเดียวกับ Traversal เลย แต่เราเพียงเพิ่มเงื่อนไขว่า ถ้าเจอแล้วให้ Return เป็น True เท่านั้นเอง
def search (self, target) :
found = False
current_node = self.head
while current_node != None and found != True :
if current_node.data == target :
found = True
return found
จากด้านบน เราเริ่มจากการกำหนด Boolean ขึ้นมาตัวนึงเป็น Flag ว่าเราเจอรึยัง จากนั้น เราก็ Traversal ปกติ แต่เราเพิ่มการเช็คว่า มันเจอ Data ตรงกับที่เราต้องการจะหารึยังเท่านั้นเลย ถ้าไม่เจอมันก็จะลูปจนเจอตัวสุดท้ายแล้วหลุดออกมา
ถัดไปคือ เราจะมาเพิ่มข้อมูลกัน เริ่มจากอะไรที่ง่าย ๆ ก่อนคือการเติม Node เข้าไปที่อันแรกของ Linked List พูดง่าย ๆ คือ Head จะเป็น Node ใหม่นั่นเอง ทำยังไงดีละ
def insert (self, data) :
new_node = Node(data)
new_node.next = self.head
self.head = new_node
ก็คือ เราเริ่มจากเราสร้าง Node โดยอัด Data ไปก่อน ทีนี้เราบอกว่า เราอยากจะเพิ่ม Node เข้าไปที่หัวของมันแปลว่า Node ที่เราสร้างขึ้นมาใหม่ Node ต่อไปของมันจะต้องเป็น Head อันปัจจุบัน เราก็เซ็ตไปในบรรทัดที่ 3 ของ Code ด้านบน และ สุดท้าย ก็ให้ Head ของ Linked List ตัวนี้เป็น Node ใหม่ก็เรียบร้อยแล้ว จะเห็นว่า เรียบง่ายตาม Logic ทั่ว ๆ ไปเลย และ ใช้ O(1) เท่านั้น เร็วมาก ๆ
ลองมาดูอะไรที่พิเรนทร์กว่านั้นกัน เราทำสลับกันบ้าง ถ้าเราอยากจะ Append ไปที่อันสุดท้าย เราจะทำยังไงดี ???
def append (self, data) :
new_node = Node(data)
current_node = self.head
while current_node != None :
if current_node.next == None :
current_node.next = new_node
Goal ของเราคือ เราจะต้องทำให้ Next ของ Node สุดท้ายจาก None เป็น Node ที่เราสร้างขึ้นใหม่ ซึ่งคิดเข้าไปอีก Node สุดท้ายก็คือ Node ที่ Next เป็น None นั่นเอง ทำให้เราจะต้อง Loop หาไปเรื่อย ๆ จนกว่าจะเจอว่า Next ของ Node ไหนเป็น None จากใน Condition ที่อยู่ใน For Loop และ เรากำหนด Next ให้เป็น Node ใหม่ก็จะเรียบร้อย ดังนั้นวิธีนี้เราจะใช้ O(n) นั่นเอง
และสุดท้าย เรามาลองลบข้อมูลออกจาก Linked List กันบ้าง วิธีการก็คือ เมื่อเราเจอ Node ที่เราต้องการ เราก็เอามันออก และ Link Previous Node เข้ากับ Next Next Node ลองมาดู Code กัน
def delete_node (self, target) :
current_node = self.head
while current_node != None :
if current_node.next.data == target :
current_node.next = current_node.next.next
จะเห็นว่า เราทำง่าย ๆ เลย เราแค่ เช็คเลยว่า ถ้า Node ต่อไป data เป็นสิ่งที่เราต้องการ เราก็ตัดสายอันต่อไป แล้วเปลี่ยนเป็นอันถัด ๆ ไปแทน ก็เรียบร้อยแล้ว
Linked List เป็น Data Structure ประเภทนึงที่การเข้าถึงข้อมูลเราไม่สามารถที่จะเข้าถึงตรง ๆ ได้ เราสามารถเข้าถึงได้จากหัว (Head) เท่านั้น โดยที่ใน Data เราสามารถเก็บอะไรก็ได้ลงไป สนใจแค่ Core Concept ที่ว่า มันจะต้องต่อ ๆ กันเป็นเส้นเท่านั้นเองใน Linked List ที่เราสอนในวันนี้เป็น Singly Linked List ที่เราจะเก็บแค่ Data กับ Next Node เท่านั้น แต่ถ้าเป็น Doubly Linked List เราจะเก็บ Previous เพื่อเป็น Pointer สำหรับชี้ไปที่ Node ก่อนหน้า ทำให้เราสามารถเดินย้อนกลับไป Node ก่อนหน้าได้ อาทิตย์ต่อไป เราจะมา Implement เรื่องของ Queue และ Stack กัน
เราเป็นคนที่อ่านกับซื้อหนังสือเยอะมาก ปัญหานึงที่ประสบมาหลายรอบและน่าหงุดหงิดมาก ๆ คือ ซื้อหนังสือซ้ำเจ้าค่ะ ทำให้เราจะต้องมีระบบง่าย ๆ สักตัวในการจัดการ วันนี้เลยจะมาเล่าวิธีการที่เราใช้ Obsidian ในการจัดการหนังสือที่เรามีกัน...
หากเราเรียนลงลึกไปในภาษาใหม่ ๆ อย่าง Python และ Java โดยเฉพาะในเรื่องของการจัดการ Memory ว่าเขาใช้ Garbage Collection นะ ว่าแต่มันทำงานยังไง วันนี้เราจะมาเล่าให้อ่านกันว่า จริง ๆ แล้วมันทำงานอย่างไร และมันมีเคสใดที่อาจจะหลุดจนเราต้องเข้ามาจัดการเองบ้าง...
ก่อนหน้านี้เราเปลี่ยนมาใช้ Zigbee Dongle กับ Home Assistant พบว่าเสถียรขึ้นเยอะมาก อุปกรณ์แทบไม่หลุดออกจากระบบเลย แต่การติดตั้งมันเข้ากับ Synology DSM นั้นมีรายละเอียดมากกว่าอันอื่นนิดหน่อย วันนี้เราจะมาเล่าวิธีการเพื่อใครเอาไปทำกัน...
เมื่อหลายวันก่อนมีพี่ที่รู้จักกันมาถามว่า เราจะโหลด CSV ยังไงให้เร็วที่สุด เป็นคำถามที่ดูเหมือนง่ายนะ แต่พอมานั่งคิด ๆ ต่อ เห้ย มันมีอะไรสนุก ๆ ในนั้นเยอะเลยนี่หว่า วันนี้เราจะมาเล่าให้อ่านกันว่า มันมีวิธีการอย่างไรบ้าง และวิธีไหนเร็วที่สุด เหมาะกับงานแบบไหน...