© 1999-2003, Flemming Koch Jensen Alle rettigheder forbeholdt

Linkede lister rev: 28. august 99

"..." - ...

Abstract: x

Forudsætninger: x

 

 

	Den datastruktur vi i det følgende vil studere kan illustreres med følgende figur:
Figur 1: Linket liste
	Her skal data forstås som oplysninger; hvis struktur vi ikke her lægger os fast på. De er naturligvis præcist defineret, men deres nærmere beskaffenhed er uden betydning for det vi vil studere. Det, der er det væsentlige, er listestrukturen: at element følger element, og sammenhængen mellem dem.
Fremad og tilbage	Vi vil normalt illustrere linkede lister med referencerne gående fra venstre mod højre, og vi vil betegne denne retning som fremad i listen, men retningen modsat referencerne vil blive kaldt tilbage i listen.
	1. Hvorfor linkede lister?
	Inden vi fordyber os i linkede lister kunne vi stille spørgsmålet: Hvad skal vi med linkede lister?
Arrays er alternativ	Alternativet til linkede lister er arrays. Med et array kan vi også repræsentere en række på hinanden følgende data. Et array kan derfor løse den samme opgave, men hvor godt?
Statisk størrelse	Arrays har en ulempe - de er statiske. Et noget er statisk vil sige, at det ikke kan ændres under programudførelsen. For et arrays vedkommende ligger det statiske i, at de ikke kan ændre størrelse efter de er allokeret. Denne ulempe gør at man skal kunne forudsige hvor mange elementer man får brug for; hvilke i mange sammenhænge ikke er muligt. Såfremt man skulle anvende arrays i disse situationer, måtte man allokerer ekstra store arrays for at være på den sikre side; hvilket giver et pladsspild.
Dynamisk størrelse	Linkede lister har ikke denne statiske egenskab. Listen kan ændre størrelse dynamisk, dvs. mens programmet afvikles. Denne dynamiske egenskab har en pris: Man mister den direkte tilgang til elementerne. Det er ikke længere muligt at gå direkte til et element, man må arbejde sig igennem alle de foregående elementer, idet man følger kæden fra starten og fremad.
Byttehandel	Resultatet bliver at man løser at effektivitetsproblem mht. plads, men i stedet får et effektivitetstab mht. tid. Der er dog også andre effektivitetsforskelle mellem arrays og linkede lister, som vi vil berøre når vi i det følgende støder på dem.
	2. Implementation
	2.1 class Element
	Da vi har en række data og en reference i hvert element, der fører videre til det næste, skal de naturligvis implementes som objekter. Datakernen vil vi lade være en integer. At vi lader data blot være et heltal, giver os mulighed for samtidig at bruge den som en identifikation af det enkelte element. Det er en hjælp når vi senere skal studere en række operationer på linkede lister:
Source 1: class Element	class Element { private int data; private Element next; public Element( int d ) { this( d, null ); } public Element( int d, Element n ) { data = d; next = n; } public void next( Element n ) { next = n; } public Element next() { return next; } public int data() { return data; } public String toString() { return "" + data; } }
	Vi har to konstruktorer der viser sig at være nyttige. De kunne i princippet undværes da vi kunne lave set-metoder der kunne bruges i forbindelse med initialiseringen, men konstruktorerne forenkler det.
	Når vi skal arbejde med en linket liste får vi brug for at manipulere next-referencen derfor er set-/get-metoder nødvendigt for next. Derimod får vi kun brug for en get-metode til data.
	Man kunne fjerne den lille flig af kode-redundans, der findes mellem konstruktoren og set-metoden for next ved at lade konstruktoren kalde set-metoden.
	public Element( int d, Element n ) { data = d; next( n ); }
	Til gengæld bliver konstruktoren mere rodet at se på, da data ikke tilsvarende initialiseres på samme måde, da der ikke er nogt set-metode til data. Vi undlader derfor at gøre det, for at prioritere læsevenligheden.
Container Collection	Det kan hurtigt blive meget kompliceret at arbejde med disse lister, hvis man ikke gøre det på en kontrolleret måde. Derfor laver man en række metoder, der foretager den egentlige manipulation med referencer og elementer. Vi vil derfor bruger et objekt til at organisere en linket liste. Dette objekt kommer til at ligge imellem os og den linkede liste - det kommer til at repræsentere liste. Et sådant objekt kalder man en container eller en collection. Vi vil foretrække betegnelsen collection, alene af den grund, at det er den Java selv anvender.
	2.2 class List
	En instans af klassen List vil holde styr på den linkede liste, og alt hvad vi gør ved den vil gå gennem den. På den måde indkapsler List den linkede liste i forhold til os.
	Datakernen i List er meget enkel. Den består kun af to variable. Først en reference-variabel der refererer til det første element i den linkede liste, og dernæst en integer der holder regnskab med hvor mange elementer der er i listen. Det sidste kan være nyttigt i flere sammenhænge. Vi starter derfor ud med:
	class List { private Element first; private int size; ... }
	Vha. referencen til det første element i listen, bliver det muligt for List at udføre alle de operationer vi får brug for. Når vi bruger referencerne til at bevæge os rundt i listen kan vil kun bevæge os fremad, da vi fra et element ikke har nogen reference tilbage i listen. Det er derfor afgørende at vi har fat i det første element, da vi derved får adgang til alle elementerne i listen.
	Vi vil i det følgende gennemgå de konstruktorer og metoder man kan forvente af en collection-klasse.
	2.2.1 Konstruktorerne
	Default-, set- eller copy-konstruktor; hvad får vi brug for?
	En set-konstruktor egner sig ikke godt til en linket liste - vi får ganske enkelt aldrig brug for den - men de to andre er nyttige.
	En default-konstruktor skal initialisere den linkede liste til at være tom. Hvordan ser listen ud når den er tom?
	Her kommer vi til at berøre et spørgsmål der faktisk har to mulige svar - populært sagt er spørgsmålet nemlig: "Skal det være med eller uden dummy?". Hvad er en dummy? Betragt følgende liste; hvor vi har taget List-objektet med:
Figur 2: Linket liste med List-objekt
	Her er det første element i listen markeret, fordi det skal spille en særlig rolle. En særlig rolle lyder måske så lovende, for i virkeligheden er den tiltænkt ingen rolle. Den er der bare! Vi bruger den ikke til at opbevare data i, den skal bare altid være der uanset om der er andre elementer eller ej. Hvorfor?
	Det er et spørgsmål man med rette kan stille, men svaret er ikke helt så enkelt, det skal prøves før man ser det. Med en dummy - som den kaldes - bliver den kode vi skal lave en hel del simplere. Det er ganske enkelt erfaring der har ført til at man bruger den. Umiddelbart skulle man tænke: "Skal jeg nu til at tage hensyn til den dummy?", men i virkeligheden gør det enklere. Vi skal i et senere afsnit i dette kapitel se på implementationen uden en dummy.
	Tilbage til vores oprindelige spørgsmål: Hvordan ser en tom liste ud? Eftersom dummien altid skal være, må en tom liste, være en liste der kun indeholder dummien.
Figur 3: Tom liste med dummy
	Vores default-konstruktor skal initialisere listen til en tom liste:
	class List { private Element first; private int size; public List() { first = new Element( -1 ); size = 0; } ... }
	Vi initialiserer dummien til -1, og vi vil også i andre sammenhænge bruge -1 som ikke-værdi - indikation af at der ikke er nogen værdi/resultat. Det betyder at vi vil holde os til data, der er tallene: 0, 1, 2 ...
	En copy-konstruktor kan, som nævnt, også være nyttig, men en sådan vil vi først lave senere, når vi har fået et bedre kendskab til linkede lister.
	2.2.2 Indsættelse
	Indsættelse er det første vi vil se på. Hvad skal klienten kunne indsætte i forhold til List-objektet? Klienten skal aldrig arbejde direkte på listen inde bag List-objektet. List-objektet tager sig af al arbejdet med listen, og det eneste klienten skal bekymre sig om er data, den ser aldrig nogen elementer. Derfor skal klienten i vores tilfælde kunne indsætte et tal.
	Hvor i listen skal List-objektet indsætte et nyt element med det tal den modtager fra klienten? Der er flere muligheder. Det kunne være i starten af listen eller i slutningen af listen. Derved ville det nye element efter indsættelsen blive det første eller det sidste element i listen. Vi vil lave en metode til hver af de to muligheder.
	2.2.2.1 addFirst
	Den metode der indsætter i starten af listen vil vi kalde addFirst:
	class List { private Element first; private int size; public void addFirst( int data ) { first.next( new Element( data, first.next() ) ); size++; } ... }
	Her sker der flere ting i den første linie af metoden. Det er bekvemt, at man kan skrive hele operationen på en linie, men det kan i starten være svært at overskue hvad der sker, indtil man er fortrolig med notationen. Lad os derfor se den samme linie delt ud på tre linier:
	Element nyt = new Element( data ); nyt.next( first.next() ); first.next( nyt );
	Lad os ligeledes se hvilken tilstand listen har efter hver linie er blevet udført. Vi antager at listen har en række elementer i forvejen: 8, 5 og 2, og at vi har kaldt addFirst med parameteren 4:
Figur 4: Før indsættelse
	Element nyt = new Element( data );
Figur 5: Nyt element instantieres
	nyt.next( first.next() );
Figur 6: Nyt element får kontakt til listen
	first.next( nyt );
Figur 7: Efter indsættelse
	Dette var indsættelse i en liste; hvor der allerede var elementer. Hvad med en tom liste? Fungerer metoden også på en sådan? Det gør den!
	I den situation er first.next() lig null. Og det nye element får derfor selv en next der er null, mens dummien som altid kommer til at kan referere til det nye element
	2.2.2.2 toString
	Indsættelse i slutningen af listen kræver en større indsats end i starten. Det skyldes at vi som udgangspunkt kun har referencen til det første element, og nu skal arbejde os hen i den modsatte ende. Det gør vi ved at gennemløbe listen, ved at følge referencerne fremad i listen.
	Et sådant gennemløb af listen formuleres bedst som en for-løkke [FKJ1]. Et gennemløb, der udskriver listen er et godt eksempel på et sådant gennemløb, og derfor har toString sneget sig ind i dette afsnit, der ellers drejer sig om indsættelse.
	Da klienten vil bruge List-objektets toString har vi valgt kun at returnere selve tallet som tekst fra Elements toString, altså undlade de sædvanlige kantede paranteser. Det har vi gjort for at prioritere læsbarheden af List-objektets toString, da der eller ville komme en umådelig mængde af paranteser. En anden forskel er at List-objektets toString bruger almindelige paranteser i stedet for kantede. Det skyldes at jeg fandt det passende at bruge den samme notation for lister som det klassiske programmeringssprog Lisp, der netop er berømt for sine lister.
	public String toString() { String s="("; for ( Element e=first.next(); e!=null; e=e.next() ) { s += e.toString(); if ( e.next()!=null ) s += " "; } s += ")"; return s; }
	Følgende anvendelse illustrerer listens udseende:
	List vorListe = new Liste(); vorListe.addFirst( 2 ); vorListe.addFirst( 5 ); vorListe.addFirst( 8 ); vorListe.addFirst( 4 ); System.out.println( vorListe ); (4 8 5 2)
	For-løkken er værd at studere nærmere.
	for ( Element e=first.next(); e!=null; e=e.next() ) { ... }
	Det centrale i den er referencen e som gennemløber listen. Den starter med det første element som den får fra dummien. For hver iteration flyttes den ét element fremad i listen, ved at den sættes til next for det element der refererede til. Disse skrift fremad i listen forløber så længe referencen ikke er null. Den bliver null når den henter next fra det sidste element.
	If-sætningen skyldes, at ethvert element i udskriften skal have et mellemrum efter sig, undtagen det sidste, ellers ville vi få følgende fejlslagne udseende:
	(4 8 5 2 )
	2.2.2.3 addLast
	Efter nu at have set på gennemløb er vi nu klar til at implementere en metode der indsætter sidst i listen.
	Vi kan opdele opgaven i to dele. Først skal vi have fat i det sidste element i listen, og dernæst skal vi sætte det nye element efter det. Første del af opgaven er et gennemløb, der stopper ved det sidste element, og anden del er almindelig reference-gymnastik, når vi første er nået dertil.
	Ved gennemløbet af listen skal vi være opmærksom på to ting.
	Først og fremmest skal vi ikke blive ved til vores reference bliver null, for så er vi kommet ét skridt for langt. Kørselsbetingelsen må derfor være at vi kun vil fortsætte, såfremt det element vi har fat i nu ikke er det sidste.
	Den anden ting man skal være opmærksom på er scope for vores reference. For at foretage indsættelse af det nye element må vi også have referencen efter for-løkken - det er netop for-løkkens formål at placere referencen før anden del af opgaven kan løses. Dette problem løses naturligvis ved at erklære referencen før for-løkken.
	Vores gennemløb bliver derfor:
	public void addLast( int data ) { Element e; for ( e=first.next(); e.next()!=null; e=e.next() ) ; e.next( new Element( data ) ); size++; }
	Her afslutter vi med at indsætte det nye element og opdatere size.
	2.2.2.4 addAll
	Nu vil vi implementere indsættelse af ikke blot ét element, men en hel liste. Hvordan vil vi forstå det? Vi vil indsætte den anden liste i slutningen af den første (altså svarende til en concatenering - vedr. betydningen af concatnering, se evt. kapitlet "Tekststrenge" under metoden concat)
	Hvad med elementerne? Vil vi "stjæle" elementerne fra den anden liste og indsætte dem i vores? Nej, vi vil lave vores egne elementer med de samme værdier.
	Metoden kan implementeres vha. addLast, idet vi gennemløber den anden liste fra start til slut og kalder addLast for hvert element i listen:
	public void addAll( List list ) { for ( Element e=list.first.next(); e!=null; e=e.next() ) addLast( e.data() ); }
	Som man ser, lader vi en reference gennemløbe den anden listes elementer.
	Metoden er dundrende ineffektiv (tidskompleksiteten er O(n2)). Hver gang vi rykker et element frem i den anden liste skal addLast genneløbe hele vores liste for at indsætte det nye element sidst i listen. En betydelig mere effektiv metode (med tidskompleksitet O(n)) fås ved hele tiden at have en reference til det sidste element i vores liste, så addLast ikke skal til at lave den hver gang. For at opnå dette må vi selv lave addLasts arbejde:
	public void addAll( List list ) { Element last; for ( last=first; last.next()!=null; last=last.next() ) ; for ( Element e=list.first.next(); e!=null; e=e.next() ) { addLast( e.data() ); last = last.next(); } }
	Her genkender man kode der optræder i addLast. Man bemærker at last må erklæres før den for-løkken, der placerer den på det sidste element, for at den efterfølgende kan anvendes .
	Denne koderedundans kan vi fjerne ved at lave en servicemetode der returnerer en reference til det sidste element
	public void addAll( List list ) { Element last = getLastElement(); for ( Element e=list.first.next(); e!=null; e=e.next() ) { addLast( e.data() ); last = last.next(); } } private Element getLastElement() { Element last; for ( last=first; last.next()!=null; last=last.next() ) ; return last }
	2.2.2.5 Copy-konstruktor
	En anden ting det er muligt at implementere efter vi har introduceret gennemløb af lister, er copy-konstruktoren. Ja, efter at vi har implementeret addAll, behøver vi faktisk ikke at lave kopieringen selv, man kan få metoden til at gøre det på den, som udgangspunkt, tomme liste:
	public List( List list ) { this(); addAll(); }
	Vha. af default-konstruktoren og addAll bliver denne konstruktor uhyre enkel.
	2.2.3 Søgning
	boolean contains( int )
	2.2.4 Get-agtige metoder
	Get-metoder, der ikke er index-orienterede, knytter sig til to positioner i listen - starten og slutningen. Metoderne er ikke videre komplicerede - i særdeleshed ikke getFirst:
	public int getFirst() { if ( first.next() != null ) return first.next().data(); else return -1; }
	getLast løber blot til slutningen af listen:
	public int getLast() { Element e; for ( e=first; e.next()!=null; e=e.next() ) ; return e.data(); }
	Vi udnytter her at dummien har data-værdien -1; hvilket er fuldt legitimt, da den netop har denne værdi for at indikere "ingen værdi".
	Rent æstetisk er der dog en kodemæssig divergens mellem de to metoder. getFirst gør sig en særlig anstrengelse mht. -1 mens getLast får den automatisk af dummien. Det ville være pænere med en service-metode, der gjorde dem mere ensartede:
	private int elementValue( Element e ) { if ( e!=null ) return e.data(); else return -1; }
	Metoden returnerer elementets værdi uanset og det eksisterer eller ej. Hvis det ikke eksisterer, returneres -1 som en indikation af at der ikke er nogen værdi. Med denne servicemetode bliver getFirst enklere (vi har reelt flyttet dens indhold over i servicemetoden) og vi kan se frem til senere, igen at få glæde af servicemetoden:
	public int getFirst() { return elementValue( first.next() ); }
	2.2.5 Sletning
	Den ultimative sletning er naturligvis at slette hele listen:
	public void clear() { first.next( null ); }
	Herefter er samtlige elementer prisgivet garbage collectoren.
	Svarende til de get-agtige metoder og metoderne til indsættelse, relaterer metoderne til sletning af enkelt-elementer sig til starten og slutningen af listen. removeFirst anvender service-metoden ovenfor:
	public int removeFirst() { int value = elementValue( first.next() ); if ( first.next() != null ) first.next( first.next().next() ); return value; }
	------------------
	public int removeLast() { if ( first.next() != null ) { Element e; for ( e=first; e.next().next()!=null; e=e.next() ) ; int value = e.next().data(); e.next( e.next().next() ); else return -1; }
	Vi er her nød til at opdele i to tilfælde, da dummien ikke kan hjælpe os, når vi skal se hele to elementer fremad. At det er nødvendigt at se så langt frem for efterfølgende at kunne foretage sletningen gør sletning til den mest komplicerede enkelt-operation på linkede lister.
	Man bemærker svarende til de get-agtige metoder, at det kun er den af metoderne der arbejder med det første element i listen der har glæde af service-metoden. Den metode der tager sig af det sidste element i listen har derimod nemmest ved selv at løse opgaven, da den ved at der er et sidste element, når den først er begyndt at gennemløbe listen.
	Hvis man sammenligner de to metoder observerer man to redundante linier:
	e.next( e.next().next() ); first.next( first.next().next() );
	Den kan fjernes med en service-metode:
	private void disconnectSuccessor( Element e ) { e.next( e.next().next() ); }
	Der afkobler efterfølgende til det anførte element.
	2.2.6 Index-orienterede metoder
	int get( int index )
	void add( int index, int data )
	int remove( int index )
	2.2.7 Lisp-orienterede metoder
	int car()
	List cdr()
	3. Eksempel: Reverse
	Vi vil i dette afsnit udelukkende se på en enkelt metode til klassen List. Vi vil lave metoden som et eksempel - man laver den normalt ikke i rigtige list-klasser.
	Vi vil konstruere en metode reverse, der vender listen om, så det sidste element bliver det første, og det første det sidst.
	Lad os skitsere et eksempel; hvor en liste bliver reversed.
	Vores udgangspunkt kunne være følgende liste:
	Fig. 19.1. Før Reverse().
	Tallene kunne være andre, men er valgt for at gøre det nemmere at se hvad der sker. Vi ønsker at denne liste ved Reverse() skal blive:
	Fig. 19.2. Efter Reverse().
	Man bemærker at elementerne er de samme, og der er derfor ikke grund til at lave nye, men blot ændre pointerne.
	Hvis vi rent grafisk holder placeringen af elementerne fast fra Fig. 19.1. og flytter pointerne så de svarer til placeringen i Fig. 19.2. giver det et indtryk af hvad det er, der skal ske.
	Fig. 19.3. Efter Reverse(), uden visuelt at flytte elementerne.
	Alle elementer skal altså pege på det foregående, på nær listehovedet og det "nye" sidste element i listen, (1). Rent algoritmisk betyder det, at man skal starte med elementet (1) efter dummy’en og for hvert af de efterfølgende elementer (2, ...) sætte det til at pege på det foregående.
	Hvis vi ser på det første skridt i en sådan algoritme vil listen fra Fig. 19.1. se sådan ud:
	Fig. 19.4. Listen efter "første skridt".
	Det eneste vi har gjort er at flytte pointeren (2)® (3) til (2)® (1).
	Man bemærker at dummy’en stadig peger på (1). Den skal efter reverse() pege på (3), men så langt er vi ikke nået. Af estetiske grunde kan vi derfor sætte den til NULL, indtil videre.
	Ligeledes bemærker man at (1) peger på (2), og dette ikke ændres når vi går videre og ændrer (3) til at pege på (2). I Fig. 19.3. kan vi se, at den efter reverse() skal være NULL, men hvor skal det NULL komme fra. Man kunne selvfølgelig sætte det direkte ind, men rent logisk kunne det komme fra et andet sted. Lad os dog først se på hvordan listen kommer til at se ud efter disse justeringer:
	Fig. 19.5. Listen efter "første skridt" og justeringer.
	Det første man ser er, at der nu er flere stumper der svæver frit. Vi har mistet kontakten til (2) og (3), med andre ord har vi brug for et par hjælpepointere.
	I den forbindelse ser man at (3) så at sige er den eneste tilbage der er ordnet normalt, mens (2) og (1) er reversed. Når vi derfor skal vælge et navn til den hjælpepointer der skal pege på (3) kunne vi f.eks. bruge normal. Tilsvarende vælger vi naturligt nok navnet reversed til den hjælpepointer der skal pege på (2).
	Lad os se hvordan billedet nu ser ud:
	Fig. 19.6. Listen med hjælpepointere.
	Hvis vi "retter det ud" bliver det mere tydeligt hvilken idé der ligger bag denne algoritme.
	Fig. 19.7 De tre dellister.
	Som det er forsøgt angivet med pilen til højre, kommer elementerne til at vandre fra dellisten normal til dellisten reversed, som var der tale om en stack der blev tømt over i en anden stack.
	Det bringer os tilbage til hvor det NULL (1) skal pege på, kan komme fra. Hvis man ser på situationen i starten er reversed tom, og derefter sættes de elementer der føjes til reversed til at pege på det samme som reversed. Det er derfor logisk/praktisk at initialisere reversed til NULL og derefter behandle (1) som ethvert andet element og sætte det til at pege på det samme som reversed, nemlig NULL!
	reversed skulle altså initialiseres til NULL, men hvad med normal. normal må i starten skulle pege på elementet umiddelbart efter dummy’en, da dummy’en ikke skal behandles som de andre, og (1) derfor er det første elementet i den delliste vi vil reverse.
	Det giver os flg. initialiseringer:
	reversed = NULL; normal = Listen->next;
	Hvis vi vender tilbage til Fig. 19.7. begynder vi nu at lede efter en betingelse for gentagelsen af, at flytte et element fra normal til reversed. Naturligt nok kan man blive ved så længe der er flere elementer i normal, og derfor bliver betingelsen:
	(normal!=NULL)
	Dernæst vælger vi en while-løkke for også at kunne behandle den situation hvor Listen er tom (dvs. kun indeholder dummy’en).
	Hvis vi samler det hele, og tilføjer procedure-hoved og erklæring af hjælpepointere får vi:
	void Liste::Reverse() { struct element_t *normal, *reversed; // initialiseringer reversed = NULL; normal = Listen->next; // flytning af elementer while (normal!=NULL) { // flyt et element fra normal til reversed } // sætter listen til resultatet Listen->next = reversed; }
	Til slut er også tilføjet listen->next = normal; . Idéen er at når alle elementerne er flyttet over fra normal til reversed, peger reversed på en tilfredsstillende liste, pånær, at den mangler dummy’en som vi har gemt vha. Listen. Derfor føjes listen reversed til dummy’en.
	Nu mangler kun at udfylde // flyt et element fra normal til reversed. Lad os se på normal (med nogle ekstra elementer, for bedre at kunne illustrere det følgende) og reversed fra Fig. 19.7.
	Fig. 19.8. // flyt et element fra normal til reversed
	De tre pointere der skal flyttes er A® (4), B® (3) og C® (2). Dette giver naturligvis anledning til tre assignments, men det er ikke så ligetil alligevel.
	Problemet ligger i, at vi ikke kan flytte nogen af de tre pointere da de hver for sig er den eneste pointer til det element de peger på. En flytning vil derfor bevirke at et element vil komme til at svæve frit. Det løses naturligvis ved at vi må have endnu en hjælpepointer, lad os kalde den help.
	Vi kunne starte med at sikre kontakten til (4) med help, og flytte C® (2):
	help = normal->next; normal->next = reserved;
	Grafisk vil resultatet bliver:
	Fig. 19.9 Efter help® C og C® (2).
	Man skal så flytte B® (3) og A® (4), altså:
	reserved = normal; normal = help;
	Hvilket grafisk giver flg. resultat:
	Fig. 19.10 Efter B® (3) og A® (4).
	Dermed er alle pointerne flyttet og der er samtidig gjort klar til næste iteration, idet strukturen er den samme som i Fig. 19.8.
	Den endelige procedure bliver:
	void Liste::Reverse() { struct element_t *normal, *reversed, *help; // initialiseringer reversed = NULL; normal = Listen->next; // flytning af elementer while (normal!=NULL) { help = normal->next; normal->next = reversed; reversed = normal; normal = help; } // sætter listen til resultatet Listen->next = reversed; }
	[Tale om at collection-objekter ikke alene indkapsler men også er eksmepel på information hiding, da det også er skjult at det er en linket liste der inde bagved]
	4. Chain of Responsability
	Hidtil har vores perspektiv på elementerne kun i ringe grad været objektorienteret. De har været passive objekter der har holdt data og en reference fremad i listen. Vi har gjort noget ved elementerne - de har intet gjort selv. I dette afsnit vil vi lade elementerne gøre det hele [FKJ2].
	5. Iteratorer
	uddelegere gennemløb af linket liste
	6. Uden dummy
	7. LinkedList
	I praksis laver man aldrig selv en linket liste (og det siger jeg først nu!), man anvender i stedet en generisk collection-klasse LinkedList som findes i Java's util-package.
	Epilog
	Dette kapitel har haft til formål at lære læseren hvordan man laver en linket liste. Derfor er der enkelte ting man i virkeligheden ville lave anderledes. Det vedrører primært indkapslingen og datakernen:
	Indkapslingen
	I kapitlet er datakernen i Element indkapslet med private. Nogen ville måske foretrække at gøre den public for at undgå set-/get-metoderne. Jeg har dog valgt at bibeholde dem private og leve med set-/get-metoderne. Det har jeg gjort af tre grunde. Den første, og vigtigste, er at indoktrinere den studerende til altid at tænke indkapsling frem for alt. Den anden er at set-/get-metoderne reelt kun fylder fire metoder med et indhold på hver én linie; hvilket er udetydeligt i kapitlet. Den tredie er at ineffektiviteten ved den ekstra indirection er uvæsentligt, da kapitlets sigte er pædagogisk og ikke at lave kommerciel kode. I virkeligheden ville man naturligvis gøre dem protected og indkapsle dem i en package som det er gjort med LinkedList i java.util. Jeg har valgt ikke at lægge op til en package, da det vil kræve at læseren forstår hvordan man laver packages og kender protected. Samtidig vil læseren reelt ikke lære mere om linkede lister selvom jeg lavede en package.
	Datakernen
	I virkelighedens verden ville man aldrig drømme om at lave datakernen som andet end en reference af typen Object. Derved bliver den generisk, og man bør aldrig lave én til en speciel datakerne. Man ville slippe for lidt casting, men at udvikle listen vil tage længere tid og muligheden for fejl vil ikke kunne udelukkes (det kan den formodentlig mht. LinkedList).
	Dummy eller ej
	Som nævnt er spørgsmålet om dummy eller ej, noget der kun kan ophidse dummies. Jeg har valgt at starte med en dummy, da det gør koden simplere, idet behandlingen af første element ikke bliver et specialtilfælde, og jeg betragter denne fordel som væsentlig når man skal introducere studerende til noget nyt. Man kunne måske mene at en dummy i sig selv forvirrer eller komplicerer det billede den studerende får af en linket liste, men det er min erfaring at det ikke er nævneværdigt. Jeg inddrager senere i kapitlet implementationen af en linket liste uden dummy, da jeg mener det er en variantion der tjener som et godt eksempel.
	Kode-redundans
	I kapitlet er det praktiseret at fjerne så meget kode-redundans som muligt - nærmest i hysterisk grad. Man vil normalt ikke fjerne ethvert lille spor af kode-redundans, men det er min erfaring, at det giver den studerende en god erfaring med at fjerne redundans der samtidig styrker indlæringen af stoffet, da fjernelse af redundansen kræver en nøjagtig forståelse af hvad der sker.
	Hedder det "linket liste" eller "hægtet liste"?
	Mit personlig standpunkt er, at jeg er fuldstændig ligeglad. Hvad jeg selv kalder den afhænger af vind og vejr. Jeg har valgt at bruge den betegnelse der ligger tættest op af den engelske: "linked list". Det har jeg gjort fordi det er den de studerende vil støde på i andre sammenhænge (f.eks. LinkedList).
fodnoter
1	Jeg fandt i 1995 på denne enkle anvendelse af en for-løkke i stedet for de while-løkker man ellers altid ser i literaturen om linkede lister. Jeg har altid undret mig over at der ikke var andre som gjorde det samme. At bruge en for-løkke er blot at tage konsekvensen af for-løkken som syntaktisk sukker for denne form for while-løkker. For et par år siden fandt jeg så endelig en anden der brugte det samme i sin bog. I skrivende stund kan jeg desværre ikke huske hvilken bog, men jeg vil nævne den her når jeg kommer i tanke om det. Jeg har for øvrigt meget vanskeligt ved at forestille mig at vi skulle være de eneste der har bemærket denne teknik - det er det for enkelt til.
2	Anvendelsen af Chain of Responsability pattern til at implementere en linket liste, hvor elementerne selv løser de opgaver man forventer af en almindelig linket liste, har jeg ikke set andre steder, og jeg formoder idéen er original.
	Følgende er fra et gammel manuskript, som jeg ikke vil slette, før jeg er sikker på, at dele af det ikke kan/skal genbruges (det stammer fra starten af kapitlet om dobbelthægtede lister)
	De enkeltkædede lister, som vi har arbejdet med i det foregående, har alle én ulempe: Man kan kun vandre den ene vej. Når man først har flyttet sin pointer et skridt hen ad listen, kan man ikke komme tilbage igen. I en del sammenhænge ville det være et fordel hvis det var muligt. Hvis hvert element udstyres med en ekstra pointer der peger tilbage til det forrige element, opstår der en dobbeltkædet liste.
	Den sædvanlige orientering i listen, fra "venstre" mod "højre", giver ikke længere nogen mening, da man lige så godt kan vandre den ene vej som den anden. Det er derfor logisk at bruge to pointere til listen. Man tillægger dog alligevel listen en orientering når man skal arbejde med den, men uden en pointer i begge ender ville listen i visse sammenhænge blive besværlig at arbejde med. Ligeledes arbejder man også her med dummies, nu en i hver ende. Vi vil igen arbejde med at data er et tal, af illustrative hensyn. En konkret liste kunne derfor være: