Data Structure ใน Python แบบง่าย ๆ (ตอน Linked List)

จากตอนก่อน เราคุยกันในเรื่องของ 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

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

เราลองมาดูกันบ้างดีกว่า ว่าถ้าเราอยากจะ 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 ต่อไปมา มันจะได้มีลูกศรคั่นก่อนนั่นเอง

Searching

อีกหนึ่ง 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 ตรงกับที่เราต้องการจะหารึยังเท่านั้นเลย ถ้าไม่เจอมันก็จะลูปจนเจอตัวสุดท้ายแล้วหลุดออกมา

Adding 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) นั่นเอง

Deleting

และสุดท้าย เรามาลองลบข้อมูลออกจาก 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 กัน