Danh sách được liên kết thực tế trong Ruby

Đây là mục thứ 3 trong loạt bài “Khoa học máy tính thực tế trong Ruby”! Hôm nay chúng ta sẽ nói về danh sách liên kết.

Vậy danh sách liên kết là gì?

Giống như tên gọi, danh sách được liên kết là một cách để lưu trữ dữ liệu ở định dạng danh sách (cảm ơn, Thuyền trưởng Rõ ràng!).

Phần "được liên kết" xuất phát từ thực tế là dữ liệu được lưu trữ trong một nút và các nút này được liên kết với nhau theo cách tuần tự.

Điều này khác với mảng như thế nào?

Danh sách được liên kết so với Mảng

Một danh sách được liên kết có các đặc điểm hiệu suất khác với một mảng. Đó là một lý do tại sao bạn có thể muốn chọn cái này hơn cái kia.

Điều này có nghĩa là danh sách được liên kết có thể hiệu quả hơn cho các tác vụ nhất định so với một mảng.

Trong danh sách được liên kết không có lập chỉ mục, không có quyền truy cập ngẫu nhiên, có nghĩa là bạn không thể tiếp cận với một mục ở giữa danh sách .

Bạn phải bắt đầu ở “đầu” của danh sách và theo các liên kết cho đến khi bạn tìm thấy nút mình muốn hoặc cho đến cuối danh sách.

Xóa (hoặc thêm) một mục khỏi giữa danh sách được liên kết nhanh hơn rất nhiều .

Tất cả những gì bạn phải làm là thay đổi con trỏ "tiếp theo" cho một nút.

Nhưng nếu bạn muốn xóa một phần tử ở giữa mảng, bạn sẽ để lại một khoảng trống và để thu hẹp khoảng cách đó, bạn phải di chuyển tất cả các phần tử ở bên phải của phần tử đã xóa.

Không hiệu quả lắm nếu bạn phải làm việc này thường xuyên!

Nếu chúng ta muốn chèn vào giữa một mảng, chúng ta phải di chuyển tất cả các phần tử của mảng để tạo ra một không gian trống.

Hãy xem ví dụ về mã :

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

Lưu ý :Cũng có một phương thức chèn Array # tích hợp sẵn, nhưng tôi muốn chỉ cho bạn cách hoạt động của phương pháp này.

Tác động hiệu suất của việc chèn một mục vào giữa danh sách là gì?

Đây là điểm chuẩn:

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

Sự khác biệt lớn ở đây, nhưng nó cũng phụ thuộc rất nhiều vào kích thước của LinkedList vì chúng tôi phải tìm kiếm nút.

Một cách khác để so sánh hai cấu trúc dữ liệu là xem bảng độ phức tạp thời gian (điều này giả sử bạn không phải tìm kiếm một nút để chèn và xóa):

Tìm kiếm các ứng dụng trong thế giới thực?

Đây là một yêu cầu kéo của Aaron Patterson khi anh ấy tăng tốc Ruby Gems bằng cách sử dụng một danh sách được liên kết:

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

Triển khai danh sách được liên kết

Ruby không bao gồm LinkedList vì vậy chúng ta cần tạo lớp của riêng mình.

Chúng tôi muốn có các thao tác sau:

• nối (vào cuối danh sách)
• append_ after
• xóa
• tìm

Dưới đây là một trong những cách triển khai có thể thực hiện:

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

Cách triển khai cụ thể này không theo dõi phần đuôi, nó sẽ tìm phần đuôi khi thêm một mặt hàng mới. Điều này làm cho hoạt động nối thêm thời gian tuyến tính (O(n) ). Trong video bên dưới, tôi chỉ cho bạn một cách triển khai khác mà tôi nối các phần tử ở phía trước.

Và đây là lớp nút của chúng tôi:

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

Chúng ta có thể sử dụng nó như thế này:

list = LinkedList.new

list.append(10)
list.append(20)
list.append(30)

list.append_after(10, 15)
list.append_after(20, 25)

list.print

Đây là cách triển khai "Danh sách liên kết đơn".

Bạn cũng có các loại danh sách được liên kết khác :

• Danh sách được liên kết kép
• Danh sách được Liên kết theo Hình tròn

Trong danh sách được liên kết kép, mỗi nút có hai con trỏ:một con trỏ tới nút tiếp theo &một nút khác đến nút trước đó .

Điều này cho phép bạn linh hoạt hơn khi tìm kiếm danh sách, nhưng cũng yêu cầu thêm công việc khi thực hiện các thay đổi đối với danh sách.

Danh sách liên kết vòng giống với danh sách được liên kết kép, nhưng nút cuối cùng được kết nối với nút đầu.

Video

Tóm tắt

Bạn đã học về danh sách được liên kết, một cấu trúc dữ liệu mà bạn có thể xem xét nếu bạn đang thực hiện nhiều việc thêm và xóa các phần tử ở giữa một mảng.

Nó cũng có thể xuất hiện trong một cuộc phỏng vấn viết mã, vì vậy, điều đáng học hỏi ngay cả khi nó chỉ dành cho điều đó.

Đừng quên chia sẻ bài đăng này bằng cách sử dụng các nút bên dưới để nhiều người hơn có thể hưởng lợi từ kiến ​​thức này 🙂