Thuật toán để xóa một phần tử trong một danh sách liên kết đơn với O (1) phức tạp

Tôi là sinh viên ngành khoa học máy tính ở Đức. Giáo sư của tôi đã sử dụng câu hỏi sau đây để suy nghĩ về:Thuật toán để xóa một phần tử trong một danh sách liên kết đơn với O (1) phức tạp

'Cho một tham chiếu đến một nút trong một danh sách liên kết duy nhất (không phải là nút cuối cùng). Đưa ra một thuật toán để xóa phần tử này khỏi danh sách có độ phức tạp O (1) trong khi duy trì tính toàn vẹn '.

Tôi đã nghĩ về điều này, nhưng tôi khá chắc chắn rằng không có thuật toán như vậy. vì nó là một danh sách liên kết duy nhất, bạn phải lặp qua tất cả các nút trong danh sách cho đến khi bạn đạt đến nút cần xóa, bởi vì bạn phải sửa đổi con trỏ tiếp theo trong nút trước khi xóa. Mà sẽ dẫn đến O (n) phức tạp.

Tôi có thiếu gì không?

Nguồn

2009-04-27 Martin Thurau

Tùy thuộc vào việc các nút có thể thay đổi được hay không (về giá trị).

Có là một cách để làm việc đó, nếu bạn có thể làm những gì bạn thích với các nút:

toDelete.value = toDelete.next.value 
toDelete.next = toDelete.next.next

Tất cả các thông tin từ toDelete hiện đã được ghi đè, bởi thông tin trong cái cũ toDelete.next. (Tùy thuộc vào nền tảng, sau đó bạn có thể cần phải giải phóng cũ toDelete.next - có nghĩa là giữ một tham chiếu tạm thời với nó. Không tốt nếu bất cứ ai khác vẫn còn có một tham chiếu đến nó, tất nhiên.Trong Java/C# bạn chỉ cần bỏ qua nó .)

tôi đã cố gắng để tìm ra một cách để gợi ý vào nó mà không đưa nó đi, nhưng nó kinda khó khăn ...

nó dựa vào điều này không phải là nút cuối cùng trong danh sách mặc dù.

Nguồn

2009-04-27 15:12:21

Ah, hiểu rồi. Cảm ơn :) –

hãy cẩn thận, như Jon đã giải thích, rằng để làm việc này, cấu trúc nút cần phải riêng tư. Không nên giữ tham chiếu đến các nút, chỉ với dữ liệu. Nếu không, người tiêu dùng sẽ bị bỏ sót với tham chiếu không hợp lệ đối với đối tượng toDelete.next cũ (nếu bạn đang ở trong C++ chẳng hạn và bạn đã xóa cấu trúc nút), hoặc tốt nhất là một đối tượng nút không hợp lệ. –

Điều này không thực sự là một thuật toán '' để loại bỏ một phần tử từ một danh sách liên kết đơn là nó? Đây là phương pháp tiêu chuẩn để loại bỏ một phần tử khỏi danh sách. – Dinuk

Không chính xác coi xóa một nút nhưng bạn có thể sao chép dữ liệu của nút bên cạnh hiện và xóa các nút tiếp theo:

// pseudocode: 
this.data = next.data; 
var temp = this.next; 
this.next = next.next; 
delete temp;

Nguồn

2009-04-27 15:13:08

Yes. Bạn giữ như con trỏ lặp của bạn, một con trỏ đến con trỏ kế tiếp của danh sách trước đó.

walk = &head; 
while (!match(*walk)) { 
    walk = &walk[0]->next; 
    if (!*walk) return ; 
} 
*walk = walk[0]->next;

Nguồn

2009-04-27 15:13:47 Joshua

Đó không phải là O (1). –

Phần xóa là. Trình lặp cập nhật trên danh sách được liên kết nên * luôn * sử dụng con trỏ đến con trỏ tới nút tiếp theo. – Joshua

Nếu các nút là các cấu trúc cơ bản trong bộ nhớ, bạn có thể sao chép nội dung của nút "bên cạnh" vào vị trí bộ nhớ của nút xóa, và deallocate bộ nhớ nơi mà các nút "tiếp theo" từng là.

Nguồn

2009-04-27 15:13:59