luan vu

Posted on Apr 23, 2022

ArrayList và LinkedList trong Java

#java #arraylist #linkedlist #list

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.

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.

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

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

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

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

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

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

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

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

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

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

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.

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.

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

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.