Structure de données linéaires
Data structure	Collection	Ordre	Accepte Duplication	Accepte Null	Recherche & Suppression	Ajout fin	Ajout début
Tableau dynamique	ArrayList Vector (ThreadSafe)	Insertion	Oui	Oui	O(n)	O(1)	O(n)
Liste chaînée	LinkedList						O(1)
File	ArrayDeque	Insertion (FIFO)
Pile	Stack	Insertion (LIFO)				N/A ajout début

—–> Linear data structures

Structure de données non linéaires (hierarchical)
Data structure	Collection	Ordre	Accepte Duplication	Accepte Null	Ajout/Suppr/Recherche
Table de hachage	HashSet	NON	NON	Oui (1 seul)	O(1)
	HashMap
	LinkedHashSet	Insertion
	LinkedHashMap
Arbre binaire de recherche	SortedSet (TreeSet)	Valeur		NON	O(log n)
	SortedMap (TreeMap)
	PriorityQueue

—–> hierarchical-data-structure

Implémentations de Collection

• ArrayList : Peut avoir une complexité de recherche O(log n) en utilisant la recherche binaire si le tableau est ordonné (possible d’utiliser la méthode sort pour l’ordonner)
• Vector :
  • Similaire à ArrayList, mais synchronisé (thread-safe).
• LinkedList :
  • Pas de gaspillage de mémoire, car pour chaque nouveau élément on crée simplement un noeud contrairement à l’array où on doit donne une taille au tableau et donc peut avoir des emplacement vide
  • Suppression O1 si on connait l’adresse du nœuds qui précède celui à supprimer

• Queue :
  • Il est possible qu’une implémentation Queue restreigne le nombre d’éléments qu’elle contient ; ces Queue sont appelées « bounded » (délimitées). Certaines implémentations de Queue dans java.util.concurrent sont bounded, mais les implémentations dans java.util ne le sont pas.
  • BlockingQueue est très utilisés dans le concurrent programming
  • Chaque méthodes de Queue existe en deux forme la première lève une exception si elle échoue la deuxième forme renvoie une valeur null ou false si elle échoue

Type of Operation	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

• Deque :
  • Une implémentation de Queue mais qui lui ajoute plus de fonctionnalité
  • Deque propose aussi deux autres méthode qui sont : removeFirstOccurence et removeLastOccurence qui supprimment la première ou la dernière occurrence de l’élément s’il est trouvée et renvoie true sinon si l’élément n’existe pas elles renvoient false

Type of Operation	First Element (Beginning of the Deque instance)	Last Element (End of the Deque instance)
Insert	addFirst(e) offerFirst(e)	addLast(e) offerLast(e)
Remove	removeFirst() pollFirst()	removeLast() pollLast()
Examine	getFirst() peekFirst()	getLast() peekLast()

• HashSet :
  • Se base sur une HashMap pour stocker les valeurs, les valeurs sont stockées dans keys de la HashMap et comme value de HashMap c’est une constante (un objet nommé PRESENT)
• TreeSet :
  • Utilise TreeMap
• LinkedHashSet :
  • Se base sur une LinkedHashMap (même principe que HashSet)
• WeakHashMap :
  • Les entrées sont éliminées de la map lorsque la clé n’est plus référencée par aucun autre objet dans le programme.