Jaka jest różnica między HashMap a LinkedList?

HashMap

• Implementuje tablicę asocjacyjną (mapę "klucz-wartość").
• Dostęp, wstawianie i usuwanie elementów mają średnią złożoność O(1).
• Kolejność elementów nie jest gwarantowana.
• Używa haszowania do szybkiego wyszukiwania.

// Przykład użycia HashMap
import 'dart:collection';

void main() {
  final HashMap<String, int> inwentarz = HashMap();
  inwentarz['jabłka'] = 5;
  inwentarz['banany'] = 10;
  print(inwentarz['jabłka']); // Wyświetli 5
}

LinkedList

• Implementuje listę powiązaną.
• Dostęp do elementu po indeksie ma złożoność O(n).
• Wstawianie i usuwanie elementów na początku lub końcu listy ma złożoność O(1).
• Jest wydajny dla operacji dodawania/usuwania elementów w dowolnym miejscu listy (jeśli znana jest referencja do węzła) z złożonością O(1).
• Obsługuje wstawianie i usuwanie elementów zachowując referencje do węzłów (LinkedListEntry), zapewniając O(1).
• Kolejność elementów odpowiada kolejności dodania.

// Przykład użycia LinkedList
import 'dart:collection';

void main() {
  final LinkedList<String> listaZakupów = LinkedList();
  listaZakupów.addFirst(LinkedListEntry('Mleko'));
  listaZakupów.add(LinkedListEntry('Chleb')); // Dodaje na koniec
  print(listaZakupów.first); // Wyświetli Mleko
  print(listaZakupów.where((entry) => entry.element == 'Chleb').first.element); // Przykład dostępu, nieoptymalny
}

// Przykład użycia LinkedListEntry
class LinkedListEntry<T> extends LinkedListEntry<LinkedListEntry> {
  final T data;
  LinkedListEntry(this.data);

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

Charakterystyka	HashMap	LinkedList
Struktura danych	Tablica asocjacyjna	Lista powiązana
Przechowywanie	Parę klucz-wartość	Węzły (elementy)
Dostęp po indeksie	Nie obsługiwany bezpośrednio	O(n)
Dostęp po kluczu	O(1) (średnio)	Nie obsługiwany
Wstawianie/Usuwanie	O(1) (średnio)	O(1) (na początku/końcu), O(1) (przez odniesienie do węzła)
Kolejność elementów	Nie gwarantowana	Zachowuje kolejność dodania
Użycie pamięci	Większe z powodu haszowania	Mniejsze, jeśli węzły są małe
Główne zastosowanie	Szybkie wyszukiwanie po kluczu	Efektywne operacje na początku/końcu/ dowolnej części (przez odniesienie)