Deall Rhestrau Cysylltiedig Ruby

Mae rhestrau cysylltiedig yn strwythurau data hanfodol yn y byd rhaglennu, ac maent yn cynnig dulliau effeithiol o storio a rheoli data. Yn yr erthygl hon, byddwn yn archwilio rhestrau cysylltiedig yn Ruby, gan drafod eu strwythur, eu manteision, a sut i'w defnyddio. Byddwn hefyd yn cynnwys enghreifftiau o god i helpu i ddangos sut mae rhestrau cysylltiedig yn gweithio yn ymarferol.

Beth yw Rhestrau Cysylltiedig?

Mae rhestr gysylltiedig yn strwythur data sy'n cynnwys cyfres o nodau, lle mae pob nod yn cynnwys dwy elfen: gwerth a chysylltiad â'r nod nesaf. Mae hyn yn wahanol i dablau, sy'n defnyddio cyfeiriadau cyson i storio data. Mae rhestrau cysylltiedig yn cynnig mwy o hyblygrwydd wrth ychwanegu neu ddileu nodau, gan nad ydynt yn gorfod symud data fel y byddai'n digwydd mewn tabl.

Strwythur Rhestr Gysylltiedig

Mae'r strwythur sylfaenol ar gyfer nod yn rhestr gysylltiedig yn cynnwys:

Gwerth: Y data a storir yn y nod.
Cysylltiad: Cyfeiriad at y nod nesaf yn y rhestr.

Mae'r nodau hyn yn gysylltiedig â'i gilydd, gan greu cadwyn o nodau. Mae'r nod cyntaf yn y rhestr yn cael ei alw'n "pen" neu "ben rhestr," ac mae'r nod olaf yn cael ei alw'n "gwrthrych" neu "gwrthrych olaf."

Manteision Rhestrau Cysylltiedig

Mae rhestrau cysylltiedig yn cynnig nifer o fanteision dros dablau, gan gynnwys:

Hyblygrwydd: Mae'n hawdd ychwanegu neu ddileu nodau heb orfod symud data eraill.
Defnydd o gofrestrfa: Mae rhestrau cysylltiedig yn defnyddio llai o gofrestrfa pan fyddant yn cael eu defnyddio'n effeithiol.
Gweithrediadau cyflym: Mae gweithrediadau fel ychwanegu a dileu yn gyflymach na'r rhai ar dablau, yn enwedig pan fydd y rhestr yn fawr.

Mathau o Rhestrau Cysylltiedig

Mae yna sawl math o rhestrau cysylltiedig, gan gynnwys:

Rhestr Gysylltiedig Unffordd: Mae gan bob nod gysylltiad â'r nod nesaf yn unig.
Rhestr Gysylltiedig Ddwyffordd: Mae gan bob nod gysylltiad â'r nod nesaf a'r nod blaenorol.
Rhestr Gysylltiedig Cylchol: Mae'r nod olaf yn cysylltu â'r nod cyntaf, gan greu cylch.

Sut i Ddefnyddio Rhestrau Cysylltiedig yn Ruby

Mae creu rhestr gysylltiedig yn Ruby yn syml. Gadewch i ni edrych ar sut i greu rhestr gysylltiedig unffordd. Yn gyntaf, bydd angen i ni greu dosbarth ar gyfer y nod:

class Node
  attr_accessor :value, :next_node

  def initialize(value)
    @value = value
    @next_node = nil
  end
end

Yma, rydym wedi creu dosbarth Node sy'n cynnwys gwerth a chysylltiad â'r nod nesaf. Nawr, gadewch i ni greu dosbarth ar gyfer y rhestr gysylltiedig:

class LinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end

  def append(value)
    new_node = Node.new(value)
    if @head.nil?
      @head = new_node
    else
      current = @head
      current = current.next_node while current.next_node
      current.next_node = new_node
    end
  end

  def display
    current = @head
    while current
      print "#{current.value} -> "
      current = current.next_node
    end
    puts "nil"
  end
end

Yn y dosbarth LinkedList, rydym wedi creu dull i ychwanegu nodau a dull i ddangos y rhestr. Gallwn nawr ddefnyddio'r dosbarth hwn i greu rhestr gysylltiedig:

list = LinkedList.new
list.append(1)
list.append(2)
list.append(3)
list.display

Pan fyddwn yn rhedeg y cod hwn, byddwn yn gweld y canlyniad canlynol:

1 -> 2 -> 3 -> nil

Ychwanegu Gweithrediadau Eraill

Mae'n bwysig gallu gweithredu ar y rhestr gysylltiedig. Gadewch i ni ychwanegu dulliau i ddileu nod a chanfod gwerth:

def delete(value)
  return if @head.nil?

  if @head.value == value
    @head = @head.next_node
    return
  end

  current = @head
  while current.next_node
    if current.next_node.value == value
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

def find(value)
  current = @head
  while current
    return current if current.value == value
    current = current.next_node
  end
  nil
end

Yma, rydym wedi creu dull delete i ddileu nod o'r rhestr a dull find i chwilio am nod. Gallwn nawr ddefnyddio'r dulliau hyn:

list.append(4)
list.append(5)
list.display

list.delete(3)
list.display

found_node = list.find(2)
puts found_node ? "Found: #{found_node.value}" : "Not found"

Pan fyddwn yn rhedeg y cod hwn, byddwn yn gweld:

1 -> 2 -> 3 -> 4 -> 5 -> nil
1 -> 2 -> 4 -> 5 -> nil
Found: 2

Casgliad

Mae rhestrau cysylltiedig yn strwythurau data pwerus sy'n cynnig hyblygrwydd a chynhyrchedd. Mae Ruby yn cynnig dulliau syml a chynhwysfawr i greu a rheoli rhestrau cysylltiedig. Trwy ddeall y strwythur a'r gweithrediadau sylfaenol, gallwch ddechrau defnyddio rhestrau cysylltiedig yn eich prosiectau Ruby.

Gobeithio bod yr erthygl hon wedi bod yn ddefnyddiol i chi wrth ddysgu am rhestrau cysylltiedig yn Ruby. Peidiwch ag oedi i archwilio mwy a chreu eich fersiwn eich hun o'r strwythur hwn!