รายการเชื่อมโยงที่ใช้งานได้จริงใน Ruby

นี่เป็นรายการที่ 3 ของซีรีส์ "Practical Computer Science in Ruby"! วันนี้เราจะมาพูดถึงรายการที่เชื่อมโยงกัน

แล้วรายการที่เชื่อมโยงคืออะไร

เช่นเดียวกับชื่อที่กล่าว รายการที่เชื่อมโยงเป็นวิธีหนึ่งในการจัดเก็บข้อมูลในรูปแบบรายการ (ขอบคุณ Captain Obvious!)

ส่วน "เชื่อมโยง" มาจากข้อเท็จจริงที่ว่าข้อมูลถูกเก็บไว้ในโหนด &โหนดเหล่านี้เชื่อมโยงกันในลักษณะที่ต่อเนื่องกัน

แตกต่างจากอาร์เรย์อย่างไร

รายการที่เชื่อมโยงเทียบกับอาร์เรย์

รายการที่เชื่อมโยงมีลักษณะการทำงานที่แตกต่างจากอาร์เรย์ นั่นเป็นเหตุผลหนึ่งที่คุณอาจต้องการเลือกข้อใดข้อหนึ่ง

ซึ่งหมายความว่ารายการที่เชื่อมโยงอาจมีประสิทธิภาพมากกว่าสำหรับงานบางอย่างมากกว่าอาร์เรย์

ในรายการที่เชื่อมโยง ไม่มีการจัดทำดัชนี ไม่มีการเข้าถึงแบบสุ่ม หมายความว่า คุณไม่สามารถเข้าถึงรายการที่อยู่ตรงกลางของรายการได้ .

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

การลบ (หรือเพิ่ม) รายการจากตรงกลางของรายการที่เชื่อมโยง เร็วกว่ามาก .

สิ่งที่คุณต้องทำคือเปลี่ยนตัวชี้ "ถัดไป" สำหรับโหนดเดียว

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

ไม่ค่อยมีประสิทธิภาพถ้าคุณต้องทำสิ่งนี้บ่อยๆ!

หากเราต้องการแทรกกลางอาร์เรย์ เราต้องย้ายองค์ประกอบอาร์เรย์ทั้งหมดเพื่อสร้างพื้นที่ว่าง

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

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

หมายเหตุ :นอกจากนี้ยังมีวิธี Array#insert ในตัว แต่ฉันต้องการแสดงให้คุณเห็นว่าวิธีนี้ทำงานอย่างไร

อะไรคือผลกระทบต่อประสิทธิภาพของการแทรกรายการที่อยู่ตรงกลางรายการ?

นี่คือเกณฑ์มาตรฐาน:

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

ความแตกต่างใหญ่ที่นี่ แต่ก็ขึ้นอยู่กับขนาดของ LinkedList เนื่องจากเราต้องค้นหาโหนด

อีกวิธีหนึ่งในการเปรียบเทียบโครงสร้างข้อมูลสองโครงสร้างคือการดูตารางความซับซ้อนของเวลา (ซึ่งถือว่าคุณไม่จำเป็นต้องค้นหาโหนดสำหรับการแทรกและการลบ):

กำลังมองหาแอปพลิเคชันในโลกแห่งความเป็นจริงอยู่ใช่หรือไม่?

นี่คือคำขอดึงโดย Aaron Patterson ซึ่งเขาเร่งความเร็ว Ruby Gems โดยใช้รายการที่เชื่อมโยง:

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

การใช้งานรายการที่เชื่อมโยง

Ruby ไม่รวม LinkedList เราจึงต้องสร้างคลาสขึ้นมาเอง

เราต้องการให้การดำเนินการต่อไปนี้พร้อมใช้งาน:

• ต่อท้าย (ต่อท้ายรายการ)
• append_after
• ลบ
• ค้นหา

นี่คือการใช้งานที่เป็นไปได้อย่างหนึ่ง:

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

การใช้งานเฉพาะนี้ไม่ได้ติดตามส่วนท้าย แต่จะพบส่วนท้ายเมื่อต่อท้ายรายการใหม่ สิ่งนี้ทำให้เวลาเชิงเส้นของการดำเนินการต่อท้าย (O(n) ). ในวิดีโอด้านล่าง ฉันจะแสดงให้คุณเห็นการใช้งานอื่น โดยฉันจะต่อท้ายองค์ประกอบที่ด้านหน้า

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

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” พื้นฐาน

คุณมีรายการที่เชื่อมโยงประเภทอื่นๆ ด้วย :

• รายการที่เชื่อมโยงแบบทวีคูณ
• รายการเชื่อมโยงแบบวงกลม

ในรายการที่เชื่อมโยงแบบทวีคูณ ทุกโหนดมีตัวชี้สองตัว:ตัวหนึ่งไปยัง โหนดถัดไป &อีกอันไปยัง โหนดก่อนหน้า .

ซึ่งช่วยให้ค้นหารายการมีความยืดหยุ่นมากขึ้น แต่ยังต้องดำเนินการเพิ่มเติมเมื่อทำการเปลี่ยนแปลงรายการ

รายการที่เชื่อมโยงแบบวงกลมจะเหมือนกับรายการที่เชื่อมโยงแบบทวีคูณ แต่โหนดสุดท้ายเชื่อมต่อกับโหนดหลัก

วิดีโอ

สรุป

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

นอกจากนี้ยังอาจเกิดขึ้นในการสัมภาษณ์เขียนโค้ดด้วย ดังนั้นจึงควรเรียนรู้แม้ว่าจะเป็นเพียงแค่เรื่องนั้นก็ตาม

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