Care este diferența dintre HashMap și LinkedList?

HashMap

• Implementați un array asociativ (hartă "cheie-valoare").
• Accesul, inserția și ștergerea elementelor au o complexitate medie de O(1).
• Ordinea elementelor nu este garantată.
• Utilizează hashing pentru o căutare rapidă.

// Exemplu de utilizare HashMap
import 'dart:collection';

void main() {
  final HashMap<String, int> inventar = HashMap();
  inventar['mere'] = 5;
  inventar['banane'] = 10;
  print(inventar['mere']); // Va afișa 5
}

LinkedList

• Implementează o listă legată.
• Accesul la un element după index are o complexitate de O(n).
• Inserarea și ștergerea elementelor la începutul sau sfârșitul listei au o complexitate de O(1).
• Este eficient pentru operații de adăugare/ștergere a elementelor oriunde în listă (dacă se are referință la nod) cu o complexitate de O(1).
• Suportă inserarea și ștergerea elementelor păstrând referințele către noduri (LinkedListEntry), garantând O(1).
• Ordinea elementelor corespunde ordinii de adăugare.

// Exemplu de utilizare LinkedList
import 'dart:collection';

void main() {
  final LinkedList<String> listaCumparaturi = LinkedList();
  listaCumparaturi.addFirst(LinkedListEntry('Lapte'));
  listaCumparaturi.add(LinkedListEntry('Pâine')); // Adaugă la final
  print(listaCumparaturi.first); // Va afișa Lapte
  print(listaCumparaturi.where((entry) => entry.element == 'Pâine').first.element); // Exemplu de acces, nu optim
}

// Exemplu de utilizare LinkedListEntry
class LinkedListEntry<T> extends LinkedListEntry<LinkedListEntry> {
  final T data;
  LinkedListEntry(this.data);

  @override
  String toString() => data.toString();
}

Caracteristică	HashMap	LinkedList
Structură de date	Array asociativ	Listă legată
Stocare	Perechi cheie-valoare	Nodi (elemente)
Acces după index	Nu suportat direct	O(n)
Acces după cheie	O(1) (în medie)	Nu suportat
Inserare/Ștergere	O(1) (în medie)	O(1) (la început/sfârșit), O(1) (prin referință la nod)
Ordinea elementelor	Nu garantată	Se păstrează ordinea de adăugare
Utilizare memorie	Mai mult din cauza hashing-ului	Mai puțin, dacă nodurile sunt mici
Scop principal	Căutare rapidă după cheie	Operații eficiente la început/sfârșit/oriunde (prin referință)