Mảng và danh sách liên kết khi chỉnh sửa dữ liệu

Chèn cạnh một nút đã biết trong danh sách liên kết cần lượng công việc cập nhật liên kết không đổi. Nhưng chèn tại vị trí 50.000 có thể đòi hỏi đi qua 50.000 nút trước khi chèn. Nếu bạn đang chọn cấu trúc cho trình soạn thảo hoặc tập hợp có thứ tự, đây là điều kiện quan trọng phía sau nhận xét quen thuộc rằng danh sách liên kết chèn nhanh.

Hãy tách hai thao tác. Thao tác thứ nhất nhận một chỉ số và chèn phần tử mới trước vị trí đó. Thao tác thứ hai đã giữ tham chiếu đến một nút và chèn ngay sau nút ấy. Hai giao diện cung cấp thông tin khác nhau. So sánh công bằng phải tính cả chi phí lấy được vị trí mà mỗi thao tác cần.

Theo dõi một lần chèn vào mảng

Bắt đầu với [A, B, C, D, E] và chèn X vào chỉ số hai. Cách biểu diễn bằng mảng dịch E sang phải một vị trí, rồi đến D, rồi C, trước khi ghi X. Dịch từ bên phải tránh ghi đè giá trị còn cần chuyển ở bước sau.

def insert_with_shift_count(values, index, item):
    if not 0 <= index <= len(values):
        raise IndexError(index)
    values.append(None)
    shifts = 0
    for position in range(len(values) - 1, index, -1):
        values[position] = values[position - 1]
        shifts += 1
    values[index] = item
    return shifts

values = ["A", "B", "C", "D", "E"]
assert insert_with_shift_count(values, 2, "X") == 3
assert values == ["A", "B", "X", "C", "D", "E"]

Mã học tập này đếm việc di chuyển các phần tử đang có. Nó không đếm chi phí cấp phát có thể xảy ra trong append của Python, và không nhằm thay thế phương thức insert có sẵn. Với danh sách dài n, chèn tại chỉ số i dịch n - i tham chiếu. Chèn cuối không dịch phần tử cũ nào; chèn đầu dịch tất cả.

Mảng nền còn có thể hết chỗ. Mảng động khi đó cấp vùng lớn hơn rồi sao chép các tham chiếu. Tăng dung lượng theo cấp số nhân làm chi phí bổ sung trung bình phân bổ của nhiều lần thêm cuối là O(1), dù một lần đổi kích thước riêng lẻ vẫn tốn O(n). Phần ArrayStack của Open Data Structures tách chi phí đổi kích thước này khỏi việc dịch phần tử bên trong mảng.

Thực hiện cùng thay đổi trên danh sách liên kết

Với danh sách liên kết đơn, giả sử cursor đã trỏ đến nút chứa B. Tạo nút chứa X, cho nó trỏ đến nút kế tiếp hiện tại của B, rồi cho B trỏ đến X. Các nút chứa C, D, E không phải đổi vị trí.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def insert_after(cursor, value):
    node = Node(value, cursor.next)
    cursor.next = node
    return node

Thứ tự gán giữ lại đường dẫn đến phần còn lại của danh sách. Nếu thay cursor.next trước khi lưu đích cũ, phần đuôi có thể không còn truy cập được từ đầu danh sách. Nút trả về có thể trở thành con trỏ cho lần chèn kế tiếp. Nhờ giữ tham chiếu này, một loạt thay đổi gần nhau không phải tìm lại từ đầu.

Mở ảnh kích thước đầy đủ ↗

Hình biểu diễn liên kết logic, không biểu diễn vị trí vật lý trong bộ nhớ. Các nút có thể nằm rải rác. Những hộp vẽ cách đều không bảo đảm giá trị của chúng nằm liền nhau trong RAM.

Tính theo chuỗi thao tác thực sự cần dùng

Giả sử một trình soạn thảo minh họa có 100.000 token, nhảy đến chỉ số ngẫu nhiên 1.000 lần và chèn một token sau mỗi lần nhảy. Mảng truy cập theo chỉ số trong O(1), nhưng mỗi lần chèn có thể phải dịch một phần đuôi dài. Danh sách liên kết tránh việc dịch sau khi đến đúng chỗ, nhưng mỗi lần nhảy lại có thể phải đi qua nhiều nút. Cả hai đều có thể tốn Θ(n) cho một lần tìm vị trí rồi chèn trong kiểu sử dụng này.

Bây giờ đổi cách sử dụng: tìm một vị trí một lần, giữ con trỏ rồi gõ 1.000 token liền nhau. Danh sách liên kết chỉ cần tìm ban đầu và làm lượng công việc liên kết không đổi cho mỗi lần chèn sau đó. Mảng có thể phải chuyển cùng một phần đuôi nhiều lần. Đây là lý do cụ thể để xem xét cấu trúc hỗ trợ sửa quanh con trỏ.

Cách đọc dữ liệu cũng ảnh hưởng lựa chọn. Duyệt mảng thường có lợi từ việc các phần tử hoặc tham chiếu nằm liền nhau. Khi duyệt danh sách liên kết, phải đọc con trỏ kế tiếp mới biết nút tiếp theo ở đâu; mỗi nút còn cần bộ nhớ cho liên kết và quản lý cấp phát. Đây là yếu tố triển khai và phần cứng, không làm đổi cận tiệm cận. Danh sách Python chứa tham chiếu đến đối tượng; tham chiếu liền nhau không có nghĩa các đối tượng cũng liền nhau.

Giữ vị trí khi chèn cả một nhóm

Một ví dụ nhỏ giúp đếm được chi phí dịch lặp. Bắt đầu với ABCDE, đặt con trỏ sau B và chèn XYZ theo thứ tự đó. Với mảng, tăng chỉ số chèn sau mỗi lần. Phần đuôi CDE ban đầu vẫn nằm bên phải, nên mỗi lần trong ba lần chèn đều dịch ba tham chiếu. Tổng là chín lần dịch, chưa tính cấp phát và ghi các giá trị mới.

Với danh sách liên kết, tìm B một lần rồi chuyển con trỏ sang từng nút vừa chèn. Dữ liệu mẫu dưới đây dùng một nút lính canh trước A để cách dựng danh sách cũng dùng được khi dãy ban đầu rỗng. Nút này giúp quản lý cấu trúc, không phải token của trình soạn thảo.

def make_chain(values):
    sentinel = Node(None)
    tail = sentinel
    for value in values:
        tail = insert_after(tail, value)
    return sentinel


def chain_values(sentinel):
    result, node = [], sentinel.next
    while node is not None:
        result.append(node.value)
        node = node.next
    return result

array = list('ABCDE')
position, shifts = 2, 0
for item in 'XYZ':
    shifts += insert_with_shift_count(array, position, item)
    position += 1
assert array == list('ABXYZCDE') and shifts == 9

head = make_chain('ABCDE')
cursor, hops = head.next, 0
while cursor.value != 'B':
    cursor = cursor.next
    hops += 1
for item in 'XYZ':
    cursor = insert_after(cursor, item)
assert chain_values(head) == list('ABXYZCDE')
assert hops == 1 and cursor.value == 'Z'

Mở ảnh kích thước đầy đủ ↗

Tìm kiếm bắt đầu tại A nên đi theo liên kết kế tiếp một lần là đến B. Việc dựng dữ liệu mẫu và chuyển danh sách trở lại dạng danh sách Python nằm ngoài số đếm chỉnh sửa. Mỗi lần chèn tạo một nút và ghi hai trường liên kết: nút kế tiếp của nút mới, rồi nút kế tiếp của con trỏ cũ. Chín tham chiếu mảng bị dịch, một bước tìm kiếm, ba lần cấp phát và sáu lần ghi liên kết là các loại công việc khác nhau. Ví dụ không khẳng định tỷ lệ tốc độ đã đo giữa chúng.

Không đưa con trỏ đến nút mới sẽ đổi kết quả. Nếu cả ba lần đều chèn sau B, thứ tự chèn X, Y, Z tạo ra ABZYXCDE. Thao tác chèn vẫn đúng theo giao diện; bên gọi đã giữ con trỏ không phù hợp với việc gõ một dãy xuôi. Giữ nguyên chỉ số chèn của mảng cũng đảo thứ tự nhóm mới theo cùng cách.

Với k lần chèn cạnh nhau trước phần đuôi không đổi dài s, hàm mảng đơn giản này thực hiện k * s lần dịch. Một thao tác chèn cả nhóm có thể mở khoảng trống một lần và chỉ dịch phần đuôi một lần. Đó là giao diện và cách cài đặt khác; không phải mọi cách chỉnh sửa mảng đều buộc lặp lại công việc. Chèn liên kết cục bộ làm lượng công việc liên kết không đổi mỗi lần sau khi định vị, nhưng vẫn cần tính cấp phát và những lượt đọc về sau.

Hãy thử chèn đầu, chèn cuối và chèn vào dãy rỗng. Dùng nút lính canh làm nút đứng trước khi chèn đầu. Dự đoán cả thứ tự kết quả lẫn số tham chiếu cũ phải dịch. Sau đó cố tình giữ nguyên con trỏ để xác định chính xác giao diện mà trình soạn thảo cần.

Quy định cả việc xóa và tính hợp lệ của con trỏ

Danh sách liên kết đơn thường không thể xóa một nút đã biết trong thời gian hằng số nếu không có tham chiếu đến nút trước nó. Xóa nút ngay sau một nút đã biết thì dễ. Danh sách liên kết đôi lưu thêm nút trước, cho phép tháo liên kết cục bộ nhưng dùng thêm bộ nhớ và cần nhiều lần cập nhật hơn. Phần DLList giải thích khác biệt giữa truy cập theo chỉ số và chỉnh sửa cạnh vị trí đã biết.

Trình soạn thảo cũng cần quy tắc cho vị trí được giữ lại. Con trỏ xác định một token cụ thể hay khoảng trống trước token? Nếu token bị xóa thì sao? Chỉ số mảng có thể trỏ đến nội dung khác sau một lần chèn. Tham chiếu nút có thể ổn định qua các lần chèn ở nơi khác, rồi không còn hợp lệ khi chính nút đó bị xóa. Đây là hành vi của giao diện, cần được quyết định rõ.

Với trình soạn thảo văn bản thực tế, bộ đệm khoảng trống, bảng mảnh văn bản và cấu trúc dãy dựa trên cây còn tạo ra những kết hợp khác giữa đọc liên tiếp, chỉnh sửa quanh con trỏ và truy cập theo chỉ số. Bài tập mảng với danh sách liên kết hữu ích vì buộc bạn mô tả chuỗi thao tác trước. Hãy ghi tần suất nhảy vị trí, duyệt và sửa gần con trỏ, rồi so sánh cả chi phí cấp phát lẫn quy tắc giữ vị trí.