Đây là bài thứ 3 trong series "Khoa học Máy tính Thực hành 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ì?
Như tên gọi, danh sách liên kết là một cách lưu trữ dữ liệu theo định dạng danh sách (cảm ơn, Thuyết trưởng Hiển nhiên!).
Phần "liên kết" đến từ việc 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 trình tự tuần tự.
Cái này khác với mảng như thế nào?
Danh sách Liên kết vs Mảng
Danh sách liên kết có đặc điểm hiệu suất khác với 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 liên kết có thể hiệu quả hơn cho một số tác vụ nhất định so với mảng.
Trong danh sách liên kết không có chỉ mục, không có truy cập ngẫu nhiên, nghĩa là bạn không thể truy xuất một mục ở giữa danh sách.
Bạn phải bắt đầu từ "đầu" của danh sách và theo dõi các liên kết cho đến khi tìm thấy nút bạn muốn hoặc đến cuối danh sách.
Xóa (hoặc thêm) một mục từ giữa danh sách liên kết nhanh hơn nhiều.
Tất cả những gì bạn phải làm là thay đổi con trỏ "next" cho một nút.
Nhưng nếu bạn muốn xóa một phần tử từ giữa mảng, bạn sẽ để lại một khoảng trống và để đóng khoảng trống đó, bạn phải di chuyển tất cả các phần tử bên phải của phần tử bị xóa.
Không hiệu quả chút nào nếu bạn phải làm điều này thường xuyên!
Nếu chúng ta muốn chèn vào giữa mảng, chúng ta phải di chuyển tất cả các phần tử mảng để tạo khoảng trống.
Hãy xem ví dụ 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ó phương thức Array#insert tích hợp sẵn, nhưng tôi muốn cho bạn thấy phương thức này hoạt động như thế nào.
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à benchmark:
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 ta phải tìm kiếm nú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 (giả sử bạn không phải tìm 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 Liên kết | O(n) | O(n) | O(1) | O(1) |
Tìm ứng dụng thực tế?
Đây là một pull request của Aaron Patterson, nơi anh ấy tăng tốc Ruby Gems bằng cách sử dụng danh sách liên kết:
https://github.com/rubygems/rubygems/pull/1188
Triển khai Danh sách Liên kết
Ruby không bao gồm lớp LinkedList nên chúng ta cần tự tạo.
Chúng ta muốn các hoạt động sau có sẵn:
- append (đến cuối danh sách)
- append_after
- delete
- find
Đây là một triển khai có thể:
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
Triển khai cụ thể này không theo dõi đuôi, nó tìm đuôi khi thêm mục mới. Điều này làm cho phép append trở thành thời gian tuyến tính (O(n)). Trong video bên dưới, tôi cho bạn thấy triển khai khác nơi tôi thêm các phần tử ở đầu.
Và đây là lớp nút của chúng ta:
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ư sau:
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à triển khai cơ bản "Danh sách Liên kết Đơn".
Bạn cũng có các loại danh sách liên kết khác:
- Danh sách Liên kết Kép
- Danh sách Liên kết Vòng
Trong danh sách liên kết kép, mỗi nút có hai con trỏ: một đến nút tiếp theo và một đến nút trước đó.
Điều này cho phép linh hoạt hơn khi tìm kiếm danh sách, nhưng cũng yêu cầu công việc thêm khi thay đổi danh sách.
Danh sách liên kết vòng giống với danh sách 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 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 làm nhiều việc thêm và xóa phần tử ở giữa mảng.
Nó cũng có thể xuất hiện trong phỏng vấn viết mã, vì vậy nó đáng để học ngay cả chỉ cho mục đích đó.
Đừng quên chia sẻ bài viết này bằ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 🙂