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>:
1 |
List<int> lista = new List<int>(); |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
using System.Collections; class Program { static void Main() { //declara o noua lista de tip clasa custom, declarata mai jos List<Test> listaMea = new List<Test>(); //adauga o noua instanta a clasei custom ca element al listei noastre listaMea.Add(new Test() { integerulMeu = 5, stringulMeu = "un string" }); //acceseaza o variabila a clasei custom din lista noastra int integerNou = listaMea[0].integerulMeu; //apeleaza metoda din clasa custom stocata in lista noastra listaMea[0].MetodaMea(); } } //declara o clasa custom class Test { public int integerulMeu; public string stringulMeu; public void MetodaMea() { Console.WriteLine(stringulMeu); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
using System.Collections; class Program { static void Main() { List<int> lista = new List<int>(); lista.Add(2); lista.Add(3); lista.Add(5); lista.Add(7); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
using System; using System.Collections.Generic; class Program { static void Main() { List<int> a = new List<int>(); a.Add(1); a.Add(2); a.Add(5); a.Add(6); // Contine: // 1 // 2 // 5 // 6 int[] b = new int[3]; b[0] = 7; b[1] = 6; b[2] = 7; a.AddRange(b); // Contine: // 1 // 2 // 5 // 6 // 7 [adaugat] // 6 [adaugat] // 7 [adaugat] foreach (int i in a) { Console.WriteLine(i); } } } |
Clear() – Puteți apela metoda instanță Clear() a listelor. Exemplu:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
using System; using System.Collections.Generic; class Program { static void Main() { List<bool> lista = new List<bool>(); lista.Add(true); lista.Add(false); lista.Add(true); Console.WriteLine(lista.Count); // 3 lista.Clear(); Console.WriteLine(lista.Count); // 0 } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
using System; using System.Collections.Generic; class Program { static void Main() { List<string> lista = new List<string>(); lista.Add("ton"); lista.Add("crap"); lista.Add("stiuca"); // sorteaza tipul de pesti alfabetic, in ordine ascendenta (A - Z) lista.Sort(); foreach (string valoare in lista) Console.WriteLine(valoare); var invers = lista.Reverse(); // afiseaza continutul listei. foreach (string valoare in invers) Console.WriteLine(valoare); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
using System.Collections.Generic; class Program { static void Main() { List<int> lista = new List<int>(); for (int i = 0; i < 100000; i++) { // Insereaza inaintea primului element lista.Insert(0, i); // INCET } //sterge elementele listei lista.Clear(); for (int i = 0; i < 100000; i++) { // Adauga la sfarsit lista.Add(i); // RAPID } //declara un nou array de tip integer int[] b = new int[3]; b[0] = 7; b[1] = 6; b[2] = 7; //insereaza noul array in lista, la pozitia 1 lista.InsertRange(1, b); //sterge un element specific lista.Remove(5); //sterge un element la un anumit index lista.RemoveAt(2); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
sing System; using System.Collections.Generic; class Program { static void Main() { List<int> numerePrime = new List<int>(new int[] { 19, 23, 29 }); int index = numerePrime.IndexOf(23); // Exista. Console.WriteLine(index); index = numerePrime.IndexOf(10); // Nu exista. Console.WriteLine(index); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // Creaza o lista cu trei elemente var lista1 = new List<string>(); lista1.Add("pisica"); lista1.Add("caine"); lista1.Add("molie"); // Cauta dupa acest element. if (lista1.Contains("caine")) Console.WriteLine("Caine a fost gasit"); // cauta acest element independent de majuscule sau minuscule. // ... aceasta este metoda LINQ cu acelasi nume. if (lista1.Contains("MOLIE", StringComparer.OrdinalIgnoreCase)) Console.WriteLine("MOLIE a fost gasita (indiferent de caz)"); // Acest element nu este gasit. Console.WriteLine(lista1.Contains("peste")); List<int> lista2 = new List<int>(); lista2.Add(7); lista2.Add(11); lista2.Add(13); // verifica daca exista elemente mai mari ca 10. bool exista = lista2.Exists(element => element > 10); Console.WriteLine(exista); // Verifica dupa numere mai mici de 7. exista = lista2.Exists(element => element < 7); Console.WriteLine(exista); List<int> lista3 = new List<int>(new int[] { 19, 23, 29 }); // Gaseste primul element mai mare de 20 int rezultat = lista3.Find(item => item > 20); Console.WriteLine(rezultat); } } |
ToArray() – returnează un array compus din elementele listei. Exemplu:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
using System; using System.Collections.Generic; class Program { static void Main() { // Lista oraselor pe care trebuie sa le unim. List<string> orase = new List<string>(); orase.Add("New York"); orase.Add("Mumbai"); orase.Add("Berlin"); orase.Add("Istanbul"); // Uneste stringurile intr-o linie CSV (comma separated values - valori separate prin virgula). string linie = string.Join(",", orase.ToArray()); Console.WriteLine(linie); } } |
Distinct() – elimină duplicatele dintr-o listă. Exemplu:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // Lista cu elemente duplicat. List<int> lista = new List<int>(); lista.Add(1); lista.Add(2); lista.Add(3); lista.Add(3); lista.Add(4); lista.Add(4); lista.Add(4); foreach (int valoare in lista) { Console.WriteLine("Inainte: {0}", valoare); } // Preia elementele distincte si converteste-le intr-o lista noua. List<int> distinct = list.Distinct().ToList(); foreach (int valoare in distinct) { Console.WriteLine("Dupa: {0}", valoare); } } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
using System; using System.Collections.Generic; class Program { static void Main(string[] args) { List<Cub> cuburi = new List<Cub>(); cuburi.Add(new Cub(8, 8, 4)); cuburi.Add(new Cub(8, 4, 8)); cuburi.Add(new Cub(8, 6, 4)); if (cuburi.Contains(new Cub(8, 6, 4))) Console.WriteLine("Un cub egal exista deja in colectie."); else Console.WriteLine("Cubul poate fi adaugat."); //Afiseaza "Un cub egal exista deja in colectie." } } public class Cub : IEquatable<Cub> { public int Inaltime { get; set; } public int Lungime { get; set; } public int Latime { get; set; } public Cub(int _inaltime, int _lungime, int _latime) { this.Inaltime = _inaltime; this.Lungime = _lungime; this.Latime = _latime; } public bool Equals(Cub altul) { if (this.Inaltime == altul.Inaltime && this.Lungime == altul.Lungime && this.Latime == altul.Latime) return true; else return false; } } |
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.
Tags: lista, structuri de date