Hej igen!
Skrivet av Teknocide:
Den länkade listan i Java verkar vara dubbellänkad vilket kan tyckas lite synd eftersom varje List-item håller två referenser istället för bara en, vilket är tillräckligt för det mesta. Jag inte hur den är implementerad internt men en "smart" länkad lista är en tunn wrapper runt ett värde, med en referens till nästa länkade lista (jag gissar att det är detta du menar). Implementeras den på detta vis är utrymmeskravet negligerbart för referensen, men att skapa varje list-item är förhållandevis dyrt. När listan väl "är igång" är filteroperationer, sortering osv mycket effektivare då listan kan delas i flera bitar utan någon nyallokering, och inte behöver byggas om när ett värde tas bort.
Anledningen till att den är dubbellänkad är antagligen för att möjliggöra bra prestanda på interfacet java.util.ListIterator som samtliga standardlistklasser bland Collections-klasserna implementerar. Till skillnad från vanliga java.util.Iterator där man kan stega igenom en lista från början till slutet så kan man stega både fram och bak med en ListIterator. Håller dock med dig att det i särklass vanligaste användningsfallet är att man stegar/itererar igenom hela listan framifrån till slutet och gör något med innehållet under tiden.
Din beskrivning av hur en "smart" länkad lista stämmer även in på LinkedList med just den redna nämnda detaljen att den tunna wrappern innehåller referenser till både föregående och nästa element.
Det jag dock fortfarande vill påpeka att man måste vara väldigt medveten att varje tillägg på en LinkedList medför en allokering av ett nytt objekt. Du verkar förstå det men jag skriver det för att förtydliga för andra som läser och är intresserade av de olika aspekterna runt val av olika list-klasser.
Det finns ju ett fall där LinkedList är riktigt dålig. Det är när man vill hämta godtyckligt element i listan. Med en LinkedList så måste den stega från början (eller slutet) tills den nått objektet. Här är dubbellänkningen till en liten hjälp för listan kan välja att stega antingen från början eller slutet beroende på vilken som är närmast målet. En ArrayList däremot, som bara har en intern array har ju "omedelbar" tillgång till alla objekt. Så när det handlar om "random access" så vinner ju ArrayList stort.
Jag håller med dig om att filteroperationer är smidiga med länkade listor, där man i ett eller flera omgångar ska filtrera bort (eller göra urval av) objekt.
Däremot sortering är mer tveksamt. Även om det kan verka logiskt så behöver man inte ta bort några element ur listan när man sorterar. Det räcker med att ersätta dem. Eftersom alla element i listan bara är referenser så är själva ersättandet billigt.
Det är ju något som Sun själva tänkte på när de implementerade sina standard-sorteringsrutiner. Detta är saxat från java.util.Collections#sort(List) och java.util.Collections#sort(List,Comparator) (den sistnämnda är ju ett bra sätt att sköta sortering med egna krav):
Citat:
This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
Sedan är det ju ingen riktigt inlägg om man inte har en personlig anekdot
Jag jobbar mycket med större finansiella system där givetvis prestanda är en väldigt viktig parameter i det hela. I många fall så handlar användningsfallet att få en lista från någonstans (till exempel en databas) och sedan filtrera bort prylar man inte vill ha med och sedan passera de vidare till nästa aktör i kedjan.
Efter benchmarking så var valet självklart hos oss. ArrayList vinner som filtreringslista. Om vi fortsätter med exemplet långt ovan med 100 poster. Vad som händer är att vi får en lista med de 100 posterna i (det exakta antalet och implementationen av listan vet vi inte i förhand). Sedan skapar vi en ny ArrayList som är den som ska innehålla det filtrerade resultatet med en initial kapacitet av lika många poster som den första (dvs 100). Det gör att vi kan snabbt stega över inlistan och kopiera över det vi vill filterlistan utan att orsaka en enda väx-operation på resultat listan. I värsta fall dock så ska allt filtreras bort och då har vi en ArrayList med 0 element i sig men med en intern allokering av 100. Fast då det är referenser så är det förhållandevis billigt. Den stora prestandavinsten är dock i att vi slipper alla interna allokeringar (och sedan den efterföljande skräpuppsamlingen) som LinkedList innebär. Minnesallokatorn är ju i värsta fall en resurs som är delad med alla trådar som körs i JVM:en.
Fast som sagt, detta är en personlig anekdot. Olika användningsfall och situationer kräver olika lösningar. Att utvärdera olika lösningar i sin egen miljö är alltid bra istället för att bara lyssna på olika personer på forum
Ha en bra dag!
//C
PS: Gnejs, vadå? Det här är väl ungefär vad trådskaparen frågade efter?
