Khám Phá Java Collections: Hướng Dẫn Chi Tiết Về ArrayList, LinkedList và Vector (Phần 1)

Giới thiệu

Gần đây, mình nhận được nhiều câu hỏi liên quan đến Collections trong Java, bao gồm các cấu trúc dữ liệu như ArrayList, LinkedList, Set và nhiều hơn nữa. Khi suy ngẫm lại, mình nhận ra rằng bản thân đã lâu không ôn lại kiến thức này, đặc biệt là khi trong các dự án mình đã sử dụng chủ yếu ArrayList mà không xem xét các lựa chọn khác. Chính vì vậy, bài viết này sẽ giúp mình và bạn đọc cùng nhau khám phá Collections bằng một phương pháp mới mẻ, đó là đọc mã nguồn của chúng.

Sơ Đồ Cấu Trúc Các Collection

Trước khi đi sâu vào từng loại Collection, chúng ta cần có cái nhìn tổng quát về cấu trúc của chúng. Dưới đây là sơ đồ đơn giản để giúp bạn dễ dàng hình dung.

I - ArrayList

1. Khởi Tạo ArrayList

Chúng ta sẽ bắt đầu bằng cách khởi tạo một ArrayList. Trong môi trường phát triển như IntelliJ, bạn có thể sử dụng phím tắt Ctrl + click để xem mã nguồn của ArrayList. Bạn sẽ thấy rằng nó kế thừa từ AbstractList<E> và implements các interface như List<E>, RandomAccess, Cloneable, và java.io.Serializable. Để hiểu rõ hơn, chúng ta tiếp tục nghiên cứu mã nguồn của AbstractList<E>.

2. Tìm Hiểu Về Iterable

Trong mã nguồn của ArrayList, chúng ta thấy có một interface gọi là Iterable, cho phép đối tượng trở thành mục tiêu của vòng lặp for-each. Điều này có nghĩa là nếu bạn implements interface này, bạn có thể dễ dàng sử dụng vòng lặp for-each trong code của mình. Dưới đây là một ví dụ đơn giản để minh họa:

public class SimpleIterable implements Iterable<Integer> {
    private final int[] numbers;

    public SimpleIterable(int[] numbers) {
        this.numbers = numbers;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            private int index = 0;

            @Override
            public boolean hasNext() {
                return index < numbers.length;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return numbers[index++];
            }
        };
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        SimpleIterable iterable = new SimpleIterable(nums);

        for (int number : iterable) {
            System.out.println(number);
        }
    }
}

3. Khám Phá Collection

Interface Collection chứa nhiều phương thức cơ bản mà các collection khác sử dụng. Điều này giúp các lập trình viên có thể nhanh chóng hiểu và áp dụng các phương thức cần thiết trong dự án của mình.

4. Exploratory về SequencedCollection

Interface này định nghĩa các phương thức cần thiết cho các collection có cấu trúc liên kết. Mọi loại List như ArrayList hay LinkedList đều sử dụng Node để kết nối với nhau.

5. AbstractList

AbstractList cung cấp một triển khai cơ bản cho interface List, giúp giảm bớt công sức lập trình viên trong việc triển khai các phương thức cần thiết cho một kho dữ liệu truy cập ngẫu nhiên như mảng.

6. Tìm Hiểu Về ArrayList

Class ArrayList có ba kiểu constructor: nhận vào kích thước mặc định, constructor rỗng, và constructor với một mảng có sẵn. Đặc biệt, phương thức add của ArrayList rất thú vị vì khi chèn một phần tử, mọi phần tử sau đó phải được dịch chuyển để tạo không gian cho phần tử mới. Điều này khiến việc thêm hoặc xóa phần tử ở đầu mảng trở nên chậm hơn, còn việc truy vấn phần tử theo index thì rất nhanh, chỉ O(1).

Tóm Tắt Về ArrayList

ArrayList là cấu trúc dữ liệu mảng động, sử dụng index để truy cập các phần tử. Việc thêm hoặc xóa phần tử ở vị trí đầu hoặc giữa mảng chậm (O(n)), nhưng việc chèn hoặc xóa ở cuối mảng nhanh chóng (O(1)).

II - LinkedList

1. Khám Phá LinkedList

Để hiểu thêm về LinkedList, chúng ta vẫn làm theo quy trình tương tự như ArrayList. Sự khác biệt lớn nhất chính là cấu trúc của LinkedList, nơi mà mỗi Node được kết nối với nhau thông qua con trỏ, cho phép việc thêm và xóa phần tử trở nên dễ dàng và nhanh chóng hơn so với ArrayList.

2. Tóm Tắt Về LinkedList

LinkedList là cấu trúc dữ liệu liên kết hai chiều, cho phép chèn và xóa phần tử dễ dàng (O(1)), nhưng duyệt qua nó lại chậm hơn (O(n)).

III - Vector

Chúng ta cũng không thể không nhắc đến Vector, một version truyền thống hơn của ArrayList. Điểm khác biệt chính là Vector được đồng bộ hóa, phù hợp cho các ứng dụng đa luồng. Tuy nhiên, bạn vẫn có thể đồng bộ hóa ArrayList thông qua Collections.synchronizedList nếu cần thiết.

IV - Kết Luận

Qua bài viết này, chúng ta đã khám phá cách tiếp cận Collections trong Java qua việc tìm hiểu mã nguồn. Nếu bạn có góp ý hay câu hỏi nào, hãy để lại ý kiến dưới bài viết này nhé. Chúc mọi người một ngày học tập và làm việc hiệu quả!
source: viblo