---

Hvad er forskellen på en Vector og en LinkedList ?

---

Rene Iversen skrev:

>Hvad er forskellen på en Vector og en LinkedList ?

En Vector er implementeret som et array, mens en LinkedList er
implementeret som en linket liste.

Array: Et stykke sammenhængende hukommelse hvor elementerne
ligger som naboer og kan tilgås direkte via deres pladsnummer.
Man har fat i et array via en pointer ... nå nej, det er jo Java
.... via en reference til starten.

Linket liste: Hvert element ligger på et tilfældigt sted i
hukommelsen og kan kun findes fordi det foregående har et link
dertil. Man har fat i listen via en reference til det første
element.

Hvis man kun bruger små datamængder, opdager man ikke forskellen.
Ved store datamængder er der forskel på hastigheden ved
forskellige operationer, men der er ikke én metode der er bedre
end den anden.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> wrote in message

> >Hvad er forskellen på en Vector og en LinkedList ?
>
> En Vector er implementeret som et array, mens en LinkedList er
> implementeret som en linket liste.
>

Men en vector er vel ikke statisk ligesom et array?

---

Rene Iversen skrev:

>Men en vector er vel ikke statisk ligesom et array?

Jo og nej. Det *er* et array - men det kan nedlægge sig selv og
genopstå i dobbelt størrelse med indholdet bevaret (altså udvide
sig selv dynamisk) når det bliver nødvendigt. Det sker usynligt
for brugeren.

Det betyder at det ind imellem skal bruge noget ekstra tid (til
at kopiere), og hvis man er oppe i store datastørrelser, og skal
bruge ét element mere, så kan det koste en del hukommelse. Jeg
kan dog ikke huske om der er en kommando til at frigive den tomme
plads.

Det initialiseres med plads til 20 elementer hvis man ikke selv
tvinger noget andet.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospam@lundhansen.dk> writes:

> at kopiere), og hvis man er oppe i store datastørrelser, og skal
> bruge ét element mere, så kan det koste en del hukommelse.

En Vector bruger vel ikke mere plads end en hægtet liste? En Vector af
referencer bruger _højst_ dobbelt så meget plads som nødvendigt, mens
en hægtet liste bruger _mindst_ dobbelt så meget plads som nødvendigt,
i hvert fald hvis leddene i listen er lavet noget lignende dette:

class Link {
Link next;
Object data;
};

Hvis hvert led i listen desuden er et selvstændigt objekt (og det
skulle ikke forbavse mig om det var tilfældet), får man ud over next-
og data-pointerne også en klassepointer, så man alt i alt kommer til
at bruge mindst tre gange så meget hukommelse som nødvendigt.

---

Soeren Sandmann <sandmann@daimi.au.dk> writes:

> En Vector bruger vel ikke mere plads end en hægtet liste?

En Vector (fra før den blev tilpasset Collections) var formentlig
implementeret som en Array.

--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Soeren Sandmann skrev:

>En Vector bruger vel ikke mere plads end en hægtet liste? En Vector af
>referencer bruger _højst_ dobbelt så meget plads som nødvendigt, mens
>en hægtet liste bruger _mindst_ dobbelt så meget plads som nødvendigt,

Det har du da ret i. Det havde jeg ikke gjort mig klart.

>Hvis hvert led i listen desuden er et selvstændigt objekt (og det
>skulle ikke forbavse mig om det var tilfældet), får man ud over next-
>og data-pointerne også en klassepointer, så man alt i alt kommer til
>at bruge mindst tre gange så meget hukommelse som nødvendigt.

Hvis det er objekter, er alle data vel pakket ind i objektets
attributter så der stadig kun er én objektpointer?

Hvis der er 'løse' data, er der samme problem ved arrayløsningen.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospam@lundhansen.dk> writes:

> Det har du da ret i. Det havde jeg ikke gjort mig klart.

Ja, man ser for sig et array, hvor halvdelen af indgangene bruges på
absolut ingenting, mens den hægtede liste består af led hvor alle
pointerne bruges til noget fornuftigt, så der ikke går noget til
spilde.

Det er ofte en god ide, når man tror et eller andet er mere effektivt
eller bruger mindre hukommelse end noget andet, at stille sig selv
spørgsmålet: "Hvor _meget_ bedre er det?" Nogle gange bliver man
overrasket når man regner det ud.

> Hvis det er objekter, er alle data vel pakket ind i objektets
> attributter så der stadig kun er én objektpointer?

Det jeg mente med selvstændigt objekt er at hvert led er en
selvstændig instans af en klasse som ligner dette:

class Link {
public Object data;
public Link next;
}

Java-maskinen bruger noget ekstra hukommelse pr. objekt, typisk to
ord, så i det tilfælde kommer man faktisk til at bruge fire gange så
meget hukommelse som nødvendigt.

Det jeg havde i tankerne, var at implementationen af den hægtede liste
kan reservere et stort array af Links, og så allokere fra det array,
for på den måde at undgå at bruge ekstra hukommelse til hvert
objekt-instans. Men det virker jo ikke i Java, for sådan et array
ville være et array af referencer, så der ville ikke være vundet
noget.

Man kan også forestille sig en hægtet liste som kun kan indeholde
elementer der implementerer et bestemt interface,

interface Linkable {
Linkable getNext();
}

Ved at allokere next-pointeren inde i data-objekterne kunne man med
sådan en liste spare en pointer pr. objekt i forhold til en
Vector. (Men sådan virker Javas LinkedList vist ikke).

---

Soeren Sandmann <sandmann@daimi.au.dk> writes:

> Ved at allokere next-pointeren inde i data-objekterne kunne man med
> sådan en liste spare en pointer pr. objekt i forhold til en
> Vector. (Men sådan virker Javas LinkedList vist ikke).

Til gengæld får du en tilgangstid i O(n) istedet for O(1).

--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

thunderbear@bigfoot.com (Thorbjørn Ravn Andersen) writes:

> Soeren Sandmann <sandmann@daimi.au.dk> writes:
>
> > Ved at allokere next-pointeren inde i data-objekterne kunne man med
> > sådan en liste spare en pointer pr. objekt i forhold til en
> > Vector. (Men sådan virker Javas LinkedList vist ikke).
>
> Til gengæld får du en tilgangstid i O(n) istedet for O(1).

Huh? Det er en egenskab ved hægtede lister at adgang til det n'te
element er O(n). Det ændres ikke af at next-pointeren allokeres inde i
data-objekterne.

---

Soeren Sandmann <sandmann@daimi.au.dk> writes:

> > Soeren Sandmann <sandmann@daimi.au.dk> writes:
> >
> > > Ved at allokere next-pointeren inde i data-objekterne kunne man med
> > > sådan en liste spare en pointer pr. objekt i forhold til en
> > > Vector. (Men sådan virker Javas LinkedList vist ikke).
> >
> > Til gengæld får du en tilgangstid i O(n) istedet for O(1).
>
> Huh? Det er en egenskab ved hægtede lister at adgang til det n'te
> element er O(n). Det ændres ikke af at next-pointeren allokeres inde i
> data-objekterne.

Jeg var vist for hurtig på aftrækkeren - jeg havde fået ind i hovedet
at det drejede sig om en Vectorlignende tingest implementeret med en
LinkedList.


--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Bertel Lund Hansen wrote:

> Man har fat i et array via en pointer ... nå nej, det er jo Java
> ... via en reference til starten.

Man skal nu heller ikke uden videre, sætte lighedstegn mellem en C-pointer
og en Java-reference.


/Henry

---

> >Hvad er forskellen på en Vector og en LinkedList ?
>
> En Vector er implementeret som et array, mens en LinkedList er
> implementeret som en linket liste.

.... "hægtet liste"...

Mvh. Madsie

---

Mads Andersen skrev:

>> implementeret som en linket liste.

>... "hægtet liste"...

The missing link = den manglende hægte?

"Hægtet liste" er nu ikke nogen dårlig oversættelse, men jeg er
vant til at sige "linket liste".

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Rene Iversen wrote:
> Hvad er forskellen på en Vector og en LinkedList ?
>
>

De performance-mæssige forskelle der tidligere er nævnt er rigtige nok,
og hvis du stadig er i tvivl om hvilken liste du skal anvende kan du
finde lidt interessant læsning på følgende link:

http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html

Men jeg synes dog at den "mest" interessante forskel, og i nogen
tilfælde den vigtigste forskel (også i performance-mæssig øjemed), er at
Vector er trådsikker (synchronized), hvilket LinkedList ikke er. Hvis du
ønsker at anvende an array-baseret liste, som ikke skal tilgås fra flere
tråde bør du måske istedet kigge på ArrayList istedet for Vector.

Hygge
/Dennis