---

Er der nogen der kan forklare forskellem mellem en LinkedList og en
ArrayList?

Henry

---

Henry Vest wrote:
>
> Er der nogen der kan forklare forskellem mellem en LinkedList og en
> ArrayList?

ArrayList er implementeret vha. et array.
I LinkedList har hvert element i listen en reference til det naeste
(og det forrige) element.

Brug LinkedList, hvis du aendrer meget i listen.
Brug ArrayList, hvis listen er lang og du har brug for at kunne referere
et vilkaarligt element i listen.

mvh. Morten N

---

"Henry Vest" <hv@softadvice.dk> skrev:

> Er der nogen der kan forklare forskellem mellem en LinkedList og en
> ArrayList?

Jeg kan da forsøge.

En ArrayList har en bestemt størrelse, og har alle elementerne liggende i
rækkefølge, så det altid tager lige lang tid at finde et element. Til
gengæld tager det lang tid at fjerne eller tilføje et element midt i listen,
fordi så skal alle de efterfølgende elementer flyttes frem eller tilbage. At
tilføje et element tilsidst tager ikke nær så lang tid, da listen så blot
skal vokse, men det tager stadig tid.

En LinkedList har ikke nogen bestemt størrelse, og alle elementerne kan
ligge hulter til bulter i hukommelsen. Hvert element peger videre på det
næste, og tilbage på det forrige, så at fjerne et element, kræver blot at
det forrige sættes til at pege videre på det næste igen, og omvendt. At
tilføje et element kræver ligeledes ikke ret lang tid. Til gengæld tager det
længere tid at finde et element, fordi man ikke ved hvor de ligger, og
derfor skal scanne hele listen igennem.

For programmøren der benytter de to ting kan det være nogenlunde ligemeget
hvilken type man bruger, da interfacene stort set er ens, men det kan have
alvorlige performance indflydelse, om man bruger den ene eller den anden.
Hvis ens liste er forholdsvis statisk, men man tit skal bruge elementer på
vilkårlige pladser, så foretrækkes ArrayList. Hvis listen derimod er meget
dynamisk, og man ikke så tit skal søge på vilkårlige element-pladser,
foretrækkes LinkedList.

Jeg håber at det klarlagde det en smule.

mvh
Peter Lind

---

Peter Lind wrote:
>
> "Henry Vest" <hv@softadvice.dk> skrev:
>
> > Er der nogen der kan forklare forskellem mellem en LinkedList og en
> > ArrayList?
>
> Jeg kan da forsøge.
>
> En ArrayList har en bestemt størrelse,

Nej, det passer ikke. Men den er afhaengig af arrays (et af gangen), som
selvfoelgelig har bestemte stoerrelser.

mvh. Morten N

---

Takker for to udmærkede svar.

Henry

---

Ved at anvende upcast til List, kan du skifte den underliggende
implementation som det passer dig. Dvs du altid kan skifte en ArrayList til
en LinkedList, ¨ålænge du klun bruger metoder defineret i List.

/Lars

"Henry Vest" <hv@softadvice.dk> wrote in message
news:GE5r6.10621$lk1.315665@twister.sunsite.dk...
> Er der nogen der kan forklare forskellem mellem en LinkedList og en
> ArrayList?
>
> Henry
>
>
>

---

Lars wrote:

> Ved at anvende upcast til List, kan du skifte den underliggende
> implementation som det passer dig. Dvs du altid kan skifte en ArrayList til
> en LinkedList, ¨ålænge du klun bruger metoder defineret i List.

Mener du, at følgende kan lade sig gøre:

List al = new ArrayList();
LinkedList ll = (LinkedList)l;

?

Du vil altså få en ClassCastException i "(LinkedList)l;", da
en List ikke nødvendigvis er en LinkedList - i dette tilfælde
er det en ArrayList.

At konvertere ned i hierachiet er ikke altid sikkert -
og der bliver ikke lige pludseligt oprettet et LinkedList objekt, fordi
beder systemet om at se på et objekt som om det er et LinkedList
objekt. Man bør vel også generelt konvertere ned ved at checke med
instanceof først.

Man kan dog gøre følgende (som du måske også mente..):

List list = new ArrayList();
// kode der regner med at list er en ArrayList
// - add(int index, Object element) kører nu i konstant tid
// ...
list = new LinkedList( list );
// kode der regner med at list er en LinkedList
// - add(int index, Object element) kører nu i lineær tid
// ...

- da en ArrayList er en Collection. Ovenstående synes jeg nu ikke
er særlig pænt - hvis man regner med at list er et ArrayList objekt
(og programmet måske afhænger af dette), hvorfor så ikke skrive
det eksplicit?

Ulrik Magnusson

--
"I am the eggman. They are the eggmen. I am the walrus."
beatles - 'I am the walrus', Magical Mystery Tour
Visit my home page: http://www.geocities.com/ulrikm

---

Ulrik Magnusson wrote:

> List list = new ArrayList();
> // kode der regner med at list er en ArrayList
> // - add(int index, Object element) kører nu i konstant tid

Gu gør den ej - men set( int index, Object element ) gør.

Ulrik Magnusson

--
"I am the eggman. They are the eggmen. I am the walrus."
beatles - 'I am the walrus', Magical Mystery Tour
Visit my home page: http://www.geocities.com/ulrikm

---

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
>
>
>

---

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.

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. Hægtede lister skal man ikke flytte for meget data ud fra, og man
skal nok have et datagrundlag, hvor man løber listen meget i gennem enten
forlæns eller baglæns.

/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
> >
> >
> >
>
>

---

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

---

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

---

On Sat, 7 Apr 2001 22:15:31 +0200, "Lars" <svend@bent.dk> wrote:

>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
>

Forskellene er lidt mere præcist:

         Array         Linked

Indsæt i kendt index:   O(n)         O(1)
Indsæt i slutning:      O(1)         O(n) *
Indsæt i starten:      O(n)         O(1)

Slet ligner indsæt.

Find i kendt index      O(1)         O(n)
Find med nøgle:   Afhængig af algoritmen.      O(n)

* Medmindre der er en refence til "bagenden" af en LinkedList.

Hvis der er mest søgning i datastrukturen er en ArrayList at
foretrække. Hvis der er mange indsættelser/sletninger er en LinkedList
nok bedst.

Mvh
   Rune