Mảng động trong Java

Khi tạo các chương trình có mức độ phức tạp khác nhau, mỗi nhà phát triển sử dụng nhiều loại dữ liệu, bao gồm cả mảng. Cấu trúc này rất phù hợp để lưu trữ một bộ cùng loại, mang lại hiệu suất tuyệt vời và nói chung là thuận tiện. Một nhược điểm đáng kể của mảng là chúng tĩnh: kích thước của chúng phải được xác định trước. Tuy nhiên, các lập trình viên vẫn chưa biết cách dự đoán tương lai (tất nhiên trừ khi xuất hiện AI sẽ xử lý thông tin cực kỳ nhanh chóng và có thể dự đoán bất kỳ sự kiện nào). Vì lý do này, chúng tôi đã tạo một cấu trúc có thể thay đổi kích thước của nó trong khi chương trình đang chạy. Nó được gọi là mảng động .

Mảng động trong khóa học JavaRush

Chủ đề này được đề cập rất dễ hiểu và rõ ràng ở cấp độ 7 và một phần ở cấp độ 8 của khóa học JavaRush trong nhiệm vụ Cú pháp Java. Trong suốt một số bài giảng và có tới 18 bài toán, các vấn đề chính sẽ được đề cập, các loại mảng động và sự khác biệt giữa chúng, bao gồm cả hiệu suất. Chủ đề này cực kỳ quan trọng, vì mảng động giúp nhà phát triển giảm bớt trầm cảm, đau đầu và tiết kiệm một lượng thời gian đáng kinh ngạc.

Mảng động là gì?

Mảng động là mảng có thể thay đổi kích thước trong quá trình thực hiện chương trình. Trong Java, vai trò này chủ yếu được thực hiện bởi các lớp ArrayList và LinkedList. Không giống như mảng, ArrayList và LinkedList chỉ chứa các kiểu dữ liệu tham chiếu, nghĩa là chỉ có các đối tượng mới có thể được lưu trữ trong chúng. May mắn thay, Java có cơ chế tự động đóng hộp và tự động mở hộp cho phép bạn lưu trữ các kiểu nguyên thủy trong mảng động. Giống như mảng tĩnh, mảng động có tính đồng nhất, tức là nó có thể lưu trữ một kiểu dữ liệu duy nhất. Tuy nhiên, nhờ cơ chế kế thừa và sử dụng giao diện hợp lý, có thể lưu trữ trong một mảng động toàn bộ các lớp khác nhau được kế thừa từ một lớp chung, nhưng còn nhiều hơn thế ở bên dưới. Nghĩa là, một mảng tĩnh hoạt động như thế này: Và một mảng động trong Java sẽ hoạt động như sau (chúng ta tiếp tục sơ đồ từ bước thứ ba): Trong Java, một hàm gốc đặc biệt được sử dụng để sao chép mảng, do đó, một “di chuyển” như vậy sẽ ” không đắt lắm.

Tại sao chúng ta cần một mảng động?

Mảng động trong Java được sử dụng để xử lý các tập hợp dữ liệu đồng nhất có kích thước không xác định tại thời điểm chương trình được viết. Ví dụ: bạn có thể muốn lưu trữ dữ liệu của mọi khách hàng hiện đang sử dụng ứng dụng vào bộ nhớ đệm. Không thể dự đoán trước số lượng khách hàng như vậy. Nếu không có mảng động, vấn đề này có thể được giải quyết bằng các tùy chọn sau:

1. Tạo một mảng lớn có khả năng đáp ứng 100% nhu cầu;
2. Tạo một mảng tĩnh sẽ hoạt động như một bộ đệm;
3. Áp dụng các cấu trúc động khác, chẳng hạn như tập hợp.

Tùy chọn đầu tiên chỉ phù hợp trong trường hợp phạm vi bị giới hạn nghiêm ngặt. Trong các trường hợp khác, một mảng như vậy sẽ chiếm nhiều dung lượng bộ nhớ, điều này cực kỳ kém hiệu quả. Thứ hai sẽ yêu cầu triển khai các cơ chế bổ sung để xóa, đọc bộ đệm, v.v. Cái thứ ba cũng có nhược điểm do sự khác biệt về chức năng.

Công việc của mảng động trong Java là gì

Trong ngôn ngữ Java, các lớp ArrayList và LinkedList hoạt động như một mảng động. Được sử dụng phổ biến nhất là ArrayList, vì nó hoạt động như một mảng cổ điển, không giống như LinkedList, thực hiện khái niệm danh sách liên kết đôi. Chúng ta sẽ nói về nó một lát sau.

ArrayList, LinkedList - khái niệm và quy tắc hoạt động

ArrayList là một mảng cổ điển có thể được mở rộng trong quá trình thực hiện chương trình. Nó dựa trên một mảng thông thường: kích thước của nó khi được tạo là 10 phần tử. Khi kích thước tăng lên, công suất tăng lên. Các quy tắc mà ArrayList hoạt động:

• Giống như mảng tĩnh, nó được lập chỉ mục từ 0;
• Chèn ở cuối và truy cập theo chỉ mục rất nhanh - O(1);
• Để chèn một phần tử vào đầu hoặc giữa, bạn sẽ cần sao chép tất cả các phần tử sang bên phải một ô, sau đó dán phần tử mới vào vị trí yêu cầu;
• Truy cập theo giá trị phụ thuộc vào số phần tử - O(n);
• Không giống như mảng cổ điển, nó có thể lưu trữ null;

Trong trường hợp LinkedList, mọi thứ phức tạp hơn một chút: nó dựa trên danh sách liên kết đôi. Nghĩa là, về mặt cấu trúc, mảng Java động này là một số đối tượng nằm rải rác tham chiếu đến nhau. Nó dễ dàng hơn để giải thích bằng hình ảnh. Bên trong LinkedList chúng ta có một đối tượng chính Head, lưu trữ thông tin về số lượng phần tử, cũng như liên kết đến phần tử đầu tiên và cuối cùng: Bây giờ trường size = 0là , firstvà last = null. Mỗi phần tử được thêm vào danh sách này là nội dung của một đối tượng bên trong riêng biệt. Hãy thêm một phần tử Johnny: Bây giờ chúng ta có một nút có giá trị “Johnny”. Đối với phần tử chính, các liên kết đến phần tử đầu tiên và cuối cùng trỏ đến nút mới. Đối tượng này cũng có liên kết đến các phần tử trước và phần tử tiếp theo. Liên kết đến phần trước sẽ luôn là null, vì đây là phần tử đầu tiên và liên kết đến phần tiếp theo sẽ luôn là null, vì nó chưa tồn tại. Hãy khắc phục điều này: Đã thêm một phần tử mới có giá trị “Watson”, phần tử này trở thành phần tử thứ hai. Xin lưu ý rằng phần tử đầu tiên có trường nexttrỏ đến phần tử tiếp theo và phần tử mới có trường previoustrỏ đến phần tử trước đó. Đối với phần tử chính, liên kết đến phần tử cuối cùng bây giờ trỏ đến nút mới. Sơ đồ sau đây cho thấy cách thêm các phần tử vào giữa danh sách: Một phần tử mới “Hamish” đã được thêm vào. Để chèn nó vào giữa danh sách, chỉ cần gán lại các liên kết đến các phần tử, như trong hình. Những minh họa này giải thích quy trình của danh sách liên kết đôi ở cấp cao nhất mà không đi sâu vào chi tiết. Để tóm tắt câu chuyện về LinkedList, chúng ta có thể rút ra một số quy tắc hoạt động của nó:

• Giống như một mảng, nó được lập chỉ mục từ 0;
• Quyền truy cập vào phần tử đầu tiên và cuối cùng không phụ thuộc vào số lượng phần tử - O(1);
• Lấy một phần tử theo chỉ mục, chèn hoặc xóa từ giữa danh sách tùy thuộc vào số lượng phần tử - O(n);
• Bạn có thể sử dụng cơ chế lặp: khi đó việc chèn và xóa sẽ diễn ra theo thời gian không đổi;
• Không giống như mảng cổ điển, nó có thể lưu trữ giá trị rỗng.

Ví dụ về mã

Chúng ta hãy đi qua một số ví dụ. Đoạn mã bao gồm các ví dụ cho cả ArrayList và LinkedList.

Sự sáng tạo

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Thêm một phần tử

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

Thoạt nhìn, các phương thức add()AND addLast()thực hiện chức năng tương tự, nhưng phương thức này add()đến từ LinkedList từ giao diện Listvà phương thức này addLastđến từ giao diện Deque. LinkedList triển khai cả hai giao diện này. Cách thực hành tốt trong trường hợp này là sử dụng phương pháp phù hợp nhất với ngữ cảnh. Nếu LinkedList được sử dụng làm hàng đợi thì tốt nhất nên sử dụng phương thức addLast. Nếu LinkedList được sử dụng làm danh sách thì việc sử dụng add().

Loại bỏ một phần tử

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Nếu một đối tượng bị xóa theo chỉ mục, phương thức sẽ trả về đối tượng đã xóa. Nếu một đối tượng bị xóa theo giá trị (hoặc phần tử đầu tiên hoặc cuối cùng của LinkedList bị xóa), phương thức sẽ trả về true nếu đối tượng được tìm thấy và xóa, ngược lại là sai .

Truy cập một phần tử và tìm kiếm trong danh sách

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Đi bộ trong một vòng lặp

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Ở đây cần nói đôi lời về tìm kiếm. Nhiều nhà phát triển mới làm quen, khi tìm kiếm một phần tử trong danh sách, bắt đầu tìm kiếm theo vòng lặp, so sánh tất cả các phần tử với phần tử được tìm kiếm, bất chấp sự hiện diện của các phương thức indexOf()và lastIndexOf(). Bạn cũng có thể sử dụng phương thức này contains()để biết thực tế rằng một phần tử có trong danh sách:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Liên kết để đọc thêm

1. Có một bài viết tuyệt vời ở đây về cách xóa các phần tử khỏi ArrayList. Do đây là một mảng Java động nên việc loại bỏ các phần tử có rất nhiều điều tinh tế.
2. Hoạt động của ArrayList được minh họa chi tiết tại đây .
3. Tìm hiểu thêm một chút về LinkedList.
4. Một vài bài viết của Habr về ArrayList và LinkedList .