Giới thiệu bộ sưu tập LinkedList

1. Lịch sử củaLinkedList

Java có một lớp tập hợp khác Java kế thừa từ ngôn ngữ C++. Đây là LinkedListlớp thực hiện một "danh sách được liên kết".

Bề ngoài, a LinkedListcó vẻ giống như ArrayList. Lớp LinkedListcó tất cả các phương thức giống như ArrayListlớp. Về nguyên tắc, bạn luôn có thể sử dụng a LinkedListthay vì an ArrayListvà mọi thứ sẽ hoạt động.

Vậy tại sao chúng ta cần một lớp danh sách khác?

Câu trả lời có liên quan đến cấu trúc bên trong của lớp LinkedList. Thay vì một mảng, nó sử dụng một danh sách liên kết đôi . Chúng tôi sẽ giải thích đó là gì sau một chút.

Cấu LinkedListtrúc bên trong khác biệt của lớp làm cho nó nhanh nhất trong việc chèn các phần tử vào giữa danh sách.

Trên Internet, bạn thường có thể tìm thấy sự so sánh giữa các lớp ArrayListvà LinkedListlớp:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Mọi thứ dường như đủ rõ ràng: nếu bạn cần thường xuyên chèn các phần tử vào danh sách, hãy sử dụng LinkedList; nếu ít thì dùng ArrayList. Nhưng thực tế thì hơi khác một chút.

2. Không ai sử dụngLinkedList

Không ai sử dụng LinkedList.

Ngay cả tác giả của LinkedListlớp học gần đây cũng đã tweet: "Có ai thực sự sử dụng không LinkedList? Tôi đã viết nó và tôi không bao giờ sử dụng nó."

Vậy thỏa thuận là gì?

Đầu tiên, lớp ArrayListbắt đầu có thể chèn các phần tử vào giữa danh sách một cách rất nhanh chóng. Khi chèn một phần tử vào giữa danh sách, bạn phải dịch chuyển tất cả các phần tử sau dấu chèn thêm 1 về phía cuối danh sách. Điều này được sử dụng để mất thời gian.

Nhưng bây giờ mọi thứ đã thay đổi. Tất cả các phần tử của một mảng đều ở gần nhau trong cùng một khối bộ nhớ, vì vậy thao tác dịch chuyển các phần tử được thực hiện bằng một lệnh cấp thấp rất nhanh: .System.arraycopy()

Ngoài ra, các bộ xử lý ngày nay có bộ đệm lớn thường có thể chứa toàn bộ mảng, điều này cho phép các phần tử mảng được chuyển vào bên trong bộ đệm thay vì trong bộ nhớ. Một triệu yếu tố dễ dàng được thay đổi trong một phần nghìn giây.

Thứ hai, lớp LinkedListcó thể chèn các phần tử một cách nhanh chóng nếu bạn chèn chúng bằng một trình vòng lặp. Nếu bạn sử dụng một trình vòng lặp để đi qua một LinkedListvà liên tục chèn các phần tử mới (hoặc xóa các phần tử hiện có), thao tác này sẽ cực kỳ nhanh.

Nếu bạn chỉ thêm các phần tử vào một LinkedListđối tượng bên trong một vòng lặp, thì mỗi thao tác chèn nhanh sẽ đi kèm với thao tác "lấy phần tử" chậm.

Thực tế gần với điều này hơn nhiều:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Tại sao nhận được một yếu tố từ một LinkedListhoạt động chậm như vậy?

Bạn có thể trả lời câu hỏi đó sau khi làm quen một chút với cách LinkedListcấu trúc.

3. LinkedListCấu trúc như thế nào

LinkedListcó cấu trúc bên trong khác với ArrayList. Nó không có một mảng bên trong để lưu trữ các phần tử. Thay vào đó, nó sử dụng một cấu trúc dữ liệu được gọi là danh sách viết tay đôi .

Mỗi phần tử của danh sách liên kết kép lưu trữ một tham chiếu đến phần tử trước đó và phần tử tiếp theo. Điều này phần nào giống như việc xếp hàng tại một cửa hàng, nơi mỗi người nhớ người đứng trước mặt họ cũng như người đứng sau họ.

Đây là danh sách như vậy trông như thế nào trong bộ nhớ:

Đầu và đuôi (các ô có nền màu xám) là các biến firstvà lastlưu trữ các tham chiếu đến Nodecác đối tượng.

Ở giữa, bạn có một chuỗi Nodeđối tượng (đối tượng, không phải biến). Mỗi người trong số họ bao gồm ba lĩnh vực:

• prev— lưu trữ một tham chiếu (liên kết) đến Nodeđối tượng trước đó (các ô có nền màu vàng).
• value— lưu trữ giá trị của phần tử này trong danh sách (các ô có nền màu xanh lá cây).
• next— lưu trữ một tham chiếu (liên kết) đến Nodeđối tượng tiếp theo (các ô có nền màu xanh lam)

Đối tượng thứ hai (địa chỉ F24) là đối tượng tiếp theo ( next) cho đối tượng thứ nhất và trước đó ( prev) cho đối tượng thứ ba. Trường màu vàng của đối tượng thứ ba chứa địa chỉ F24 và trường màu xanh lam của đối tượng đầu tiên chứa địa chỉ F24.

Các mũi tên từ đối tượng thứ nhất và thứ ba trỏ đến cùng một đối tượng thứ hai. Vì vậy, sẽ đúng hơn nếu vẽ các mũi tên như thế này.

4. Chèn phần tử vào danh sách liên kết

Để thêm người vào hàng như thế này, bạn chỉ cần được sự cho phép của hai người đứng cạnh nhau. Người đầu tiên nhớ đến người mới là "người phía sau tôi", và người thứ hai nhớ họ là "người trước mặt tôi".

Tất cả những gì bạn cần làm là thay đổi tham chiếu của hai đối tượng lân cận:

Chúng tôi đã thêm một mục mới vào danh sách của mình bằng cách thay đổi tham chiếu của đối tượng thứ hai và thứ ba. Đối tượng mới là đối tượng tiếp theo cho đối tượng thứ hai cũ và đối tượng trước đó cho đối tượng thứ ba cũ. Và, tất nhiên, bản thân đối tượng mới cần lưu trữ các tham chiếu chính xác: đối tượng trước của nó là đối tượng thứ hai cũ và đối tượng tiếp theo của nó là đối tượng thứ ba cũ.

Việc xóa một phần tử thậm chí còn dễ dàng hơn: Giả sử nếu chúng ta muốn xóa đối tượng thứ 100 khỏi danh sách, chúng ta chỉ cần thay đổi trường nextcho đối tượng thứ 99 để nó trỏ đến đối tượng thứ 101 và thay đổi prevtrường cho đối tượng thứ 101 đối tượng để nó trỏ đến thứ 99. Đó là nó.

Nhưng để có được đối tượng thứ 100 không dễ dàng như vậy.

5. Xóa phần tử khỏi danh sách

Để lấy phần tử thứ 100 của danh sách liên kết, bạn cần:

Lấy đối tượng thứ nhất: Bạn thực hiện việc này bằng cách sử dụng firstbiến trong LinkedListđối tượng. Trường nextcủa đối tượng thứ nhất lưu trữ tham chiếu đến đối tượng thứ 2. Đó là cách chúng ta có được đối tượng thứ hai. Đối tượng thứ 2 có tham chiếu đến đối tượng thứ ba, v.v.

Nếu chúng ta cần tham chiếu đến đối tượng thứ 100, chúng ta cần di chuyển tuần tự qua tất cả các đối tượng từ thứ 1 đến thứ 100. Và nếu chúng ta cần phần tử thứ một triệu trong danh sách, chúng ta cần lặp lại hơn một triệu đối tượng lần lượt!

Và nếu các đối tượng này được thêm vào danh sách vào các thời điểm khác nhau, thì chúng sẽ nằm ở các phần khác nhau của bộ nhớ và không có khả năng xuất hiện cùng lúc trong bộ đệm của bộ xử lý. Điều này có nghĩa là việc lặp lại các phần tử của danh sách được liên kết không chỉ chậm mà còn rất chậm.

Đó là những gì chúng tôi đang giải quyết.

Vậy tại sao chúng tôi dạy bạn cách LinkedListhoạt động chậm chạp này?

Chà, trong các cuộc phỏng vấn xin việc, bạn sẽ được hỏi nó LinkedListkhác vớiArrayList . Chắc chắn.