So sánh Array và LinkedList

Chiều 30 tết cuối năm, rảnh viết nốt bài để đón tết con Heo 😀

Tiếp tục là 1 bài về so sánh các thứ trong Java, cái này thi thoảng cũng gặp khi phỏng vấn nhưng bài này mình muốn giúp các bạn có thể hiểu rõ hơn về bản chất để sử dụng hợp lý hơn, đảm bảo hiệu năng tốt hơn.

Trước tiên mình muốn đề cập Array mô tả 1 cấu trúc dữ liệu mảng cơ bản từ C/C++. Array được lưu trữ trong 1 dãy các ô nhớ liền nhau trong bộ nhớ và có thể truy xuất trực tiếp đến từng phần tử thông qua số thứ tự [index] của phần tử trong mảng. Không có các tiện ích sẵn để add/get/remove… phần tử mà chỉ có thuộc tính length để lấy kích thước. Kích thước của Array là cố định và buộc phải định nghĩa khi khai báo.

Còn ArrayList LinkedList và Vector, cả 3 cái này đều là class implement List, trong đó List là 1 collection trong Java được thiết kế có đầy đủ các method cơ bản như get, add, remove, sort,… vì vậy ArrayList LinkedList và Vector implement lại List đều mang đầy đủ những tiện ích này từ List. List được lưu trữ dưới dạng các ô nhớ rải rác trong bộ nhớ trỏ đến nhau thông qua địa chỉ ô nhớ. Việc này nhằm tối ưu về bộ nhớ có thể tận dụng các ô nhớ ở các vị trí khác nhau không nhất thiết phải liền nhau, nhưng lại gây ra việc không thể truy xuất trực tiếp đến 1 phần từ bất kỳ mà phải duyệt từ đầu List để tìm.

Tìm hiểu chi tiết hơn.

LinkedList là class implement List và cũng mang đầy đủ tiện ích của List và được bổ sung thêm các tiện ích của Deque tối ưu cho các thao tác add/remove phần từ, hay các tiện ích của AbstractSequentialList giúp tối ưu khi duyệt phần tử bằng Iterator. Nhưng lại không được tối ưu cho việc truy xuất ngẫu nhiên qua số thứ tự phần tử nên ít khi được sử dụng. Kích thước danh sách là động và được tăng mỗi khi bổ sung phần tử.

ArrayList là class implement List, được mang thêm tiện ích của RandomAccess giúp tối ưu việc truy xuất ngẫu nhiên qua số thứ tự, nhưng lại không được implement Deque nên các thao tác add/remove không nhanh như LinkedList [mình sẽ có ví dụ test performce cụ thể ở dưới]. Kích thước ArrayList là cố định tại 1 thời điểm, nhưng có thể resize thêm 50% mỗi khi đạt giới hạn max hiện tại nên có thể coi là kích thước động.

Vector là class implement giống hệt ArrayList nên mang đầy đủ tiện ích như ArrayList có, và hơn thế nữa được xây dựng thêm các method thao tác phần tử như addElement setElement removeElement insertElement …. và đặc biệt các method của Vector đều được cài đặt synchronized nghĩa là safe nhưng fail-fast, an toàn cho dữ liệu khi sử dụng trong đa luồng nhưng lại gây chậm xử lý. Kích thước của Vector tương tự như ArrayList chỉ khác là sẽ tăng 100% mỗi khi đạt giới hạn max hiện tại.

Các bạn có thể đọc thêm docs của java hoặc đơn giản là decompile jdk hoặc đọc trong source nén của jdk để thấy rõ hơn về những sự giống và khác biệt này.

Tổng hợp lại dưới dạng bảng từ đó rút ra cân nhắc sử dụng cái nào trong từng trường hợp cụ thể.

Dưới đây là các đoạn test performance khi thực hiện add/get/remove trên Array/ArrayList/LinkedList để nhìn trực quan hơn về sự khác biệt. Các kết quả có thể sẽ không chính xác như ví dụ với từng lần chạy nhưng về cơ bản vẫn có độ chênh lệch có thể nhìn thấy

package net.tunghuynh.listcollection; import org.apache.log4j.Logger; import java.util.*; /** * net.tunghuynh.listcollection.Main * by Tùng Huynh * at 04/02/2019 13:12 AM */ public class Main { static Logger logger = Logger.getLogger[Main.class]; static int n = 100000; public static void main[String[] args] { arrayListVsLinkedList[]; } public static void arrayListVsLinkedList[] { Integer[] array = new Integer[n]; List arrayList = new ArrayList[]; List linkedList = new LinkedList[]; logger.info["==== Add ===="]; long start = System.nanoTime[]; for [int i = 0; i < n; i++] { array[i] = i; } logger.info["Array : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [int i = 0; i < n; i++] { arrayList.add[i]; } logger.info["ArrayList : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [int i = 0; i < n; i++] { linkedList.add[i]; } logger.info["LinkedList: " + [System.nanoTime[] - start]/1000000.0 + " ms"]; logger.info["==== Get ===="]; start = System.nanoTime[]; for [int i = 0; i < n; i++] { Integer x = array[i]; } logger.info["Array loop index : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [int i = 0; i < n; i++] { arrayList.get[i]; } logger.info["ArrayList loop index : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [int i = 0; i < n; i++] { linkedList.get[i]; } logger.info["LinkedList loop index : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [Object item : arrayList] { Object x = item; } logger.info["ArrayList loop interator : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [Object item : linkedList] { Object x = item; } logger.info["LinkedList loop interator: " + [System.nanoTime[] - start]/1000000.0 + " ms"]; logger.info["==== Remove ===="]; start = System.nanoTime[]; for [int i = 9999; i >=0; i--] { arrayList.remove[i]; } logger.info["ArrayList : " + [System.nanoTime[] - start]/1000000.0 + " ms"]; start = System.nanoTime[]; for [int i = 9999; i >=0; i--] { linkedList.remove[i]; } logger.info["LinkedList: " + [System.nanoTime[] - start]/1000000.0 + " ms"]; } }