Danh sách liên kết Java Util - cách tìm kiếm tiếp theo?

Question

Khi sử dụng Java LinkedList làm thế nào để bạn tìm ra mối quan hệ tiếp theo hoặc trước đó của phần tử?

Ý tôi là, trong một danh sách liên kết thường xuyên tôi sẽ làm một cái gì đó như thế này:

Node node1 = new Node(); 
Node node2 = new Node(); 
LinkedList list = new LinkedList(); 
list.add(node1); 
list.add(node2); 

//then my node1 will know who it's next is: 
assertEquals(node2, node1.next()); 

nơi Node là thùng chứa của riêng mình cho dữ liệu/đối tượng.

Nhưng trong Danh sách liên kết của Java, dữ liệu dường như không bị sửa đổi. Vì vậy, làm thế nào để tôi thực sự tìm ra những người "tiếp theo" (hoặc "trước đó" trong trường hợp của các danh sách liên kết gấp đôi) là?

Answer 1

Bạn không thể. LinkedList chỉ là một thực hiện của Danh sách và cung cấp về không có gì nhiều hơn nữa. Bạn sẽ cần phải làm của riêng bạn.

Đối với node1.next(), bạn cần tham chiếu từ node1 vào Danh sách. Trên thực tế, bạn cần nhiều tham chiếu, vì node1 có thể có nhiều lần. Hơn nữa, nó có thể được chứa trong nhiều Danh sách.

Có thể bạn có thể sử dụng ListIterator cho việc này.

Answer 2

Tôi không biết bạn đang sử dụng lớp học nào Node, nhưng LinkedList<T> có lớp nút nội bộ riêng mà bạn không có quyền truy cập. Gọi add sẽ thêm một giá trị vào danh sách - bạn không thể chèn một nút rõ ràng giữ một giá trị hoặc tự truy cập các nút theo bất kỳ cách nào khác. Vâng, đôi khi có thể là một cơn đau.

Nếu bạn cần danh sách được liên kết với đóng gói công khai của nút, bạn sẽ cần phải tìm một triển khai khác hoặc cuộn của riêng bạn.

Answer 3

Phần "được liên kết" của tên lớp LinkedList chỉ đề cập đến việc triển khai. Giao diện không hiển thị các phương thức rõ ràng để thực hiện những gì bạn muốn.

LinkedList thực hiện các giao diện Collection (và trong danh sách), vì vậy đưa ra một chỉ số i của một phần tử trong danh sách list, bạn có thể nhận được các yếu tố trước và sau với list.get(i-1) và list.get(i+1), tương ứng. Đối với một LinkedList, việc thực hiện các phương thức này khá chậm. Nếu bạn thực hiện nhiều thao tác prev/next, hãy xem xét để thực hiện danh sách của bạn hoặc sử dụng một ArrayList thay thế.

Answer 4

Tôi phải không đồng ý với câu trả lời được chấp nhận. Bạn có thể miễn là bạn có phần tử đầu. Khi bạn mất tham chiếu đến phần tử đầu tiên bằng cách xóa và không trả về phần tử tiếp theo hoặc chèn phần tử trước phần tử đầu tiên và không trả về phần tử đó, bạn sẽ không thể thực hiện tìm kiếm của mình.

Answer 5

Giải pháp tốt nhất: Hãy Liên kết tiếp theo và cuối cùng của riêng bạn khi xây dựng một new List mục Object:

Chỉ cần có một Object lastInserted ở đâu đó trên toàn cầu hơn

public MyLinkedListItem(){ 
    if(lastInserted != null){ 
     lastInserted.next = this; 
     this.last = lastInserted; 
    } 
    lastInserted = this; 
} 

Answer 6

Bạn có thể sử dụng một iterator để di chuyển qua các nút như:

Node node1 = new Node(); 
    Node node2 = new Node(); 
    LinkedList list = new LinkedList(); 
    list.add(node1); 
    list.add(node2); 

    Iterator <Node> m_iterator=list.iterator(); 

    //set iterator to first node 
    m_iterator.next(); 

    //then my node1 will know who it's next is: 
    assertEquals(node2, m_iterator.next());