---

Hvordan er en arraylist implementeret? Er det en simpel array, som on resize
opretter en helt ny array der er stor nok til at rumme alle data, eller er
den en fragmenteret liste af mindre arrays?

Hvis det er første udgave, så vil en stor liste kunne bruge en del tid på en
resize, når grænsen brydes, men er til gengæld hurtigere at anvende senere.
Ved nogen her hvordan den er opbygget? Jeg overvejer om opslag er
langsommere i en ArrayList end i en simpel array.

---

"Jakob Nielsen" <jni@no.mail> writes:

> Hvordan er en arraylist implementeret? Er det en simpel array, som on resize
> opretter en helt ny array der er stor nok til at rumme alle data, eller er
> den en fragmenteret liste af mindre arrays?

Det er et array. Det står alt sammen i API-dokumentationen:
<URL:http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html>
ArrayList er skrevet i Java, så du kan også selv tjekke koden.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

---

> Det er et array. Det står alt sammen i API-dokumentationen:
> <URL:http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html>

Ja, det må jeg jo indrømme. Det står endda indenfor de første 4 linier.
Havde ikke prøvet at kigge der, men bare ledt lidt løsligt, og enkelte
personer har faktisk påstået at den var implementeret som en hægtet liste.
Takker for dit hurtige svar.

---

Jakob Nielsen wrote:

> Hvis det er første udgave, så vil en stor liste kunne bruge en del tid på en
> resize, når grænsen brydes, men er til gengæld hurtigere at anvende senere.
> Ved nogen her hvordan den er opbygget? Jeg overvejer om opslag er
> langsommere i en ArrayList end i en simpel array.
Hej,

Som nogen har sagt, er det et array ...

Men der er nu grænser for hvor meget til der går spildt til resize. Det
kan faktisk bevises at det blot er en konstant tid pr. element i arrayet
- også selvom du bliver ved at fylde flere og flere data på. Dog skal
den nye størrelse være en kostant * den gamle - ikke noget med at lægge
10 til eller sådan noget.

MVH
Søren