ArrayList vs. LinkedList

"Vad sägs om lite träning för din hjärna? Jag hoppas att den fortfarande fungerar."

"Tidigare, i tabellen över behållare och samlingar såg du att samma gränssnitt kan ha flera implementeringar. Jag ska nu berätta varför vi behöver det. Och hur ArrayList skiljer sig från LinkedList ."

"Saken är att samlingar kan implementeras på olika sätt och ingen implementering är alltid idealisk. I ett tillvägagångssätt är vissa operationer snabba, men andra är långsamma. Motsatsen kan vara sant för en annan metod. Det finns ingen perfekt en-storlek- en lösning som passar alla."

"Därför togs beslutet att implementera flera versioner av samma samling. Varje implementering bör optimeras för någon snäv uppsättning operationer. Det var så olika samlingar kom till. Låt oss studera två klasser som exempel: ArrayList och LinkedList ."

"Internt är ArrayList implementerad som en vanlig array . Det är därför som att infoga ett element i mitten kräver att vi först flyttar alla efterföljande element med ett och sedan sätter det nya elementet i den lediga luckan. Att hämta och ställa in element (get, set ) är snabb , eftersom dessa operationer helt enkelt adresserar det relevanta array-elementet."

" LinkedList har en annan intern struktur. Den är implementerad som en lista med sammanlänkade element : en uppsättning distinkta element, som vart och ett lagrar referenser till nästa och föregående element i listan. För att infoga ett element i mitten av en sådan lista, du behöver bara ändra referenserna för dess framtida grannar. Men för att få element nr 130 måste du köra igenom varje objekt från 0 till 130. Med andra ord, få och ställ operationer kommer att vara långsamma . Titta på följande tabell :"

"Jag förstår. Jag börjar förstå det nu. Finns det några kriterier eller regler som skulle hjälpa mig att veta vilken samling som är bäst i en viss situation?"

"För att hålla det enkelt ska jag ge dig följande regel: om du ofta ska infoga (eller ta bort) element i mitten av samlingen är det bättre att använda LinkedList . I alla andra fall fungerar ArrayList bättre . "

"Vi kommer att fördjupa oss i hur de är uppbyggda i mer avancerade lektioner, men för tillfället ska vi bara träna på att använda dem."