01. Arrays & Lists (Mảng và Danh sách)

🎯 Mục tiêu học tập

  • Hiểu khái niệm và cách hoạt động của Array và List
  • Phân tích độ phức tạp các thao tác cơ bản
  • Biết khi nào nên sử dụng Array vs List
  • Cài đặt dynamic array từ đầu

📚 Lý thuyết

Array (Mảng)

Định nghĩa: Cấu trúc dữ liệu lưu trữ các phần tử cùng kiểu trong bộ nhớ liên tiếp.

Đặc điểm: - Kích thước cố định (trong Java) - Truy cập ngẫu nhiên O(1) qua index - Bộ nhớ liên tiếp → cache-friendly

Độ phức tạp: - Truy cập: O(1) - Tìm kiếm: O(n) - Chèn/Xóa ở cuối: O(1) - Chèn/Xóa ở giữa: O(n)

Dynamic Array (ArrayList trong Java)

Định nghĩa: Mảng có thể tự động thay đổi kích thước.

Cách hoạt động: 1. Bắt đầu với kích thước nhỏ (vd: 10) 2. Khi đầy, tạo mảng mới gấp đôi kích thước 3. Copy dữ liệu cũ sang mảng mới 4. Giải phóng mảng cũ

🔍 So sánh Array vs ArrayList

Tiêu chí Array ArrayList
Kích thước Cố định Động
Performance Nhanh hơn Chậm hơn (do boxing/unboxing)
Memory Ít hơn Nhiều hơn
Kiểu dữ liệu Primitives + Objects Chỉ Objects
Tính năng Cơ bản Nhiều method tiện ích

💡 Khi nào sử dụng?

Sử dụng Array khi:

  • Biết trước kích thước
  • Cần performance cao
  • Làm việc với primitive types
  • Memory hạn chế

Sử dụng ArrayList khi:

  • Kích thước thay đổi liên tục
  • Cần các method tiện ích (sort, search...)
  • Làm việc với objects
  • Ưu tiên tính dễ sử dụng

🎨 Các biến thể phổ biến

1. Static Array (Mảng tĩnh)

int[] numbers = new int[5]; // Kích thước cố định 5

2. Dynamic Array (Mảng động)

ArrayList<Integer> list = new ArrayList<>(); // Kích thước thay đổi

3. Multidimensional Array (Mảng đa chiều)

int[][] matrix = new int[3][4]; // Ma trận 3x4

🔧 Thao tác cơ bản cần implement

  1. Constructor: Khởi tạo với capacity ban đầu
  2. add(element): Thêm phần tử vào cuối
  3. add(index, element): Thêm phần tử vào vị trí chỉ định
  4. get(index): Lấy phần tử tại vị trí index
  5. set(index, element): Cập nhật phần tử tại vị trí index
  6. remove(index): Xóa phần tử tại vị trí index
  7. size(): Trả về số phần tử hiện tại
  8. isEmpty(): Kiểm tra danh sách có rỗng không
  9. contains(element): Kiểm tra phần tử có tồn tại không
  10. indexOf(element): Tìm vị trí đầu tiên của phần tử

📋 Bài tập thực hành

Cơ bản:

  1. Cài đặt MyArrayList từ đầu
  2. Tìm phần tử lớn nhất/nhỏ nhất trong mảng
  3. Đảo ngược mảng
  4. Xóa phần tử trùng lặp

Nâng cao:

  1. Merge hai mảng đã sắp xếp
  2. Tìm phần tử xuất hiện nhiều nhất
  3. Rotate mảng k vị trí
  4. Two Sum problem

🚀 Chuẩn bị code

Khi sẵn sàng coding, tạo thư mục và file:

mkdir 01-arrays-lists
cd 01-arrays-lists
# Files sẽ được tạo:
# - MyArrayList.java (Implementation)
# - ArrayDemo.java (Examples & Tests)
# - ArrayProblems.java (Practice problems)

📖 Tài liệu tham khảo