Tatasusunan Dinamik di Jawa

Apabila mencipta program dengan pelbagai tahap kerumitan, setiap pembangun menggunakan banyak jenis data, termasuk tatasusunan. Struktur ini sangat sesuai untuk menyimpan set satu jenis, memberikan prestasi yang hebat, dan secara amnya mudah. Kelemahan tatasusunan yang ketara ialah ia statik: saiznya mesti dinyatakan terlebih dahulu. Walau bagaimanapun, pengaturcara masih belum tahu bagaimana untuk meramal masa depan (melainkan, sudah tentu, AI muncul yang akan memproses maklumat dengan sangat cepat dan dapat meramalkan sebarang peristiwa). Atas sebab ini, kami mencipta struktur yang boleh menukar saiznya semasa program sedang berjalan. Ia dipanggil tatasusunan dinamik .

Tatasusunan dinamik dalam kursus JavaRush

Topik ini diliputi dengan sangat mudah difahami dan jelas pada tahap 7 dan sebahagiannya pada tahap 8 kursus JavaRush dalam pencarian Java Syntax. Sepanjang beberapa kuliah dan sebanyak 18 masalah, isu utama dibincangkan, jenis tatasusunan dinamik dan perbezaan antara mereka, termasuk prestasi. Topik ini sangat penting, kerana tatasusunan dinamik melegakan pembangun kemurungan, sakit kepala dan menjimatkan masa yang luar biasa.

Apakah tatasusunan dinamik?

Tatasusunan dinamik ialah tatasusunan yang boleh menukar saiznya semasa pelaksanaan program. Di Jawa, peranan ini dimainkan terutamanya oleh kelas ArrayList dan LinkedList. Tidak seperti tatasusunan, ArrayList dan LinkedList mengandungi hanya jenis data rujukan, iaitu, mereka hanya boleh menyimpan objek. Nasib baik, Java mempunyai mekanisme autoboxing dan autounboxing yang membolehkan anda menyimpan jenis primitif dalam tatasusunan dinamik. Seperti tatasusunan statik, tatasusunan dinamik adalah homogen, iaitu, ia boleh menyimpan satu jenis data. Walau bagaimanapun, terima kasih kepada mekanisme pewarisan dan penggunaan antara muka yang betul, adalah mungkin untuk menyimpan dalam satu tatasusunan dinamik seluruh julat kelas yang berbeza yang diwarisi daripada satu kelas biasa, tetapi lebih banyak tentang yang di bawah. Iaitu, tatasusunan statik berfungsi seperti ini: Dan tatasusunan dinamik dalam Java akan berfungsi seperti berikut (meneruskan rajah dari langkah ketiga): Java menggunakan fungsi asli khas untuk menyalin tatasusunan, jadi "pergerakan" sedemikian tidak begitu mahal.

Mengapa kita memerlukan tatasusunan dinamik?

Tatasusunan dinamik dalam Java digunakan untuk memproses set data homogen yang saiznya tidak diketahui pada masa program ditulis. Sebagai contoh, anda mungkin mahu menyimpan cache data setiap pelanggan yang sedang menggunakan aplikasi itu. Adalah mustahil untuk meramalkan bilangan pelanggan sedemikian terlebih dahulu. Tanpa tatasusunan dinamik, masalah ini boleh diselesaikan dengan pilihan berikut:

1. Buat tatasusunan besar yang berkemungkinan 100% memenuhi keperluan;
2. Buat tatasusunan statik yang akan bertindak sebagai penimbal;
3. Gunakan struktur dinamik lain, seperti set.

Pilihan pertama hanya sesuai dalam kes julat yang sangat terhad. Dalam kes lain, tatasusunan sedemikian akan menggunakan sejumlah besar ruang memori, yang sangat tidak cekap. Yang kedua memerlukan pelaksanaan mekanik tambahan untuk pembersihan penimbal, pembacaan, dan sebagainya. Yang ketiga juga mempunyai kelemahan kerana perbezaan dalam fungsi.

Apakah tugas tatasusunan dinamik dalam Java

Dalam bahasa Java, kelas ArrayList dan LinkedList bertindak sebagai tatasusunan dinamik. Yang paling biasa digunakan ialah ArrayList, kerana ia bertindak sebagai tatasusunan klasik, tidak seperti LinkedList, yang melaksanakan konsep senarai terpaut dua kali. Kami akan bercakap mengenainya sedikit kemudian.

ArrayList, LinkedList - konsep dan peraturan pengendalian

ArrayList ialah tatasusunan klasik yang boleh dikembangkan semasa pelaksanaan program. Ia berdasarkan tatasusunan biasa: saiznya apabila dicipta ialah 10 elemen. Apabila saiz bertambah, kapasiti bertambah. Peraturan yang digunakan oleh ArrayList:

• Sama seperti tatasusunan statik, ia diindeks daripada 0;
• Sisipan pada penghujung dan capaian mengikut indeks adalah sangat pantas - O(1);
• Untuk memasukkan elemen pada permulaan atau tengah, anda perlu menyalin semua elemen satu sel ke kanan, dan kemudian menampal elemen baharu pada kedudukan yang diperlukan;
• Akses mengikut nilai bergantung pada bilangan elemen - O(n);
• Tidak seperti tatasusunan klasik, ia boleh menyimpan null;

Dalam kes LinkedList, segala-galanya sedikit lebih rumit: ia berdasarkan senarai berganda. Iaitu, secara struktur, tatasusunan Java dinamik ini ialah beberapa objek bertaburan yang merujuk antara satu sama lain. Lebih mudah untuk menerangkan dengan gambar. Di dalam LinkedList kita mempunyai objek utama Head, yang menyimpan maklumat tentang bilangan elemen, serta pautan ke elemen pertama dan terakhir: Sekarang medan size = 0ialah , firstdan last = null. Setiap elemen yang ditambahkan pada senarai ini ialah kandungan objek dalaman yang berasingan. Mari tambah elemen Johnny: Sekarang kita mempunyai nod dengan nilai "Johnny". Untuk elemen utama, pautan ke elemen pertama dan terakhir menghala ke nod baharu. Objek ini juga mempunyai pautan ke elemen sebelumnya dan seterusnya. Pautan ke yang sebelumnya akan sentiasa menjadi batal, kerana ini adalah elemen pertama, dan pautan ke yang seterusnya akan sentiasa menjadi batal, kerana ia belum wujud lagi. Mari kita betulkan ini: Menambah elemen baharu dengan nilai “Watson”, yang menjadi elemen kedua. Sila ambil perhatian bahawa elemen pertama mempunyai medan nextyang menghala ke elemen seterusnya dan elemen baharu mempunyai medan previousyang menghala ke yang sebelumnya. Untuk elemen utama, pautan ke elemen terakhir kini menghala ke nod baharu. Gambar rajah berikut menunjukkan cara menambah elemen pada bahagian tengah senarai: Elemen baharu “Hamish” telah ditambah. Untuk memasukkannya ke tengah-tengah senarai, hanya tetapkan semula pautan ke elemen, seperti yang ditunjukkan dalam rajah. Ilustrasi ini menerangkan proses senarai terpaut dua kali di peringkat atas, tanpa terperinci. Untuk meringkaskan cerita tentang LinkedList, kita boleh memperoleh beberapa peraturan untuk pengendaliannya:

• Sama seperti tatasusunan, ia diindeks daripada 0;
• Akses kepada elemen pertama dan terakhir tidak bergantung pada bilangan elemen - O(1);
• Mendapatkan elemen dengan indeks, memasukkan atau memadam dari tengah senarai bergantung pada bilangan elemen - O(n);
• Anda boleh menggunakan mekanisme lelaran: kemudian pemasukan dan pemadaman akan berlaku dalam masa yang tetap;
• Tidak seperti tatasusunan klasik, ia boleh menyimpan null.

Contoh kod

Mari kita lihat beberapa contoh. Coretan kod termasuk contoh untuk ArrayList dan LinkedList.

Ciptaan

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

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

Menambah 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

Pada pandangan pertama, kaedah add()DAN addLast()melaksanakan fungsi yang sama, tetapi kaedah itu add()datang ke LinkedList daripada antara muka List, dan kaedah itu addLastdatang daripada antara muka Deque. LinkedList melaksanakan kedua-dua antara muka ini. Amalan yang baik dalam kes ini ialah menggunakan kaedah yang paling sesuai untuk konteks. Jika LinkedList digunakan sebagai baris gilir, maka sebaiknya gunakan addLast. Jika LinkedList digunakan sebagai senarai, adalah sesuai untuk digunakan add().

Mengalih keluar 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 objek dipadamkan oleh indeks, kaedah mengembalikan objek yang dipadam. Jika objek dipadamkan mengikut nilai (atau elemen pertama atau terakhir LinkedList dipadamkan), kaedah mengembalikan benar jika objek ditemui dan dipadam, sebaliknya palsu .

Mengakses elemen dan mencari senarai

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

// Использование обычного цикла
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 adalah bernilai mengatakan beberapa perkataan tentang carian. Ramai pembangun pemula, apabila mencari elemen dalam senarai, mulakan carian dalam gelung, membandingkan semua elemen dengan yang dicari, walaupun terdapat kaedah indexOf()dan lastIndexOf(). Anda juga boleh menggunakan kaedah contains()untuk mendapatkan fakta bahawa elemen berada dalam senarai:

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

Pautan untuk bacaan lanjut

1. Terdapat artikel yang sangat baik di sini tentang mengalih keluar elemen daripada ArrayList. Disebabkan fakta bahawa ini adalah tatasusunan Java dinamik , terdapat banyak kehalusan dalam mengalih keluar elemen.
2. Cara kerja ArrayList digambarkan secara terperinci di sini .
3. Sedikit lagi tentang LinkedList.
4. Beberapa artikel daripada Habr tentang ArrayList dan LinkedList .