Nu var det for at gøre det kort
mht ArrayList:
Hvis du starter med initialSize=1 og increment= 1 og hælder 100 elementer
ind kontra start med initialsize=100, så er der en mærkbar forskel (læs -99
memcpy instruktioner). Det håber jeg trods alt vi kan blive enige om, derfor
var jeg "irriteret" på en arraycopy.
Men ok, mit ordvalg bliver som det nu engang er
Mht. LinkedList:
Hvis du kigger på src for java.util.LinkedList, vil du opdage, at det er en
dobbelthægtet cirkulær liste, så append og prepend bliver "næsten" det samme
tidsmæssigt. Det er insert-in-between (eller add(index, object)), som har
problemerne. Men igen, det var bare for at give manden noget af en
forklaring. Vi kan vel altid beregne kompleksiteten, når det bliver
nødvendigt
--
/Niels Bech Nielsen -- Logical
SCJ2P - ** Sun Certified Java 2 Programmer **
"Morten Primdahl" <morten@caput.com> skrev i en meddelelse
news:3AD16206.5F44779E@caput.com...
> Niels Bech Nielsen wrote:
> >
> > Arraylist implementerer listen ved at holde et internt array af objects.
Når
> > det array bliver for fyldt, laves et nyt, større array og det gamle
indhold
> > flytter herover. Da arrays er ganske hurtigt, er denne konstruktion
ganske
> > anvendeligt. Dog er arraycopy lidt irriterende. Se konstructor med
> > (initialSize, increment) for at optimere en ArrayList.
>
> Irriterende, hvorledes? Den amortiserede tid er O(1) hvis de bruger
> array fordobling.
>
> > LinkedList er som navnet antyder en lænket liste (jfr lærebøger om
> > datastrukturer). Internt repræsenteres object i en Node i en hægtet
liste,
> > som selvfølgelig er lige dynamisk og hver tilføjelse af element tager
præcis
> > n tid.
>
> Det kommer vel an på om man appender eller prepender :)
>
> Mvh Morten
>
> >
> > /Niels
> > --
> > /Niels Bech Nielsen -- Logical
> > SCJ2P - ** Sun Certified Java 2 Programmer **
> >
> > "Lars" <svend@bent.dk> skrev i en meddelelse
> > news:9ans9d$2urm$1@news.cybercity.dk...
> > > En væsentlig pointe er at referere til både ArrayList og LinkedList
som
> > > List's (upcast), fordi det ofte giver en mulighed for at teste begge
> > > implementationer - og derved hvad for en af dem som kører bedst
> > >
> > > /Lars
> > >
> > > "Henry Vest" <hv@softadvice.dk> skrev i en meddelelse
> > > news:GE5r6.10621$lk1.315665@twister.sunsite.dk...
> > > > Er der nogen der kan forklare forskellem mellem en LinkedList og en
> > > > ArrayList?
> > > >
> > > > Henry
> > > >
> > > >
> > > >
> > >
> > >
>
> --
> Morten Primdahl Caput A/S Tel +45 70 12 24 42
> morten@caput.com Nygade 6 Fax +45 70 11 24 42
>
http://www.caput.com/ DK-1164 Kbh K