Danh sách liên kết Java hỗ trợ loại bỏ nhanh bất kỳ nút nào?

Question

java.util.LinkedList không cho phép bạn nhanh chóng xóa một đối tượng đã cho trong danh sách. Phương thức remove (object) thực hiện tìm kiếm tuyến tính để tìm đối tượng trong danh sách để nó có thể loại bỏ nó. Vì đây là một danh sách liên kết kép, nên xóa bỏ bằng cách chỉ cập nhật các con trỏ (node.prev và node.next).

Giải pháp chuẩn Java cho vấn đề này là gì?

NOTE1: Tôi không muốn xóa trong khi lặp lại. Tôi biết đó là nhanh, nhưng tôi không lặp lại thông qua các yếu tố của tôi ở nơi đầu tiên.

CHÚ Ý2: Để làm cho nó đơn giản: Cho một đối tượng O mà tôi biết nó nằm trong danh sách liên kết kép, tôi muốn xóa O nhanh khỏi danh sách đó (bằng cách cập nhật con trỏ) mà không phải tìm kiếm tuyến tính danh sách, như java.util.LinkedList.

Answer 1

Bạn nên xem qua lớp LinkedHashSet. Về cơ bản nó là một HashSet duy trì một danh sách liên kết gấp đôi giữa các mục của nó. Nó hỗ trợ truy xuất (và do đó cũng xóa) của một phần tử trong O (1) (hy vọng). Kiểm tra liên kết cho đặc điểm kỹ thuật về cách nó xử lý thứ tự các phần tử trong trường hợp chèn lại một mục nhập và các chi tiết khác.

EDIT:

Nếu bạn cần lưu trữ các bản sao bạn có thể có một cái nhìn tại GuavaLinkedHashMultiset (không bao giờ sử dụng cho đến nay). Hướng dẫn sử dụng ổi trên Multiset là here.

Answer 2

Nói chung, bạn muốn làm việc bằng cách sử dụng ListIterator nếu có thể. Đó là remove sẽ là thời gian không đổi.

Thư viện chuẩn Java không có cấu trúc nút danh sách liên kết riêng biệt, vì vậy tôi nghĩ rằng ListIterator là tùy chọn tốt nhất.

Answer 3

Có vẻ như bạn cần một đối tượng tổng hợp. Tạo một lớp có chứa danh sách của bạn, trong khi vẫn duy trì một chỉ mục trong danh sách đó. Vì vậy, khi muốn xóa nhanh, bạn thực hiện tra cứu chỉ mục thời gian không đổi, để tham chiếu đến phần tử danh sách mà bạn muốn xóa, tiếp theo là xóa thời gian liên tục.

Answer 4

Tôi đặt cược bạn rằng việc thực hiện LinkedList#remove() sẽ loại bỏ nó bằng cách cập nhật các con trỏ tới các mục trước và tiếp theo - vấn đề là, nó phải lặp lại tất cả các đối tượng cho đến khi tìm thấy đối tượng thích hợp để loại bỏ.

Nếu bạn muốn một bộ sưu tập loại bỏ nhanh hơn, mà không cần lặp qua tất cả các đối tượng, hãy sử dụng Set hoặc Map.

Answer 5

Có lẽ bản đồ sẽ phù hợp. Nó cung cấp cho dự kiến ​​ O (1) thời gian xóa. Nhưng sau đó một lần nữa bạn đã không xác định những gì nhanh chóng có nghĩa là.

Danh sách được BST hỗ trợ cũng có thể hoạt động. Nó sẽ cung cấp cho log (n) loại bỏ thời gian.

Đối với các giải pháp được liệt kê ở đây, tôi giả định điều gì đó nhanh hơn lặp qua danh sách, vì vậy mọi thứ nhanh hơn O (n);

Answer 6

Tôi chủ yếu là một lập trình viên C học Java.Tôi tìm thấy thread này bởi vì tôi cũng tự hỏi tại sao không có danh sách liên kết thực hiện mà bạn chỉ có thể loại bỏ các đối tượng trực tiếp mà không cần tìm kiếm nó. Tìm kiếm tuyến tính là vô cùng hiệu quả. Một danh sách được hỗ trợ với một bảng băm là tốt hơn, nhưng bạn không thực sự biết làm thế nào bảng băm sẽ thực hiện. Lý do bạn có thể làm điều này dễ dàng trong C là bởi vì thông thường đối tượng phần tử danh sách chứa các con trỏ tiếp theo và trước đó, do đó, cho đối tượng, đó là một thao tác đơn giản để xóa phần tử khỏi danh sách , vì vậy nó là một hoạt động O (1). Trong Java, bạn có đối tượng, nhưng bạn không có quyền truy cập trực tiếp vào các con trỏ vì chúng được duy trì riêng trong danh sách. Vì vậy, bạn phải tìm kiếm đối tượng theo đường thẳng hoặc với bảng băm. Có vẻ như người ta có thể giải quyết vấn đề này bằng cách tạo ra một danh sách liên kết, nơi mọi kiểu đối tượng được thêm vào danh sách sẽ phải triển khai một giao diện LinkedListElement để hỗ trợ việc thiết lập các con trỏ tiếp theo và trước đó. Bạn sẽ phải thêm các con trỏ tiếp theo và trước đó vào lớp của bạn và thực hiện các hàm để nhận và thiết lập chúng. Lớp danh sách liên kết sau đó sẽ có thể dễ dàng loại bỏ một đối tượng vì chính đối tượng đó chứa các con trỏ.