Uneori, colecția necesită o capacitate nelimitată și o ușurință de utilizare a listei, dar cu un timp de acces constant la un element arbitrar, ca într-o matrice. În acest caz, este utilizată o listă bazată pe array - o matrice dinamică (Listă de elemente de array).
Clasa ArrayList
Un ArrayList este o colecție care implementează interfața IList
- O serie de T (_items) pentru stocarea elementelor.
- Constructorul implicit, care creează o listă goală.
- Un constructor care ia un număr întreg care creează o listă cu o anumită capacitate. Rețineți că capacitatea listei și lungimea ei nu sunt aceleași. În practică, poate apărea o situație în care un astfel de designer va permite utilizatorului să evite un număr mare de extensii ale matricei interne.
Introducerea elementelor
Introducerea elementelor într-o matrice dinamică este diferită de inserarea într-o listă asociată. Există două motive pentru aceasta. Primul: matricea dinamică acceptă inserarea în mijlocul matricei, în timp ce lista conectată poate fi inserată numai la sfârșit sau la început. Al doilea: introducerea unui element într-o listă legată este întotdeauna efectuată în timp constant. Introducerea într-o matrice dinamică poate lua atât timp O (1) cât și O (n).
Extensia matricei
Pe măsură ce elementele sunt adăugate, matricea internă poate depăși. În acest caz, trebuie să faceți următoarele:
- Creați o matrice de dimensiune mai mare.
- Copiați elementele într-un nou tablou.
- Actualizați referința la matricea internă a listei, astfel încât aceasta să indice cea nouă.
Acum rămâne să răspundem la întrebarea cu privire la dimensiunea unei noi matrice. Aceasta este determinată de strategia de creștere a matricei dinamice. Vom analiza două strategii, iar pentru ambele vom vedea cât de repede crește matricea și cât de mult crește performanța acesteia.
Creștere dublă (abordare Mono și Rotor)
Există două implementări ale lui ArrayList. cod care poate fi găsit pe rețea: mono și rotor. Ambele utilizează un algoritm simplu pentru a mări dimensiunea matricei, dublând-o, dacă este necesar. Dacă dimensiunea inițială a matricei este zero, noua matrice va conține 16 elemente:
Acest algoritm face mai puține alocări de memorie, dar petrece mai mult spațiu decât versiunea adoptată în Java. Cu alte cuvinte, acesta oferă cazuri mai frecvente de introducere a unui timp constant, cu costul utilizării mai multor memorii. Procesul de creare a unei noi matrice și de copiere a elementelor în el va fi mai puțin frecvent.
Creșterea lentă (abordare Java)
Java utilizează o abordare similară, dar matricea crește mai încet. Dimensiunea matricei noi este determinată după cum urmează:
Utilizarea acestui algoritm utilizează mai puțină memorie.
Să ne uităm la curbele de creștere a rețelelor de până la 200.000 de elemente folosind aceste două strategii:
După cum se poate observa din grafic, pentru a trece granița în 200.000 de elemente, opțiunea de dublare matrice a 19 tranzacții și alocări de copiere, în timp ce versiunea Java a necesare 30 de operații.
Care strategie este mai bună? Nu există un răspuns corect și greșit la această întrebare. Când se folosește dublarea, vom avea mai puține operații de inserare pe O (n), dar mai multă utilizare a memoriei. Cu o creștere mai lentă, se va folosi mai puțină memorie. În general, ambele opțiuni sunt acceptabile. Dacă cererea dvs. are cerințe specifice, este posibil să fie necesar să implementați una sau altă strategie de expansiune. În orice caz, comportamentul extern al matricei dinamice nu se va schimba.
Implementarea noastră va folosi o dublare (abordare Mono / Rotor)
Introduceți metoda
- Comportament: adaugă un element la indexul specificat. Dacă indicele este egal sau mai mare decât numărul de elemente, aruncă o excepție.
- Complexitate: O (n).
Introducerea la un anumit index necesită o schimbare a tuturor elementelor, pornind de la acest index, o poziție în dreapta. Dacă matricea internă este plină, inserția va crește dimensiunea sa.
Următorul exemplu oferă o matrice cu cinci poziții, dintre care patru sunt ocupate. Valoarea "3" se introduce în a treia poziție (cu indexul 2):
Array înainte de a schimba elementele
Arra după schimbarea elementului
Array după introducerea unui element într-o poziție goală
- Comportament: adaugă un element la sfârșitul listei.
- Complexitate: O (1), dacă mai este mai mult de un spațiu liber; O (n), dacă aveți nevoie să extindeți matricea.
Ștergerea elementelor
Metoda RemoveAt
- Comportament: șterge elementul aflat la indexul specificat.
- Complexitate: O (n).
Ștergerea unui element după index este o operație inversă. Elementul specificat este șters și elementele rămase sunt mutate într-o poziție în stânga.
Array înainte de a elimina un element
Arra după eliminarea unui element
Arra după schimbarea elementului
Metoda de eliminare
- Comportament: elimină primul element al cărui valoare este egală cu cea dată. Returnează adevărat. dacă elementul a fost șters sau altfel fals.
- Complexitate: O (n).
Accesarea elementelor
Metoda IndexOf
- Comportament: returnează indexul primului element a cărui valoare este egală cu cea furnizată sau -1 dacă nu există o astfel de valoare.
- Complexitate: O (n).
Item Metoda
- Comportament: vă permite să citiți sau să modificați valoarea indexului.
- Complexitate: O (1).
Conține metoda
- Comportament: returnează adevărat. dacă valoarea este în listă și altfel falsă.
- Complexitate: O (n).
Metoda GetEnumerator
- Comportament: returnează un IEnumerator iterator
Pentru a trece prin toate elementele din listă. - Complexitate: Obținerea unui iterator este O (1), traversarea listei este O (n).
Observați că nu putem merge doar prin matricea _items. deoarece conține celule care nu sunt încă umplute, deci limităm intervalul prin care vom itera numărul de elemente.
Alte metode IList
Metoda clară
- Comportament: elimină toate elementele din listă.
- Complexitate: O (1).
Există două opțiuni pentru implementarea metodei Clear. În primul caz, se creează o nouă matrice goală, în al doilea caz, numai câmpul Count este zero. În implementarea noastră va fi creată o nouă matrice de zero lungimi.
- Comportament: copiază toate elementele din matricea internă la cea specificată, începând de la indexul specificat.
- Complexitate: O (n).
Numărătoarea metodei
- Comportament: returnează numărul curent de elemente din colecție. Dacă lista este goală, returnează 0.
- Complexitate: O (1).
Count este un câmp auto-incrementat cu un setter privat și un getter public. Utilizatorul îl poate citi numai și poate modifica metodele de adăugare și eliminare a elementelor.
Metoda IsReadOnly
- Comportament: întotdeauna se întoarce false. deoarece colecția noastră este variabilă.
- Complexitate: O (1).
A continua
Aceasta incheie parsarea unor tablouri dinamice. Data viitoare vom trece la stive și cozi.
Trimiteți-le prietenilor: