Confirm Java LinkedList "foreach" lặp

Question

Good Day,

Ai đó có thể xác nhận những gì đã nói ở dưới cùng của bài viết này java - iterating a linked list Các bài đề cập rằng bạn có thể sử dụng cho (char c: linkedlistofchars) cú pháp và nó vẫn sẽ là O (n). Tôi nghĩ rằng truy cập vào một danh sách giống như thế này ...

a b c d e f 

thực sự sẽ chạy bắt đầu tại beggining của danh sách liên kết đến trong mỗi lần lặp của vòng lặp for, như thế này ...

a ab abc abcde abcdef 

khiến thời gian truy cập không phải là O (n).

Chính xác hoạt động như thế nào? Nó có ý nghĩa với một mảng và các toán tử mảng, nhưng cú pháp java biết cách lặp qua danh sách liên kết bằng cách sử dụng vòng lặp foreach trong java?

Tôi nghĩ cấu trúc dữ liệu LinkedList chỉ là một thư viện bổ sung chứ không phải là một phần của cú pháp ngôn ngữ chính. (Tôi nhận ra rằng lớp LinkedList là tiêu chuẩn trong java)

Tôi hy vọng tôi đã giải thích mối quan tâm của tôi rõ ràng đủ .... Cảm ơn

Answer 1

Trước hết, bất kỳ thể hiện nào của lớp thực hiện Iterable đều có thể được sử dụng trong vòng lặp foreach. Lý do là sau khi biên dịch, for (Suit suit : suits) thực sự trở thành for (Iterator i = suits.iterator(); i.hasNext();). Xem this explanation để biết thêm chi tiết.

Và bộ sưu tập triển khai trình vòng lặp được tối ưu hóa, cụ thể cho cấu trúc dữ liệu. Cụ thể là LinkedList, trình lặp sẽ giữ con trỏ đến đối tượng được trả về cuối cùng để cho phép thời gian cố định next() và hoạt động previous(). Do đó, việc lặp qua một danh sách liên kết bằng cách sử dụng vòng lặp foreach sẽ làm phức tạp thời gian O (n). Bạn có thể xem mã nguồn để biết thêm chi tiết.

Answer 2

Đoạn mã ví dụ tại liên kết này demonstrates the difference. OP tại liên kết đó sai: gọi số list.get(i) sẽ bắt đầu ở đầu danh sách mỗi lần và sau đó đếm đến khi đạt được số i, trong khi iterator.next() sẽ lưu địa điểm của bạn vào danh sách, vì vậy mỗi lần gọi nó chỉ cần đọc giá trị tiếp theo, không phải tất cả các giá trị trong khoảng từ 0 đến n.