Mga Dynamic na Array sa Java

Kapag gumagawa ng mga program na may iba't ibang antas ng pagiging kumplikado, ang bawat developer ay gumagamit ng maraming uri ng data, kabilang ang mga array. Ang istraktura na ito ay angkop na angkop para sa pag-iimbak ng isang set ng isang uri, nagbibigay ng mahusay na pagganap, at sa pangkalahatan ay maginhawa. Ang isang makabuluhang kawalan ng mga array ay ang mga ito ay static: ang kanilang laki ay dapat na tinukoy nang maaga. Gayunpaman, hindi pa alam ng mga programmer kung paano mahulaan ang hinaharap (maliban kung, siyempre, lumilitaw ang AI na magpoproseso ng impormasyon nang napakabilis at magagawang mahulaan ang anumang mga kaganapan). Para sa kadahilanang ito, lumikha kami ng isang istraktura na maaaring baguhin ang laki nito habang tumatakbo ang programa. Ito ay tinatawag na dynamic array .

Mga dynamic na array sa kursong JavaRush

Ang paksang ito ay nasasakupan nang napakalinaw at malinaw sa antas 7 at bahagyang nasa antas 8 ng kursong JavaRush sa Java Syntax quest. Sa paglipas ng ilang mga lecture at kasing dami ng 18 mga problema, ang mga pangunahing isyu ay sakop, mga uri ng mga dynamic na array at ang pagkakaiba sa pagitan ng mga ito, kabilang ang pagganap. Napakahalaga ng paksang ito, dahil pinapawi ng mga dynamic na array ang developer ng depression, pananakit ng ulo at nakakatipid ng hindi kapani-paniwalang dami ng oras.

Ano ang isang dynamic na array?

Ang isang dynamic na array ay isang array na maaaring magbago ng laki nito sa panahon ng pagpapatupad ng programa. Sa Java, ang papel na ito ay pangunahing ginagampanan ng mga klase ng ArrayList at LinkedList. Hindi tulad ng mga array, ang ArrayList at LinkedList ay naglalaman lamang ng mga uri ng data ng sanggunian, iyon ay, maaari lamang silang mag-imbak ng mga bagay. Sa kabutihang palad, ang Java ay may mga mekanismo ng autoboxing at autounboxing na nagbibigay-daan sa iyong mag-imbak ng mga primitive na uri sa mga dynamic na array. Tulad ng isang static na array, ang isang dynamic na array ay homogenous, iyon ay, maaari itong mag-imbak ng isang solong uri ng data. Gayunpaman, salamat sa mekanismo ng pamana at wastong paggamit ng mga interface, posibleng mag-imbak sa isang dynamic na hanay ng buong hanay ng iba't ibang klase na minana mula sa isang karaniwang isa, ngunit higit pa sa ibaba. Iyon ay, ang isang static na array ay gumagana tulad nito: At ang isang dynamic na array sa Java ay gagana tulad ng sumusunod (pagpapatuloy ng diagram mula sa ikatlong hakbang): Gumagamit ang Java ng isang espesyal na katutubong function upang kopyahin ang isang array, kaya ang ganitong "paglipat" ay hindi masyadong mahal.

Bakit kailangan natin ng isang dynamic na array?

Ang isang dynamic na array sa Java ay ginagamit upang iproseso ang mga set ng homogenous na data na ang laki ay hindi alam sa oras na isinulat ang programa. Halimbawa, maaaring gusto mong i-cache ang data ng bawat kliyente na kasalukuyang gumagamit ng application. Imposibleng mahulaan ang bilang ng mga naturang kliyente nang maaga. Kung walang mga dynamic na array, ang problemang ito ay malulutas sa mga sumusunod na opsyon:

1. Lumikha ng isang malaking hanay na 100% malamang na sakupin ang pangangailangan;
2. Gumawa ng isang static na array na magsisilbing buffer;
3. Ilapat ang iba pang mga dynamic na istruktura, tulad ng mga set.

Ang unang pagpipilian ay angkop lamang sa kaso ng isang mahigpit na limitadong saklaw. Sa ibang mga kaso, ang ganitong array ay kukuha ng malaking halaga ng memory space, na lubhang hindi epektibo. Ang pangalawa ay mangangailangan ng pagpapatupad ng mga karagdagang mekanika para sa buffer clearing, pagbabasa, at iba pa. Ang pangatlo ay mayroon ding mga disadvantages dahil sa mga pagkakaiba sa functionality.

Ano ang ginagawa ng isang dynamic na array sa Java?

Sa wikang Java, ang mga klase ng ArrayList at LinkedList ay kumikilos bilang isang dynamic na array. Ang pinakakaraniwang ginagamit ay ArrayList, dahil ito ay gumaganap bilang isang klasikong hanay, hindi katulad ng LinkedList, na nagpapatupad ng konsepto ng isang dobleng naka-link na listahan. Pag-uusapan natin ito mamaya.

ArrayList, LinkedList - mga konsepto at panuntunan sa pagpapatakbo

Ang ArrayList ay isang klasikong array na maaaring palawakin sa panahon ng pagpapatupad ng programa. Ito ay batay sa isang regular na array: ang laki nito kapag ginawa ay 10 elemento. Habang lumalaki ang laki, tumataas ang kapasidad. Ang mga patakaran kung saan gumagana ang ArrayList:

• Tulad ng isang static na array, ito ay na-index mula sa 0;
• Ang pagpasok sa dulo at pag-access sa pamamagitan ng index ay napakabilis - O(1);
• Upang magpasok ng isang elemento sa simula o gitna, kakailanganin mong kopyahin ang lahat ng mga elemento sa isang cell sa kanan, at pagkatapos ay i-paste ang isang bagong elemento sa kinakailangang posisyon;
• Ang pag-access ayon sa halaga ay nakasalalay sa bilang ng mga elemento - O(n);
• Hindi tulad ng isang klasikong array, maaari itong mag-imbak ng null;

Sa kaso ng LinkedList, ang lahat ay medyo mas kumplikado: ito ay batay sa isang dobleng naka-link na listahan. Iyon ay, sa istruktura, ang dynamic na Java array na ito ay isang bilang ng mga nakakalat na bagay na tumutukoy sa isa't isa. Mas madaling ipaliwanag gamit ang mga larawan. Sa loob ng LinkedList mayroon kaming pangunahing object Head, na nag-iimbak ng impormasyon tungkol sa bilang ng mga elemento, pati na rin ang isang link sa una at huling mga elemento: Ngayon ang field size = 0ay , firstat last = null. Ang bawat elemento na idinagdag sa listahang ito ay ang nilalaman ng isang hiwalay na panloob na bagay. Magdagdag tayo ng elemento Johnny: Ngayon ay mayroon na tayong node na may halagang “Johnny”. Para sa pangunahing elemento, ang mga link sa una at huling elemento ay tumuturo sa bagong node. Ang bagay na ito ay mayroon ding mga link sa nakaraan at susunod na mga elemento. Ang link sa nauna ay palaging magiging null, dahil ito ang unang elemento, at ang link sa susunod ay palaging magiging null, dahil wala pa ito. Ayusin natin ito: Nagdagdag ng bagong elemento na may value na “Watson”, na naging pangalawa. Pakitandaan na ang unang elemento ay may field nextna tumuturo sa susunod na elemento, at ang bagong elemento ay may field previousna tumuturo sa nauna. Para sa pangunahing elemento, ang link sa huling elemento ay tumuturo na ngayon sa bagong node. Ang sumusunod na diagram ay nagpapakita kung paano magdagdag ng mga elemento sa gitna ng listahan: Isang bagong elementong “Hamish” ang naidagdag. Upang ipasok ito sa gitna ng listahan, italaga lamang ang mga link sa mga elemento, tulad ng ipinapakita sa figure. Ipinapaliwanag ng mga larawang ito ang proseso ng isang dobleng naka-link na listahan sa pinakamataas na antas, nang hindi nagdedetalye. Upang ibuod ang kuwento tungkol sa LinkedList, maaari tayong kumuha ng ilang panuntunan para sa pagpapatakbo nito:

• Tulad ng isang array, ito ay na-index mula sa 0;
• Ang pag-access sa una at huling elemento ay hindi nakadepende sa bilang ng mga elemento - O(1);
• Ang pagkuha ng isang elemento sa pamamagitan ng index, pagpasok o pagtanggal mula sa gitna ng isang listahan ay depende sa bilang ng mga elemento - O(n);
• Maaari mong gamitin ang mekanismo ng iterator: pagkatapos ay ang pagpasok at pagtanggal ay magaganap sa patuloy na oras;
• Hindi tulad ng isang klasikong array, maaari itong mag-imbak ng null.

Mga halimbawa ng code

Tingnan natin ang ilang halimbawa. Kasama sa mga snippet ng code ang mga halimbawa para sa ArrayList at LinkedList.

Paglikha

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

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

Pagdaragdag ng isang elemento

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

Sa unang sulyap, ang mga pamamaraan add()ng AND addLast()ay gumaganap ng parehong pag-andar, ngunit ang pamamaraan add()ay dumating sa LinkedList mula sa interface List, at ang pamamaraan addLastay nagmula sa interface Deque. Ipinapatupad ng LinkList ang parehong mga interface na ito. Ang isang mabuting kasanayan sa kasong ito ay ang paggamit ng paraang pinakaangkop para sa konteksto. Kung ang LinkList ay ginagamit bilang isang pila, kung gayon ito ay pinakamahusay na gamitin ang addLast. Kung ginamit ang LinkList bilang isang listahan, magiging angkop na gamitin ang add().

Pag-alis ng isang elemento

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

Kung ang isang bagay ay tinanggal sa pamamagitan ng index, ibabalik ng pamamaraan ang tinanggal na bagay. Kung ang isang bagay ay tinanggal ayon sa halaga (o ang una o huling elemento ng isang LinkedList ay tinanggal), ang pamamaraan ay nagbabalik ng true kung ang bagay ay natagpuan at tinanggal, mali kung hindi.

Pag-access sa isang item at paghahanap sa listahan

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

Naglalakad sa isang loop

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

Narito ito ay nagkakahalaga ng pagsasabi ng ilang mga salita tungkol sa paghahanap. Maraming mga baguhan na developer, kapag naghahanap ng isang elemento sa isang listahan, simulan ang paghahanap sa isang loop, paghahambing ng lahat ng mga elemento sa hinanap, sa kabila ng pagkakaroon ng mga pamamaraan indexOf()at lastIndexOf(). Maaari mo ring gamitin ang pamamaraan contains()upang makuha ang katotohanan na ang isang elemento ay nasa listahan:

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

Mga link para sa karagdagang pagbabasa

1. Mayroong isang mahusay na artikulo dito tungkol sa pag-alis ng mga elemento mula sa isang ArrayList. Dahil sa katotohanan na ito ay isang dynamic na Java array , mayroong maraming mga subtleties sa pag-alis ng mga elemento.
2. Ang mga gawain ng ArrayList ay inilalarawan nang detalyado dito .
3. Kaunti pa tungkol sa LinkList.
4. Isang pares ng mga artikulo mula kay Habr tungkol sa ArrayList at LinkedList .