Wednesday, June 19, 2019 00:59

List

Lista dinamică (List<T>) este una dintre cele mai populare structuri de date utilizate în programare. Nu are o dimensiune fixă ​​precum array-urile și permite accesul direct prin index, spre deosebire de listele legate (LinkedList<T>). Array-ul dinamic este de asemenea cunoscută sub numele de „array listă”, „array redimensionabil” și „array dinamic”. List<T> își păstrează elementele într-un array, care are o dimensiune mai mare decât numărul elementelor stocate. De obicei, când adăugăm un element, există o celulă goală în array-ul interior al listei. Prin urmare, această operațiune durează un timp constant. Ocazional, array-ul se umple și trebuie să se extindă. Acest lucru ia timp liniar, dar se întâmplă foarte rar. Dacă avem o mulțime de adăugări, complexitatea medie a cazului de adăugare a unui element în List<T> va fi o constantă. Dacă însumăm pașii necesari pentru adăugarea a 100.000 de elemente (pentru ambele cazuri – „adăugare rapidă” și „adăugare cu extensie”) și împărțim cu 100.000, vom obține o constantă care va fi aproape aceeași ca și în cazul adăugarii a 1.000.000 de elemente.

Această complexitate statistic medie, calculată pentru o cantitatea suficientă de operațiuni, se numește complexitate amortizată. Amortizarea complexității liniare înseamnă că dacă adăugăm 10.000 de elemente consecutiv, numărul total de pași va fi de ordinul a 10.000. În cele mai multe cazuri, adăugarea se va executa într-un timp constant. Căutarea în List<T> este o operație lentă deoarece trebuie să traversați prin toate elementele. Eliminarea prin index sau valoare se execută într-un timp liniar. Este o operație lentă deoarece trebuie să mutăm toate elementele după cel șters cu o poziție la stânga. Accesul indexat în List<T> este instant, într-un timp constant, deoarece elementele sunt stocate intern într-o matrice. Practic, List<T> combină cele mai bune caracteristici dintre array-uri și liste, acesta fiind motivul pentru care este o structură de date preferată în multe situații. De exemplu, dacă trebuie să procesăm un fișier text și să extragem din el toate cuvintele (cu duplicate) care se potrivesc cu o expresie regulară, structura de date cea mai potrivită în care le putem acumula este List<T>, pentru că avem nevoie de o listă, a cărei lungime nu este cunoscută în prealabil și poate crește dinamic. Array-ul dinamic (List<T>) este potrivită atunci când trebuie să adăugăm frecvent elemente, să păstrăm ordinea lor de adăugare și să le accesăm prin index. Dacă adesea trebuie să căutăm sau să ștergem elemente, List<T> nu este structura de date corectă. Utilizați List<T> când trebuie să adăugați rapid elemente și să le accesați prin index.

Modul în care declarăm o listă este simplu. Așa cum am aflat de la lecția Generice, <T> indică faptul că putem folosi orice tip de date dorim, deoarece metoda, structura, clasa, etc. nu știe ce tip de date îi trimitem. În cazul nostru, List<T> înseamnă că lista noastră poate stoca orice fel de elemente: int, string, float etc. Acesta este modul în care se declară și se inițiază o List<T>:

Prin înlocuirea lui <T> cu <int>, am spus listei noastre că dorim să stocăm elemente de tip integer. Procedura este aceeași pentru orice alt tip de date. Putem chiar să declarăm o clasă cu metode și membri, iar apoi să creăm o listă de tipul acelei clase:

Un lucru de observat în legătură cu lista este faptul că odată ce o declarați de un anumit tip, nu puteți adăuga alte tipuri în ea. Cu alte cuvinte, dacă declarați o listă de tip string, puteți adăuga numai variabile de tip string și nici un alt tip.

Cele mai importante metode ale Listelor sunt:

Add() – adaugă un element-obiect nou, la sfârșit. Putem continua adăugarea elementelor în colecție până când memoria se va termina. Exemplu:

AddRange() – pentru adăugarea mai multor elemente simultan, cum ar fi adăugarea unui array la o listă, vom folosi metoda AddRange. Acest lucru poate simplifica codul care combină colecțiile. Iată cum îl folosim:

Clear() – Puteți apela metoda instanță Clear() a listelor. Exemplu:

Sort(), Reverse() – aceste metode fac exact ceea ce spune numele lor: sortează o listă sau inversează ordinea elementelor sale. În cazul sortării, pentru șiruri de caractere, ordonează în ordine alfabetică; pentru numere întregi (sau alte numere) sortează de la cel mai mic la cel mai mare. Exemplu:

Insert(), Remove(), RemoveAt() – metode folosite pentru a adăuga sau elimina elemente într-o listă. RemoveAt() utilizează un index numeric pentru a specifica elementul pe care doriți să îl eliminați. Exemplu:

IndexOf() – Această metodă determină indexul unui element al unei anumite valori din colecția listei. Caută prima poziție (de la început) a valorii. IndexOf are două supraîncărcări. Funcționează în același mod ca IndexOf-ul stringurilor. Caută după o valoare și returnează locația aceteia. Exemplu:

Contains(), Exists(), Find(). Toate aceste metode oferă metode de căutare. Acestea variază în ceea ce privește argumentele acceptate. Cu Predicate, influențăm ce elemente se potrivesc. Nu am învățat despre LinQ și predicate, dar acestea nu fac domeniul acestei lecții. Exemplu:

ToArray() – returnează un array compus din elementele listei. Exemplu:

Distinct() – elimină duplicatele dintr-o listă. Exemplu:

Equality() – Uneori trebuie să testați două liste ca fiind egale, chiar și atunci când elementele lor sunt neordonate. Le putem sorta și apoi să comparăm, sau putem folosim o metodă personalizată de listă. Exemplu:

Cele mai importante proprietăți ale listei sunt:

Capacity – Putem folosi proprietatea Capacity a listei sau să transmitem un număr întreg constructorului său (care stabilește o capacitate inițială) pentru a îmbunătăți performanța alocării.
Count – Pentru a obține numărul de elemente, accesați proprietatea Count. Acest lucru este rapid – trebuie doar să evitați metoda extensie Count. Count, pe tipul listă, este sinonim cu Length pe array.

Comments

comments

Tags: ,

Leave a Reply