DEV Community

Cover image for ArrayList và LinkedList trong Java
luan vu
luan vu

Posted on

ArrayList và LinkedList trong Java

List là một collection được sử dụng rất phổ biến trong Java, đặc biệt là ArrayList và LinkedList. Đã bao giờ bạn tự hỏi sự khác nhau giữa hai list này và các tình huống sử dụng của chúng. Cùng tìm hiểu dưới đây.

List trong Java

List trong Java, hay interface java.util.List được mô tả như là một

  • Danh sách có thứ tự

  • Có thể truy xuất phần tử ở một vị trí bất kỳ trong list

ArrayList

Ưu điểm của array là tiết kiệm bộ nhớ và tốc độ truy xuất ngẫu nhiên (tìm một phần tử ở vị trí bất kỳ) nhanh. Tuy nhiên, đổi lại thì array phải có độ dài cố định khi bạn khởi tạo. Nếu khai báo nhiều quá sẽ tốn bộ nhớ, ít quá thì không đủ để lưu trữ.
Để thuận tiện cho cả việc sử dụng và tốc độ truy xuất, ArrayList ra đời để khắc phục các nhược điểm đó nhưng vẫn kế thừa ưu điểm trong việc truy xuất dữ liệu của array.
ArrayList làm điều đó bằng cách sử dụng một dynamic array để lưu trữ các phần tử. Khi bạn thêm hoặc xóa phần tử, ArrayList sẽ tính toán để tạo một array mới có kích thước phù hợp và copy toàn bộ phần tử từ array cũ sang array mới.
Khởi điểm array sẽ rỗng và có một biến integer cho biết kích thước thực của ArrayList, gọi là size, bằng 0.

Image description

Array này là một static array rỗng và share cho tất cả các hàm khởi tạo ArrayList để giảm thiểu bộ nhớ sử dụng nếu bạn mới chỉ khởi tạo chứ chưa dùng.
Khi bắt đầu thêm mới một phần tử, elementData sẽ được gán bằng một mảng mới có độ dài thường là bằng 10.

Image description

Khi tiếp tục thêm phần tử, elementData sẽ được lấp đầy

Image description

Giả sử elementData đã được lấp đầy (10 phần tử)

Image description

Khi ta lại thêm phần tử, elementData sẽ lại được khởi tạo bằng một array mới có size tăng thêm 50% size gốc

Image description

Cách thức tăng của elementData là newSize = oldSize * 1.5
Tương tự:
10 -> 15
15 -> 22
22 -> 33
33 -> 49
49 -> 73

Trong trường hợp delete, giả sử delete tại index 5, thực hiện:

  • Copy item từ vị trí 5 + 1 tới cuối và đè vào index 5

  • Giá trị ở vị trí cuối sẽ bị thừa ra, đặt giá trị thành null

  • Giảm size của list đi 1

Image description

Giờ ta có một list chỉ còn 10 phần tử.
Nhận xét:

  • Với cách liên tục tạo mới array và copy array, ArrayList sẽ kém trong việc thêm mới hoặc xóa phần tử, sẽ ngày một tệ hơn khi số phần tử tăng lên.

  • Truy xuất ngẫu nhiên trong ArrayList chính là truy xuất theo index trong array nên tốc độ rất nhanh.

  • Cách delete của ArrayList sẽ hoạt động kém nếu bạn delete với những index nhỏ, tệ nhất sẽ là index = 0. Giả sử list của bạn có size = 100. Nếu bạn delete phần tử đầu tiên, ArrayList sẽ phải copy 99 phần tử.

  • array trong ArrayList sẽ ngày một to ra khi bạn thêm phần tử, thêm mỗi lần 50% khi thiếu chỗ lưu và sẽ không giảm đi khi bạn delete.

LinkedList

LinkedList là một danh sách liên kết kép ( Doubly-linked list), thay vì dùng array để lưu dữ liệu như ArrayList, LinkedList lại dùng cấu trúc danh sách liên kết để lưu trữ.
Cách thức hoạt động như sau:
LinkedList bao gồm:

  • size để lưu dung lượng thực của list, giống ArrayList

  • Node first để lưu phần tử đầu tiên của list. Ban đầu chưa có sẽ là null

  • Node last để lưu phần tử cuối cùng của list. Ban đầu chưa có sẽ là null

  • Mỗi node sẽ chứa data thực của node, gọi là item, một node kế tiếp của nó, gọi là next và một node đứng ngay trước nó, gọi là prev

Khởi điểm, LinkedList sẽ bao gồm 2 node first và last đều mang giá trị null

Image description

Khi thêm phần tử đầu tiên, thay thế node first bằng phần tử đó

Image description

Khi thêm phần tử tiếp theo, thay vào node last và liên kết giữa node first và node last. Nay list đã có tối thiểu 2 node

Image description

Cứ như vậy, khi tiếp tục insert, dù là ở cuối danh sách hay đầu danh sách, LinkedList chỉ việc liên kết các node lại với nhau

Image description

Tương tự khi thêm ở giữa list thì list cũng chỉ cần đơn giản là tạo ra node mới, thay đổi liên kết 2 node bên cạnh node mới thêm vào

Image description

Khi cần delete, LinkedList cũng thay đổi liên kết 2 node bên cạnh node vừa bị xóa

Image description

Khi cần lấy ra một phần tử ở index bất kỳ, không như ArrayList, LinkedList phải đi dần dần từng node một từ first hay last phụ thuộc vào index ở gần bên nào hơn.

Image description

Giả sử bạn có một list với 1000 phần tử. Khi bạn cần lấy ra phần tử có index = 500, LinkedList sẽ phải duyệt tới toàn bộ 500 phần tử để có thể lấy ra cái bạn muốn, điều đó là rất tệ.

Nhận xét:

  • Việc tìm phần tử ở vị trí ngẫu nhiên của LinkedList kém hơn ArrayList, đặc biệt với index ở trung tâm

  • Việc thêm hoặc xóa node trong LinkedList rất dễ dàng nhưng sẽ tệ dần nếu bạn insert/delete càng về trung tâm của list.

ArrayList vs LinkedList

Từ những nhận xét ở trên, các bạn hoàn toàn có thể rút ra so sánh giữa ArrayList và LinkedList.
Cá nhân mình, chưa bao giờ dùng LinkedList, vì các lý do sau:

1. Chúng ta đều sử dụng những list có kích thước nhỏ.

Khi list có kích thước nhỏ thì tốc độ mở rộng của dynamic array không hề thua kém so với LinkedList.
Dưới đây là benchmark tốc độ insert với các kích thước khác nhau.
Image description

Không có quá nhiều khác biệt

2. Chúng ta có xu hướng sử dụng list để duyệt và tìm kiếm nhiều hơn so với insert từng phần tử một.

Việc duyệt bằng array chắc chắn là vượt trội hơn so với cách duyệt qua từng phần tử của LinkedList

3. Có nhiều cách để tạo ra 1 ArrayList chứa nhiều phần tử mà vẫn khắc phục được nhược điểm của ArrayList

  • Tạo ArrayList từ Collection khác: new ArrayList<>(Collection<> e);

  • Thêm nhiều phần tử một lúc bằng list.addAll(Collection<> e);

  • Định số phần tử trước khi insert: new ArrayList<>(int initialCapacity)

  • Dùng Stream API (Stream API sử dụng list.addAll)

4. LinkedList tốn nhiều bộ nhớ để lưu trữ

Giả sử có một list các integer, với size = 1000, và size = 1000_000, dung lượng cần để lưu trữ như sau:

Cách tính một ArrayList khi add lần lượt 1000 integer sẽ bao gồm:

  • object header = 12

  • size = 4

  • modCount = 4

  • elementData reference = 4

  • elementData header = 12

  • elementData size = 4

  • elementData item = 16 * 1234

Total 19784 byte
Với LinkedList:

  • object header = 12

  • size = 4

  • modCount = 4

  • Node first reference = 4

  • Node last reference = 4

  • Object alignment gap = 4

  • Node size = 12 (object header) + 4 (item reference) + 16 (Integer) + 4 (next reference) + 4 (prev reference) = 40

  • All node= node size * 1000 = 40000

Total 40032 byte

Bạn có thể thấy là LinkedList tốn dung lượng gấp đôi so với ArrayList. Ngoài ra array luôn thân thiện với Garbage Collection hơn so với các Node của LinkedList.

5. LinkedList insert/delete tốt nhưng chưa chắc đã nhanh.

Giả sử bạn cần insert hoặc delete ở giữa list. Trước khi có thể insert/delete, nó phải duyệt qua một nửa số phần tử của list, điều mà LinkedList làm tệ nhất

Một số mẹo khi dùng với list

findFirst hay findAny

Image description

Có người thích dùng findFirst, có người lại findAny, cái nào đúng hơn?
Với sequential stream và List trong Java là một list có thứ tự thì findFirst hay findAny cho ra kết quả như nhau và tốc độ như nhau trong mọi trường hợp.
Nhưng đối với parallel stream, findAny có thể trả ra kết quả khác với findFirst. Hoặc bạn dùng nó với Set thì 2 hàm cũng cho ra kết quả khác nhau.

Tìm kiếm một phần tử trong list

Trước Java 8, tôi thường code như dưới đây

Image description

Nhưng đến nay, hãy code như sau:

Image description

Không if-else, không for-loop

Kiểm tra tất cả phần tử thỏa mãn điều kiện

Image description

Kiểm tra có ít nhất một phần tử thỏa mãn điều kiện

Image description

Sort list theo một field

Sort theo ascending

Image description

Sort theo descending

Image description

Delete các phần tử thỏa mãn điều kiện với removeIf

Gọn hơn so với cách dùng iterator.remove.

Image description

Reference

Java Object Size: Estimating, Measuring, and Verifying via Profiling - DZone Java
ArrayList (Java Platform SE 8 )
LinkedList (Java Platform SE 8 )

Originally published at https://luanvv.com.

Discussion (0)