Tento reťazec Vytvorili sme objekt triedy Arraylist . V ňom je rad desiatich odkazov na celé číslo (10 je dĺžka poľa vnútri Arraylist predvolené). Žiadna z polí tohto poľa nám však nie je k dispozícii, a metóda "LIST.IPOPTY ();" Návrat TRUE. V našom zozname zatiaľ neexistuje žiadny prvok. Na obrázku to bude vyzerať takto:

Po použití "List.Add (5);" Dostaneme nasledujúci obrázok:

V prípade, že máme pridávanie prvku desaťkrát v rade a chcú urobiť tento jedenásty čas, budeme mať problém. Problém je v tom, že naše pole skončilo v zozname a nikde na písanie údajov viac. Preto potrebujeme rozšíriť pole. To sa deje automaticky. Na to je vytvorené nové pole Veľká dĺžka a hodnoty z predchádzajúceho poľa sú skopírované. Toto je dosť drahá prevádzka, vykonáva sa o o (n) iterations. V zozname tried. Dĺžka nového poľa je lepšia na dĺžku starého poľa jeden a pol krát. Celkom, ak robíte 11 krát v rade, operácia "List.Add (5);", potom sa ukázalo na nasledujúci obrázok:

Všimli sme tiež, že vykonanie operácie "List.Remove (index);" Neznižuje skutočnú dĺžku poľa v zozname.

Tabuľka pracovný čas na priemerných operáciách pre Arraylist .

Teraz zvažujeme asymptotický čas vykonávajúci operácie nad ArrayList :

Všimnite si, že pre pridanie (hodnota) a pridať (index, hodnota), čas vykonávania je O (1) a O (veľkosť - index), v tomto poradí, hoci v horší prípad Tieto operačné práce O (veľkosť). Ukážme, prečo sa priemerná prevádzka pre pridanú prevádzku (hodnota) získa O (1).

Odhadovanie prevádzky pridanej prevádzky (hodnota).

Poďme po prvé, zvážte možnosť, v ktorej sa zvýšenie poľa vyskytuje len jeden prvok. V tomto prípade, pri pridávaní nového prvku by sme museli vytvoriť nové pole zakaždým a skopírujte všetky prvky starého. Čas pridania práce (hodnota) je teda (vrátane v priemere) rovná O (n). Dokonca aj v prípade rozšírenia našej oblasti zakaždým na prvkach K, pracovný čas v priemere by stále o (n). Naozaj. Každý čas K-th sa operácia vykonáva pre O (N) av iných prípadoch pre O (1). Ak si vezmete aritmetický priemer, potom sa dostaneme C * N, to znamená o (n).

Teraz uvažujeme o skutočnom prípade, v ktorom došlo k predĺženiu polohy každé polčasy. Dovoľte nám vyplniť prepojenie typu objektu Prvky veľkosti. Predpokladajme tiež, že pridať posledný prvok Naše pole muselo expandovať. Vypočítame, koľko času bolo potrebné vyplniť tento objekt. Posledné pridanie prvku prijalo poradie veľkosti operácií. Niekoľko predchádzajúcich hovorov obsadilo približne jednu operáciu. Predposledné "dlhé" pridávanie bolo vyrobené približne (2/3) * Operácie veľkosti (ako pole sa rozširuje zakaždým, keď jeden a polkrát). Atď. Dostaneme, že operácie boli vykonané približne:

veľkosť + (2/3) * Veľkosť + (2/3) 2 * Veľkosť + (2/3) 3 * Veľkosť + ... \u003d veľkosť / (1 - 2/3) \u003d 3 * veľkosť

Dostali sme, že vykonanie veľkosti pridania (hodnota) sa raz vyskytuje veľkosť C *, a to znamená, že čas vykonávania pridania (hodnota) je O (1).

Ďalšie metódy v ArrayList .

Okrem už študovaných metód pre Arraylist Stále existuje niekoľko metód, ktoré sú užitočné na poznanie: trimtosize () a inserturacepacity (kapacita). Prvá metóda znižuje pole na dĺžku, ktorá je uložená v parametri Arraylist . To znamená, že pri použití jednoducho, nevýznamné prvky poľa sa jednoducho odstránia. Pri používaní "List.SUNDACACITY (kapacita);" Dĺžka poľa bude aspoň kapacita. Tieto metódy by mali byť na pamäti, ale nie sú tak často potrebné. Obe tieto operácie vám umožňujú ušetriť pamäť a insúrovaciu kapacitu (kapacita) s riadnym používaním znižuje čas prevádzky programu.

Tiež, dĺžka poľa môže byť nastavená pri konštrukcii objektu triedy arraylist . Ak chcete úlohu úlohu počiatočnej dĺžky kapacity, stačí písať:

Arraylist. Zoznam \u003d Nový Arraylist (Kapacita);

Záver.

ArrayList triedny prehľad Dokončíme malé porovnanie s triedou LinkEdlist .

V Arraylist. Ľubovoľný prístup k položke zoznamu sa vyskytuje v konštantnom čase, keď v prepojení - Pre lineárne. V tomto ohľade je lepšie použiť objekt triedy Arraylist . Ale ja ho opäť varím, musíte sa vyhnúť používaniu takýchto operácií ako dostať (I). Ak máte možnosť obísť get (i) volanie, potom je lepšie využiť túto príležitosť.

Vzhľadom k tomu, že Java je objektovo orientovaný programovací jazyk, významný pokrok v boji o ukladanie pamäti, žiadna z žiadnej inej triedy dostane. Hoci formálne v tomto pláne vyhráva Arraylist (Ak sa domnievame, že má takéto príležitosti, ako je tritisize), táto výhra je nevýznamná.

Linkovaný zoznam. Je to dobré, pretože vždy presne vieme, koľko času bude mať pridanie nového prvku. V Arraylist. Môžeme hovoriť len o priemernom čase pridania nového prvku.

Hlavný nedostatok Arraylist Je to, že možnosť volania špeciálnych konfunkcií pre túto triedu je v rozpore s idealogickou objektovo orientovaným programovaním.

Dátové štruktúry v obrázkoch. Arraylist.

• Java.

Pozdravy, habraloudi!

Trvalo mi, aby som napísal niekoľko článkov v mojej hlave, o tom, ako sa v Java realizujú niektoré dátové štruktúry. Dúfam, že články budú užitočné pre vizuálne (naše obrázky z našich všetkých), nováčikových Java vizuálov a tých, ktorí sú už schopní písať nový Arraylist (), ale slabo predstavuje to, čo sa deje vo vnútri.

Dnes budeme hovoriť o Arraylist-Ah

Arraylist - implementuje zoznam zoznamu. Ako viete, v Java Polia Majú pevnú dĺžku a po vytvorení poľa, nemôže rásť ani znížiť. ArrayList môže zmeniť svoju veľkosť počas vykonania programu a pri vytváraní objektu nie je potrebné špecifikovať rozmer. Arraylist Prvky môžu byť absolútne akékoľvek typy vrátane null.

Vytvorenie objektu