Array Dinamis di Java

Saat membuat program dengan tingkat kerumitan yang berbeda-beda, setiap pengembang menggunakan banyak tipe data, termasuk array. Struktur ini sangat cocok untuk menyimpan satu set jenis, memberikan kinerja luar biasa, dan umumnya nyaman. Kelemahan signifikan dari array adalah sifatnya yang statis: ukurannya harus ditentukan terlebih dahulu. Namun, pemrogram belum mengetahui cara memprediksi masa depan (kecuali, tentu saja, muncul AI yang akan memproses informasi dengan sangat cepat dan mampu memprediksi peristiwa apa pun). Untuk alasan ini, kami membuat struktur yang dapat mengubah ukurannya saat program sedang berjalan. Ini disebut array dinamis .

Array dinamis dalam kursus JavaRush

Topik ini dibahas dengan sangat jelas dan jelas di level 7 dan sebagian di level 8 kursus JavaRush dalam pencarian Sintaks Java. Selama beberapa perkuliahan dan sebanyak 18 soal, isu-isu utama dibahas, jenis-jenis array dinamis dan perbedaan di antara keduanya, termasuk kinerja. Topik ini sangat penting, karena susunan dinamis meringankan pengembang dari depresi, sakit kepala, dan menghemat banyak waktu.

Apa itu array dinamis?

Array dinamis adalah array yang dapat diubah ukurannya selama eksekusi program. Di Java, peran ini terutama dimainkan oleh kelas ArrayList dan LinkedList. Berbeda dengan array, ArrayList dan LinkedList hanya berisi tipe data referensi, yaitu hanya dapat menyimpan objek. Untungnya, Java memiliki mekanisme autoboxing dan autounboxing yang memungkinkan Anda menyimpan tipe primitif dalam array dinamis. Seperti array statis, array dinamis bersifat homogen, yaitu dapat menyimpan satu tipe data. Namun, berkat mekanisme pewarisan dan penggunaan antarmuka yang tepat, dimungkinkan untuk menyimpan dalam satu array dinamis seluruh rangkaian kelas berbeda yang diwarisi dari satu kelas umum, tetapi lebih dari itu di bawah. Artinya, array statis berfungsi seperti ini: Dan array dinamis di Java akan bekerja sebagai berikut (melanjutkan diagram dari langkah ketiga): Java menggunakan fungsi asli khusus untuk menyalin array, jadi "pemindahan" seperti itu tidak terlalu bagus. mahal.

Mengapa kita memerlukan array dinamis?

Array dinamis di Java digunakan untuk memproses kumpulan data homogen yang ukurannya tidak diketahui pada saat program ditulis. Misalnya, Anda mungkin ingin menyimpan data setiap klien yang sedang menggunakan aplikasi dalam cache. Tidak mungkin untuk memprediksi sebelumnya jumlah klien tersebut. Tanpa array dinamis, masalah ini dapat diselesaikan dengan opsi berikut:

1. Buat array besar yang kemungkinan 100% dapat memenuhi kebutuhan;
2. Buat array statis yang akan bertindak sebagai buffer;
3. Terapkan struktur dinamis lainnya, seperti himpunan.

Opsi pertama hanya cocok jika jangkauannya sangat terbatas. Dalam kasus lain, array seperti itu akan memakan banyak ruang memori, yang sangat tidak efisien. Yang kedua akan memerlukan penerapan mekanisme tambahan untuk pembersihan buffer, pembacaan, dan sebagainya. Yang ketiga juga memiliki kekurangan karena perbedaan fungsi.

Apa yang dilakukan array dinamis di Java?

Dalam bahasa Java, kelas ArrayList dan LinkedList bertindak sebagai array dinamis. Yang paling umum digunakan adalah ArrayList, karena berfungsi sebagai array klasik, tidak seperti LinkedList, yang mengimplementasikan konsep daftar tertaut ganda. Kami akan membicarakannya nanti.

ArrayList, LinkedList - konsep dan aturan operasi

ArrayList adalah array klasik yang dapat diperluas selama eksekusi program. Ini didasarkan pada array biasa: ukurannya saat dibuat adalah 10 elemen. Seiring bertambahnya ukuran, kapasitas meningkat. Aturan kerja ArrayList:

• Sama seperti array statis, ia diindeks dari 0;
• Penyisipan di akhir dan akses berdasarkan indeks sangat cepat - O(1);
• Untuk menyisipkan elemen di awal atau tengah, Anda perlu menyalin semua elemen satu sel ke kanan, lalu menempelkan elemen baru pada posisi yang diperlukan;
• Akses berdasarkan nilai bergantung pada jumlah elemen - O(n);
• Berbeda dengan array klasik, array ini dapat menyimpan null;

Dalam kasus LinkedList, semuanya menjadi sedikit lebih rumit: ini didasarkan pada daftar tertaut ganda. Artinya, secara struktural, array Java dinamis ini adalah sejumlah objek tersebar yang saling merujuk. Lebih mudah menjelaskannya dengan gambar. Di dalam LinkedList kita mempunyai objek utama Head, yang menyimpan informasi tentang jumlah elemen, serta tautan ke elemen pertama dan terakhir: Sekarang bidangnya size = 0adalah , firstdan last = null. Setiap elemen yang ditambahkan ke daftar ini adalah konten dari objek internal yang terpisah. Mari tambahkan elemen Johnny: Sekarang kita memiliki node dengan nilai “Johnny”. Untuk elemen utama, link ke elemen pertama dan terakhir mengarah ke node baru. Objek ini juga memiliki link ke elemen sebelumnya dan berikutnya. Tautan ke elemen sebelumnya akan selalu null, karena ini adalah elemen pertama, dan tautan ke elemen berikutnya akan selalu null, karena belum ada. Mari kita perbaiki ini: Menambahkan elemen baru dengan nilai “Watson”, yang menjadi elemen kedua. Harap perhatikan bahwa elemen pertama memiliki bidang nextyang menunjuk ke elemen berikutnya, dan elemen baru memiliki bidang previousyang menunjuk ke elemen sebelumnya. Untuk elemen utama, link ke elemen terakhir sekarang mengarah ke node baru. Diagram berikut menunjukkan cara menambahkan elemen ke tengah daftar: Elemen baru “Hamish” telah ditambahkan. Untuk memasukkannya ke tengah daftar, cukup tetapkan kembali tautan ke elemen, seperti yang ditunjukkan pada gambar. Ilustrasi ini menjelaskan proses daftar tertaut ganda di tingkat atas, tanpa menjelaskan secara detail. Untuk meringkas cerita tentang LinkedList, kita dapat memperoleh beberapa aturan untuk pengoperasiannya:

• Sama seperti array, ia diindeks dari 0;
• Akses ke elemen pertama dan terakhir tidak bergantung pada jumlah elemen - O(1);
• Mendapatkan elemen berdasarkan indeks, menyisipkan atau menghapus dari tengah daftar bergantung pada jumlah elemen - O(n);
• Anda dapat menggunakan mekanisme iterator: maka penyisipan dan penghapusan akan terjadi dalam waktu yang konstan;
• Berbeda dengan array klasik, array ini dapat menyimpan null.

Contoh kode

Mari kita lihat beberapa contoh. Cuplikan kode menyertakan contoh untuk ArrayList dan LinkedList.

Penciptaan

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

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

Menambahkan elemen

// Новый элемент добавляется в конец
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

Sekilas, metode add()AND addLast()menjalankan fungsi yang sama, tetapi metode tersebut add()datang ke LinkedList dari antarmuka List, dan metode tersebut addLastberasal dari antarmuka Deque. LinkedList mengimplementasikan kedua antarmuka ini. Praktik yang baik dalam hal ini adalah menggunakan metode yang paling sesuai dengan konteksnya. Jika LinkedList digunakan sebagai antrian, maka yang terbaik adalah menggunakan addLast. Jika LinkedList digunakan sebagai daftar, sebaiknya gunakan add().

Menghapus sebuah elemen

// Удаление 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);

Jika suatu objek dihapus berdasarkan indeks, metode ini akan mengembalikan objek yang dihapus tersebut. Jika suatu objek dihapus berdasarkan nilainya (atau elemen pertama atau terakhir dari LinkedList dihapus), metode mengembalikan nilai true jika objek ditemukan dan dihapus, false jika sebaliknya.

Mengakses item dan mencari daftar

// Доступ к элементу по индексу
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");

Berjalan dalam satu lingkaran

// Использование обычного цикла
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);
}

Di sini perlu disampaikan beberapa patah kata tentang pencarian. Banyak pengembang pemula, ketika mencari elemen dalam daftar, memulai pencarian dalam satu lingkaran, membandingkan semua elemen dengan elemen yang dicari, meskipun ada metode indexOf()dan lastIndexOf(). Anda juga dapat menggunakan metode ini contains()untuk mendapatkan fakta bahwa suatu elemen ada dalam daftar:

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

Tautan untuk bacaan lebih lanjut

1. Ada artikel bagus di sini tentang menghapus elemen dari ArrayList. Karena fakta bahwa ini adalah array Java dinamis , ada banyak kehalusan dalam menghilangkan elemen.
2. Cara kerja ArrayList diilustrasikan secara rinci di sini .
3. Sedikit lebih banyak tentang LinkedList.
4. Beberapa artikel dari Habr tentang ArrayList dan LinkedList .