Welke idee implementeert de klasse LinkedList in Java?

LinkedList implementeert een dubbel gekoppelde lijst (doubly linked list).

• Elk element (knoop) bevat verwijzingen naar het vorige en volgende element in de sequentie.
• Het slaat verwijzingen op naar het eerste (head) en het laatste (tail) element van de lijst.
• Het maakt efficiënte invoegingen en verwijderingen mogelijk aan het begin, einde en in het midden van de lijst (met een complexiteit van O(1) als de verwijzing naar de knoop bekend is, of O(n) bij zoeken op index).
• Het is niet efficiënt voor willekeurige toegang tot elementen op basis van index (vereist een sequentiële doorloop, complexiteit O(n)).
• Implementeert de interfaces List en Deque, waardoor het als lijst, stapel of wachtrij kan worden gebruikt.

Vergelijking met ArrayList:

Kenmerk	LinkedList	ArrayList
Interne structuur	Dubbel gekoppelde lijst	Dynamisch array
Toevoegen/verwijderen	O(1) (aan het begin/het einde of via verwijzing naar knoop), O(n) (op index)	O(1) (aan het einde), O(n) (aan het begin/in het midden)
Willekeurige toegang	O(n)	O(1)
Geheugengebruik	Meer (houdt verwijzingen bij)	Minder (als geen uitbreiding nodig is)