Share
Den første datastrukturen vi skal se på, er den koblede listen, og med god grunn. Foruten å være en nesten allestedsnærværende struktur som brukes i alt fra operativsystemer til videospill, er det også en byggestein som mange andre datastrukturer kan skape.
I en meget generell forstand er formålet med en koblet liste å gi en konsistent mekanisme for å lagre og få tilgang til en vilkårlig mengde data. Som navnet tilsier, gjør det ved å koble dataene sammen til en liste.
Før vi dykker inn i hva dette betyr, la oss begynne med å se på hvordan data lagres i en matrise.
Heltalldata lagret i en matrise Som figuren viser, lagres arraydata som en enkelt tilordnet allokert bit av minne som er logisk segmentert. Dataene som er lagret i arrayet, er plassert i ett av disse segmentene og referert til via plasseringen eller indeksen i arrayet.
Dette er en god måte å lagre data på. De fleste programmeringsspråk gjør det veldig enkelt å tildele arrays og operere på innholdet. Kontinuerlig datalagring gir ytelsesfordeler (nemlig datalokalitet), iterering over dataene er enkel, og dataene kan nås direkte av indeksen (tilfeldig tilgang) i konstant tid.
Det er imidlertid tid, når en matrise ikke er den ideelle løsningen.
Vurder et program med følgende krav:
Accentsconagua
NextValue metode) til nummer 0xFFFF oppstår.ProcessItems metode.Siden kravene angir at flere verdier må sendes til ProcessItems metode i en enkelt samtale, ville en åpenbar løsning innebære å bruke en rekke heltal. For eksempel:
void LoadData () // Anta at 20 er nok til å holde verdiene. int [] verdier = ny int [20]; for (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Denne løsningen har flere problemer, men den mest skarpe ses når mer enn 20 verdier blir lest. Som programmet er nå ignoreres verdiene fra 21 til n. Dette kan reduseres ved å tildele mer enn 20 verdier, kanskje 200 eller 2000. Kanskje størrelsen kan konfigureres av brukeren, eller om arrayet ble fullt, kan et større utvalg tildeles og alle eksisterende data kopieres inn i den. Til slutt oppretter disse løsningene kompleksitet og avfallshukommelse.
Det vi trenger er en samling som lar oss legge til et vilkårlig antall integerverdier og deretter oppregne over de heltallene i den rekkefølgen de ble lagt til. Samlingen bør ikke ha en fast maksimal størrelse og det er ikke nødvendig med tilfeldig tilgangsindeksering. Det vi trenger er en koblet liste.
Før vi fortsetter og lærer hvordan den tilknyttede listedatastrukturen er utformet og implementert, la oss forhåndsvise hva vår ultimate løsning kan se ut.
statisk tomrom LoadItems () LinkedList list = new LinkedList (); mens (sant) int value = NextValue (); hvis (verdi! = 0xFFFF) list.Add (verdi); annet break; ProcessItems (liste); statisk tomt ProcessItems (LinkedList-liste) // ... Prosessdata.
Legg merke til at alle problemene med array-løsningen ikke lenger eksisterer. Det er ikke lenger noen problemer med at arrayet ikke er stort nok eller tildeler mer enn det er nødvendig.
Du bør også legge merke til at denne løsningen informerer noen av designbeslutningene vi skal gjøre senere, nemlig at Linked klassen aksepterer et generisk type argument og implementerer IEnumerable grensesnitt.
Kjernen i den lenke listen er datastrukturen i Node-klassen. En node er en beholder som gir muligheten til både å lagre data og koble til andre noder.
En koblet listekode inneholder data og en egenskap som peker til neste knutepunkt I sin enkleste form kan en nodeklasse som inneholder heltall se slik ut:
offentlig klasse Node public int Value get; sett; offentlig node neste get; sett;
Med dette kan vi nå lage en veldig primitiv koblet liste. I det følgende eksemplet vil vi allokere tre noder (første, mellom og siste) og deretter koble dem sammen til en liste.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Knutep. først = nytt Knutepunkt Verdi = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Knutepunkt midt = nytt Knutepunkt Verdi = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Knutepunkt siste = nytt Node Value = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = siste;
Vi har nå en koblet liste som starter med noden først og slutter med noden siste. De neste Egenskapen for den siste noden peker til null som er slutten av listen indikatoren. Gitt denne listen, kan vi utføre noen grunnleggende operasjoner. For eksempel er verdien av hver knutepunkt Data eiendom:
privat statisk tomrom PrintList (Node node) mens (node! = null) Console.WriteLine (node.Value); node = node.Next;
De PrintList Metoden virker ved å iterere over hver knutepunkt i listen, skrive ut verdien til gjeldende knutepunkt, og deretter flytte videre til noden pekt av neste eiendom.
Nå som vi har en forståelse av hva en koblet listekode kan se ut, la oss se på selve LinkedListNode klasse.
offentlig klasse LinkedListNode /// /// Konstruerer en ny node med den angitte verdien. /// offentlig LinkedListNode (T-verdi) Value = value; /// /// Nodeverdien. /// offentlig T verdi get; intern sett; /// /// Den neste noden i den koblede listen (null hvis siste node). /// offentlig LinkedListNode Neste get; intern sett;
Før du implementerer vår Linked klasse, må vi tenke på hva vi ønsker å kunne gjøre med listen.
Tidligere så vi at samlingen må støtte sterkt skrevet data, slik at vi vet at vi vil skape et generisk grensesnitt.
Siden vi bruker .NET-rammen for å implementere listen, er det fornuftig at vi vil at denne klassen skal kunne virke som de andre innebygde samlingstypene. Den enkleste måten å gjøre dette på er å implementere ICollection grensesnitt. Legg merke til jeg velger ICollection og ikke IList. Dette skyldes at IList grensesnitt gir mulighet til å få tilgang til verdier etter indeks. Mens direkte indeksering er generelt nyttig, kan den ikke implementeres effektivt i en koblet liste.
Med disse kravene i tankene kan vi lage en grunnklassestub, og deretter gjennom resten av delen kan vi fylle ut disse metodene.
offentlig klasse LinkedList: System.Collections.Generic.ICollection public void Add (T element) kaste nytt System.NotImplementedException (); offentlig tomretting Clear () kaste nytt system.NotImplementedException (); offentlig bool Inneholder (T-element) kaste nytt System.NotImplementedException (); offentlig tomt CopyTo (T [] array, int arrayIndex) kaste nytt System.NotImplementedException (); offentlig int count get; privat sett; offentlig bool IsReadOnly få kaste nytt system.NotImplementedException (); offentlig bool Fjern (T element) kaste nytt system.NotImplementedException (); offentlige System.Collections.Generic.IEnumerator GetEnumerator () kaste nytt system.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () kaste nytt system.NotImplementedException ();
| Oppførsel | Legger til den angitte verdien til slutten av den koblede listen. |
| Opptreden | O (1) |
Legge til et element i en koblet liste innebærer tre trinn:
LinkedListNode forekomst.neste Egenskapen til den siste noden til den nye noden.Nøkkelen er å vite hvilken node som er den siste noden i listen. Det er to måter vi kan vite dette. Den første måten er å holde oversikt over den første noden ("hodet" node) og gå til listen til vi har funnet den siste noden. Denne tilnærmingen krever ikke at vi holder oversikt over den siste noden, noe som sparer en referanseverdi til minne (uansett hvilken plattformspekerstørrelse er), men krever at vi utfører en oversikt over listen hver gang en nod legges til. Dette ville gjøre Legg til en O (n) operasjon.
Den andre tilnærmingen krever at vi holder oversikt over den siste noden ("halen" node) i listen, og når vi legger til den nye noden, åpner vi bare vår lagrede referanse direkte. Dette er en O (1) algoritme og derfor den foretrukne tilnærmingen.
Det første vi må gjøre er å legge til to private felt til Linked klasse: referanser til de første (hode) og siste (hale) noder.
privat LinkedListNode _head; privat LinkedListNode _tail;
Deretter må vi legge til metoden som utfører de tre trinnene.
offentlig tomrom Legg til (T-verdi) LinkedListNode node = ny LinkedListNode (verdi); hvis (_head == null) _head = node; _tail = node; ellers _tail.Next = node; _tail = node; Count ++;
Først allokerer den den nye LinkedListNode forekomst. Deretter sjekker det om listen er tom. Hvis listen er tom, legges den nye noden enkelt ved å tilordne _hode og _hale referanser til den nye noden. Den nye noden er nå både den første og siste noden i listen. Hvis listen ikke er tom, legges noden til slutten av listen og _hale referansen er oppdatert for å peke til den nye enden av listen.
De Telle Egenskapen økes når en knute er lagt til for å sikre ICollection. Telle eiendom returnerer den nøyaktige verdien.
| Oppførsel | Fjerner den første noden i listen hvis verdi er lik den angitte verdien. Metoden returnerer sann hvis en verdi ble fjernet. Ellers returnerer den falsk. |
| Opptreden | På) |
Før du snakker om Fjerne algoritme, la oss ta en titt på hva den prøver å oppnå. I den følgende figuren er det fire noder i en liste. Vi vil fjerne noden med verdien tre.
En koblet liste med fire verdier Når fjerningen er ferdig, vil listen bli endret slik at neste Egenskapen på noden med verdien to peker til noden med verdien fire.
Den koblede listen med 3 noden ble fjernet Den grunnleggende algoritmen for fjerning av knutepunkter er:
Som alltid er djevelen i detaljene. Det er noen få tilfeller vi må tenke på når du fjerner en knutepunkt:
_hode og _hale felt til null._hode feltet for å peke på den nye hodetelefonen._hale feltet for å referere til den nestledende noden i listen og angi dens neste eiendom til null.offentlig bool Fjern (T-punkt) LinkedListNode forrige = null; LinkedListNode current = _head; // 1: Tom liste: Gjør ingenting. // 2: Enkeltknutepunkt: Forrige er null. // 3: Mange noder: // a: Node å fjerne er den første noden. // b: Noden som skal fjernes er midten eller sist. mens (nåværende! = null) if (current.Value.Equals (item)) // Det er en node i midten eller slutten. hvis (forrige! = null) // sak 3b. // Før: Head -> 3 -> 5 -> null // Etter: Head -> 3 ------> null previous.Next = current.Next; // Det var slutten, så oppdater _tail. hvis (nåværende.Neste == null) _tail = forrige; annet // sak 2 eller 3a. // Før: Head -> 3 -> 5 // Etter: Head ------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; // Er listen nå tom? hvis (_head == null) _tail = null; Telle--; returnere sant; forrige = nåværende; nåværende = nåværende.Neste; returner falsk;
De Telle Egenskapen blir redusert når en knute er fjernet for å sikre ICollection. Telle eiendom returnerer den nøyaktige verdien.
| Oppførsel | Returnerer en boolsk som angir om den angitte verdien finnes i den koblede listen. |
| Opptreden | På) |
De inneholder metoden er ganske enkel. Det ser på hver knute i listen, fra første til siste, og returnerer sant så snart en knutepunkt som matcher parameteren, er funnet. Hvis slutten av listen er nådd og noden ikke er funnet, returnerer metoden falsk.
offentlig bool Inneholder (T-punkt) LinkedListNode current = _head; mens (nåværende! = null) if (current.Value.Equals (item)) return true; nåværende = nåværende.Neste; returner falsk;
| Oppførsel | Returnerer en IEnumerator-forekomst som tillater oppføring av de tilknyttede listeværdiene fra første til siste. |
| Opptreden | Å returnere opptellingene er en O (1) operasjon. Oppsummering av hvert element er en O (n) -operasjon. |
GetEnumerator implementeres ved å oppregne listen fra første til siste knutepunkt og bruker C # utbytte søkeord for å returnere gjeldende nodes verdi til den som ringer.
Legg merke til at LinkedList implementerer iterasjonsadferdene i IEnumerable versjon av GetEnumerator-metoden og forsvarer denne virkemåten i den IEnumerable versjonen.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; mens (nåværende! = null) return return current.Value; nåværende = nåværende.Neste; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Oppførsel | Fjerner alle elementene fra listen. |
| Opptreden | O (1) |
De Klar Metoden setter bare _hode og _hale feltene null for å slette listen. Fordi .NET er et søppel samlet språk, trenger ikke nodene eksplisitt fjernet. Det er ansvaret til den som ringer, ikke den tilknyttede listen, for å sikre at hvis nodene inneholder IDisposable referanser de er riktig bortskaffet.
offentlig tomretting Clear () _head = null; _tail = null; Count = 0;
| Oppførsel | Kopier innholdet i den lenke listen fra start til slutt til det angitte feltet, som starter ved den angitte arrayindeksen. |
| Opptreden | På) |
De Kopier til Metoden rettes ganske enkelt over listepostene og bruker enkel oppgave til å kopiere elementene til matrisen. Det er oppringerens ansvar å sikre at målgruppen inneholder riktig ledig plass for å imøtekomme alle elementene i listen.
offentlig tomt CopyTo (T [] array, int arrayIndex) LinkedListNode current = _head; mens (nåværende! = null) array [arrayIndex ++] = current.Value; nåværende = nåværende.Neste;
| Oppførsel | Returnerer et heltall som angir antall elementer som er i listen. Når listen er tom, er verdien returnert 0. |
| Opptreden | O (1) |
Telle er rett og slett en automatisk implementert eiendom med en offentlig getter og privat setter. Den virkelige oppførselen skjer i Legg til, Fjerne, og Klar fremgangsmåter.
offentlig inntekt get; privat sett;
| Oppførsel | Returnerer falsk hvis listen ikke er skrivebeskyttet. |
| Opptreden | O (1) |
offentlig bool IsReadOnly get return false;
Den LinkedList-klassen vi nettopp har opprettet, er kjent som en enkelt, koblet liste. Dette betyr at det bare finnes en enkelt, ensrettet kobling mellom en node og den neste noden i listen. Det er en vanlig variant av den koblede listen som gjør det mulig for den som ringer til å få tilgang til listen fra begge ender. Denne varianten er kjent som en dobbeltkoblet liste.
For å opprette en dobbeltkoblet liste må vi først endre vår LinkedListNode-klasse for å få en ny eiendom med navnet Forrige. Forrige vil fungere som Neste, vil det bare peke på forrige node i listen.
En dobbeltkoblet liste ved hjelp av en Previous node-egenskap Følgende avsnitt beskriver bare endringene mellom den enkeltkoblede listen og den nye dobbeltkoblede listen.
Den eneste endringen som vil bli gjort i LinkedListNode Klassen er tillegg av en ny eiendom som heter Tidligere som peker til forrige LinkedListNode i den koblede listen, eller returnerer null hvis det er den første noden i listen.
offentlig klasse LinkedListNode /// /// Konstruerer en ny node med den angitte verdien. /// /// offentlig LinkedListNode (T-verdi) Value = value; /// /// Nodeverdien. /// offentlig T verdi get; intern sett; /// /// Den neste noden i den koblede listen (null hvis siste node). /// offentlig LinkedListNode Neste get; intern sett; /// /// Den forrige noden i den koblede listen (null hvis første node). /// offentlig LinkedListNode Forrige get; intern sett;
Mens den enkeltkoblede listen bare lagde nodene til slutten av listen, vil den dobbeltkoblede listen tillate å legge til noder til start og slutt på listen ved å bruke AddFirst og AddLast, henholdsvis. De ICollection. Legg til metode vil utsette til AddLast metode for å beholde kompatibilitet med det enkeltstående Liste klasse.
| Oppførsel | Legger til den angitte verdien på forsiden av listen. |
| Opptreden | O (1) |
Når du legger til en node på forsiden av listen, er handlingene veldig likt å legge til en enkelt tilknyttet liste.
neste Egenskapen til den nye noden til den gamle hodetelefonen.Tidligere Egenskapen til den gamle hodetelefonen til den nye noden._hale felt (om nødvendig) og økning Telle.Offentlig tomt AddFirst (T-verdi) LinkedListNode node = ny LinkedListNode (verdi); // Lagre hovednoden slik at vi ikke mister den. LinkedListNode temp = _head; // Punkthodet til den nye noden. _head = node; // Sett inn resten av listen bak hodet. _head.Next = temp; hvis (Count == 0) // Hvis listen var tom, så hodet og halen skal // begge peker på den nye noden. _tail = _head; ellers // Før: hode -------> 5 <-> 7 -> null // Etter: hode -> 3 <-> 5 <-> 7 -> null temp. Tidligere = _head; Count ++;
| Oppførsel | Legger til den angitte verdien til slutten av listen. |
| Opptreden | O (1) |
Å legge til en node til slutten av listen er enda enklere enn å legge til en til begynnelsen.
Den nye noden er ganske enkelt lagt til slutten av listen, oppdaterer tilstanden til _hale og _hode etter behov, og Telle økes.
offentlig tomrom AddLast (T-verdi) LinkedListNode node = ny LinkedListNode (verdi); hvis (Count == 0) _head = node; ellers _tail.Next = node; // Før: Hodet -> 3 <-> 5 -> null // Etter: Hodet -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = node; Teller ++;
Og som nevnt tidligere, ICollection.Legg til vil nå bare ringe AddLast.
offentlig tomrom Legg til (T-verdi) AddLast (verdi);
Som Legg til, de Fjerne Metoden vil bli utvidet til å støtte fjerning av noder fra starten eller slutten av listen. De ICollection.Fjern metode vil fortsette å fjerne elementer fra starten med den eneste forandringen er å oppdatere det aktuelle Tidligere eiendom.
| Oppførsel | Fjerner den første verdien fra listen. Hvis listen er tom, blir ingen handling tatt. Returnerer sant hvis en verdi ble fjernet. Ellers returnerer den falsk. |
| Opptreden | O (1) |
RemoveFirst oppdaterer listen ved å angi den koblede listen hode eiendom til den andre noden i listen og oppdatere dens Tidligere eiendom til null. Dette fjerner alle referanser til forrige hodetelefon, fjerner det fra listen. Hvis listen bare inneholdt en singleton, eller var tom, vil listen være tom ( hode og hale egenskaper vil være null).
offentlig ugyldig RemoveFirst () if (Count! = 0) // Før: Head -> 3 <-> 5 // Etter: Head -------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; Telle--; hvis (Count == 0) _tail = null; ellers // 5. Tidligere var 3; nå er det null. _head.Previous = null;
| Oppførsel | Fjerner den siste noden fra listen. Hvis listen er tom, utføres ingen handling. Returnerer sant hvis en verdi ble fjernet. Ellers returnerer den falsk. |
| Opptreden | O (1) |
RemoveLast fungerer ved å sette listen hale Egenskapen til å være noden som går foran dagens haleknutepunkt. Dette fjerner den siste noden fra listen. Hvis listen var tom eller bare hadde en node, når metoden returnerer hode og hale egenskaper, de vil begge være null.
Offentlig tomt FjernLast () hvis Count! = 0) hvis (Count == 1) _head = null; _tail = null; annet // før: hode -> 3 -> 5 -> 7 // hale = 7 // etter: hode -> 3 -> 5 -> null // hale = 5 // null ut 5 s neste eiendom. _tail.Previous.Next = null; _tail = _tail.Forrige; Telle--;
| Oppførsel | Fjerner den første noden i listen hvis verdi er lik den angitte verdien. Metoden returnerer sann hvis en verdi ble fjernet. Ellers returnerer den falsk. |
| Opptreden | På) |
De ICollection. Fjerne Metoden er nesten identisk med den enkeltkoblede versjonen bortsett fra at Tidligere Eiendommen er nå oppdatert under fjerningsoperasjonen. For å unngå gjentatt kode, ringer metoden RemoveFirst når det er bestemt at noden blir fjernet, er den første noden i listen.
offentlig bool Fjern (T-punkt) LinkedListNode forrige = null; LinkedListNode current = _head; // 1: Tom liste: Gjør ingenting. // 2: Enkeltknutepunkt: Forrige er null. // 3: Mange noder: // a: Node å fjerne er den første noden. // b: Noden som skal fjernes er midten eller sist. mens (nåværende! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals ) // Det er en node i midten eller slutten. hvis (forrige! = null) // sak 3b. forrige.Neste = nåværende.Neste; // Det var slutten, så oppdater _tail. hvis (nåværende.Neste == null) _tail = forrige; ellers // Før: Hodet -> 3 <-> 5 <-> 7 -> null // Etter: Hodet -> 3 <-------> 7 -> null // forrige = 3 // nåværende = 5 // nåværende.Neste = 7 // Så ... 7.Forrige = 3 nåværende.Neste.Forrige = forrige; Telle--; annet // sak 2 eller 3a. RemoveFirst (); returnere sann; forrige = nåværende; nåværende = nåværende.Neste; returner falsk;
Vi kan legge til noder på forsiden og slutten av listen - så hva? Hvorfor bryr vi oss? Som det står akkurat nå, den dobbeltkoblede Liste klassen er ikke mer kraftig enn den enkeltkoblede listen. Men med bare en liten modifikasjon, kan vi åpne opp alle slags mulige oppføringer. Ved å utsette hode og hale Egenskaper som skrivebeskyttede offentlige eiendommer, vil den forbundne listen forbruker kunne implementere alle former for ny oppførsel.
offentlig LinkedListNode Head get return _head; offentlig LinkedListNode Tail get return _tail;
Med denne enkle endringen kan vi oppsummere listen manuelt, noe som gjør at vi kan utføre omvendt (hale til hode) opptelling og søk.
For eksempel viser følgende kodeeksempel hvordan du bruker listen Hale og Tidligere Egenskaper for å oppregne listen i revers og utføre en del behandling på hver knute.
Offentlig tomgang ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (liste); LinkedListNode current = list.Tail; mens (nåværende! = null) ProcessNode (nåværende); nåværende = nåværende
I tillegg er det dobbeltkoblet Liste klassen tillater oss å enkelt lage Deque klassen, som selv er en byggestein for andre klasser. Vi vil diskutere denne klassen senere i en annen seksjon.
