So sánh hai LinkedList <String> với ListIterator so với vòng lặp và nhận (int index)

Question

Tôi có hai đối tượng LinkedList luôn có cùng kích thước. Tôi muốn so sánh chúng để xem chúng có giống nhau về nội dung hay không. Hiệu suất chung và ý nghĩa phong cách của việc tạo ListIterator cho mỗi danh sách và sử dụng vòng lặp while hasNext so với sử dụng bộ đếm (int i) và lặp từ 0 đến linkedlist.size() bằng cách sử dụng linkedlist.get (i) để so sánh và so sánh giá trị? Có cách nào tốt hơn mà tôi nhìn không?

Điều duy nhất tôi có thể nghĩ là phương pháp ListIterator có thể tốt hơn ở chỗ tôi có thể dễ dàng trao đổi trong danh sách có thể so sánh sau (không phải là tôi dự định). Tôi không biết hai người trông như thế nào dưới mui xe, vì vậy tôi không chắc chắn làm thế nào tôi sẽ so sánh chúng hiệu quả.

Answer 1

Khi hóa ra AbstractList.equals() (sử dụng số LinkedList) sẽ tự động thực hiện việc này để sử dụng. Mã này là:

public boolean equals(Object o) { 
    if (o == this) 
    return true; 
    if (!(o instanceof List)) 
    return false; 

    ListIterator<E> e1 = listIterator(); 
    ListIterator e2 = ((List) o).listIterator(); 
    while (e1.hasNext() && e2.hasNext()) { 
    E o1 = e1.next(); 
    Object o2 = e2.next(); 
    if (!(o1 == null ? o2 == null : o1.equals(o2))) 
     return false; 
    } 
    return !(e1.hasNext() || e2.hasNext()); 
} 

Vì vậy, đừng sáng tạo lại bánh xe.

Lưu ý cuối cùng: không sử dụng get(index) để lặp qua một số LinkedList. Đó là truy cập O (n) (O (1) cho số ArrayList) do đó, việc di chuyển LinkedList bằng cách sử dụng get(index) sẽ là O (n).

Answer 2

Truy cập ngẫu nhiên vào LinkedList có hiệu suất kinh khủng (cần phải bắt đầu ở một đầu và gọi next hoặc nhiều lần liên tục), vì vậy ListIterator sẽ nhanh hơn.

Answer 3

get(n) cho danh sách được liên kết không phải là hoạt động liên tục cho các lớp mở rộng AbstractSequentialList; nó là O(n). Từ AbstractSequentialList#get(int index):

Lần thực hiện này trước tiên sẽ là một trình vòng lặp danh sách trỏ đến phần tử được lập chỉ mục (với listIterator(index)). Sau đó, nó lấy phần tử bằng cách sử dụng ListIterator.next và trả về nó.

Nói chung bạn không muốn truy cập ngẫu nhiên vào các bộ sưu tập không triển khai giao diện điểm đánh dấu java.util.RandomAccess.

Như một quy tắc của ngón tay cái, một danh sách thực hiện, nếu thực hiện giao diện này nếu, ví dụ điển hình của lớp, vòng lặp này:

for (int i=0, n=list.size(); i < n; i++) 
    list.get(i); 

chạy nhanh hơn vòng lặp này:

for (Iterator i=list.iterator(); i.hasNext();) 
    i.next(); 

Kể từ Java SE 6, các lớp triển khai thực hiện là ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector.