เชี่ยวชาญ Linked List ใน Ruby: คู่มือปฏิบัติจริง

นี่คือบทความที่ 3 ในซีรีส์ "Practical Computer Science in Ruby"! วันนี้เราจะพูดถึง linked list

Linked list คืออะไร?

จากชื่อมันบอกว่า linked list เป็นวิธีจัดเก็บข้อมูลในรูปแบบรายการ (ขอบคุณ คัปตันโอเวียส!)

ส่วน "linked" มาจากข้อเท็จจริงที่ว่าข้อมูลถูกเก็บในโหนด (node) และโหนดเหล่านี้เชื่อมต่อกันแบบลำดับขั้น

มันต่างจากอาร์เรย์อย่างไร?

Linked List เทียบ Array

Linked list มีลักษณะประสิทธิภาพต่างจากอาร์เรย์ นั่นคือเหตุผลหนึ่งที่คุณอาจเลือกใช้ตัวหนึ่งแทนอีกตัว

นั่นหมายความว่า linked list อาจมีประสิทธิภาพมากกว่าสำหรับงานบางอย่าง

ใน linked list ไม่มีดัชนี (indexing) ไม่มีการเข้าถึงแบบสุ่ม (random access) หมายความว่า คุณไม่สามารถเข้าถึงรายการตรงกลางรายการได้ทันที

คุณต้องเริ่มที่ "หัว" (head) ของรายการ และติดตามลิงก์จนกว่าจะพบโหนดที่ต้องการ หรือจนถึงปลายรายการ

การลบ (หรือเพิ่ม) รายการจากกลาง linked list เร็วกว่ามาก

คุณแค่ต้องเปลี่ยน pointer "next" ของโหนดหนึ่ง

แต่ถ้าคุณอยากลบอิลิเมนต์จากกลางอาร์เรย์ คุณจะเหลือช่องว่าง และเพื่อปิดช่องว่างนั้น คุณต้องย้ายอิลิเมนต์ทั้งหมดทางขวาของอิลิเมนต์ที่ลบ

ไม่อย่างมีประสิทธิภาพเลยถ้าต้องทำบ่อย!

ถ้าอยากแทรกในกลางอาร์เรย์ ต้องย้ายอิลิเมนต์ทั้งหมดเพื่อสร้างช่องว่าง

มาดูตัวอย่างโค้ด:

 a = [1,2,3,4,5,6,7,8] def insert(arr, item, pos) tmp = arr[pos] arr[pos] = item arr.replace(arr[0..pos] + [tmp] + arr[pos+1..-1]) end insert(a, 99, 3) p a 

หมายเหตุ: Ruby มี Array#insert ในตัวแล้ว แต่ผมอยากแสดงว่ามันทำงานอย่างไร

ผลกระทบต่อประสิทธิภาพของการแทรกรายการตรงกลางรายการเป็นอย่างไร?

นี่คือ benchmark:

 Comparison: LinkedList: 1815407.9 i/s Array: 18090.3 i/s - 100.35x slower 

ต่างกันมาก แต่ก็ขึ้นอยู่กับขนาดของ LinkedList เพราะต้องค้นหาโหนด

อีกวิธีเปรียบเทียบโครงสร้างข้อมูลคือดูตาราง time complexity (สมมติว่าไม่ต้องค้นหาโหนดสำหรับ insertion และ deletion):

หาแอปพลิเคชันจริง?

นี่คือ pull request ของ Aaron Patterson ที่เขาเร่งความเร็ว RubyGems โดยใช้ linked list:

https://github.com/rubygems/rubygems/pull/1188

การนำ Linked List มาใช้งาน

Ruby ไม่มีคลาส LinkedList ตัวตน เราต้องสร้างเอง

เราต้องการอะไร:

• append (ท้ายรายการ)
• append_after
• delete
• find

นี่คือการนำไปใช้งานได้หนึ่งแบบ:

 class LinkedList def initialize @head = nil end def append(value) if @head find_tail.next = Node.new(value) else @head = Node.new(value) end end def find_tail node = @head return node if !node.next return node if !node.next while (node = node.next) end def append_after(target, value) node = find(target) return unless node old_next = node.next node.next = Node.new(value) node.next.next = old_next end def find(value) node = @head return false if !node.next return node if node.value == value while (node = node.next) return node if node.value == value end end def delete(value) if @head.value == value @head = @head.next return end node = find_before(value) node.next = node.next.next end def find_before(value) node = @head return false if !node.next return node if node.next.value == value while (node = node.next) return node if node.next && node.next.value == value end end def print node = @head puts node while (node = node.next) puts node end end end 

การนำไปใช้งานนี้ไม่เก็บตำแหน่ง tail ไว้ แต่หา tail ตอน append ใหม่ ทำให้ append ใช้เวลา linear (O(n)) ในวิดีโอด้านล่างผมแสดงอีกวิธีที่ append ที่หัว

และนี่คือคลาสโหนดของเรา:

 class Node attr_accessor :next attr_reader :value def initialize(value) @value = value @next = nil end def to_s "Node with value: #{@value}" end end 

ใช้งานได้แบบนี้:

 list = LinkedList.new list.append(10) list.append(20) list.append(30) list.append_after(10, 15) list.append_after(20, 25) list.print 

นี่คือการนำไปใช้งาน "Singly-Linked List" แบบพื้นฐาน

ยังมีประเภท linked list อื่น:

• Doubly-Linked List
• Circular Linked List

ใน doubly-linked list ทุกโหนดมี pointer 2 ตัว: ชี้ โหนดถัดไป และ โหนดก่อนหน้า

ทำให้ค้นหารายการยืดหยุ่นกว่า แต่ต้องทำงานเพิ่มตอนแก้ไขรายการ

Circular linked list เหมือน doubly-linked list แต่มันเชื่อมโหนดสุดท้ายกับ head

วิดีโอ

สรุป

คุณเรียนรู้ linked list โครงสร้างข้อมูลที่คุณควรพิจารณาถ้าทำการเพิ่ม/ลบอิลิเมนต์ตรงกลางอาร์เรย์บ่อย

มันอาจออกมใน coding interview ด้วย จึงคุ้มค่าที่จะเรียนแม้แค่เพื่อนั้น

อย่าลืม แชร์โพสต์นี้ ผ่านปุ่มด้านล่าง เพื่อให้คนอื่นได้ประโยชน์จากความรู้นี้ 🙂