Đâ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):
| Cấu trúc dữ liệu | Truy cập | Tìm kiếm | Chèn | Xóa |
|---|---|---|---|---|
| Mảng | O (1) | O (n) | O (n) | O (n) |
| Danh sách được Liên kết | O (n) | O (n) | O (1) | O (1) |
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 🙂