Share
Hva du skal skapeTo av de mest vanlige datastrukturene i datavitenskap er den enkeltstående listen og dobbeltkoblede listen.
Da jeg ble lært disse datastrukturene, spurte jeg mine jevnaldrende for analogier å konseptualisere dem. Det jeg hørte var flere eksempler, for eksempel en liste over dagligvarer og et tog. Disse analogiene, som jeg til slutt lærte, var unøyaktige. En dagligvareliste var mer analog en kø; et tog var mer analogt med en matrise.
Etter hvert som det var mer tid, oppdaget jeg til slutt en analogi som nøyaktig beskrev en enkeltkoblet liste og en dobbeltkoblet liste: en scavenger jakt. Hvis du er nysgjerrig på forholdet mellom en scavengerjakt og en koblet liste, les så nedenfor for svaret!
I datavitenskap er en enkeltlinket liste en datastruktur som har en sekvens av knutte noder. Hver knutepunkt inneholder i sin tur data og en peker, som kan peke til en annen knutepunkt.
Noder av en enkeltkoblet liste ligner veldig på trinn i en scavenger jakt. Hvert trinn inneholder en melding (for eksempel "Du har nådd Frankrike") og pekere til neste trinn (for eksempel "Besøk disse breddegrad og lengdegradskoordinater"). Når vi starter sekvensering disse individuelle trinnene for å danne en sekvens av trinn, oppretter vi en scavenger jakt.
Nå som vi har en konseptuell modell av en enkeltkoblet liste, la oss utforske operasjonene i en enkeltkoblet liste.
Siden en enkeltkoblet liste inneholder noder, som kan være en separat konstruktør fra en enkeltkoblet liste, skisserer vi operasjonene til begge konstruktørene: node og SinglyList.
Accentsconagua
data lagrer en verdi.neste peker til neste knutepunkt i listen._lengde henter antall noder i en liste.hode tilordner en node som leder av en liste.Legg til verdi) legger til en node i en liste.searchNodeAt (stilling) søker etter en node på n-posisjon i vår liste.fjerne (stilling) fjerner en node fra en liste.For implementeringen skal vi først definere en konstruktør som heter node og deretter en konstruktør oppkalt SinglyList.
Hver forekomst av node trenger evnen til å lagre data og evnen til å peke til en annen knutepunkt. For å legge til denne funksjonaliteten, oppretter vi to egenskaper: data og neste, henholdsvis.
funksjonsnode (data) this.data = data; this.next = null;
Deretter må vi definere SinglyList:
funksjon SinglyList () this._length = 0; this.head = null;
Hver forekomst av SinglyList vil ha to egenskaper: _lengde og hode. Den tidligere er tilordnet antall noder i en liste; sistnevnte peker til lederen av listen - noden på forsiden av listen. Siden hver ny forekomst av SinglyList inneholder ikke en node, standardverdien for hode er null og standardverdien for _lengde er 0.
Vi må definere metoder som kan legge til, søke og fjerne en knutepunkt fra en liste. La oss begynne med å legge til en node.
1 av 3: Legg til verdi)
Awesome, la oss nå implementere funksjonaliteten for å legge til noder på en liste.
SinglyList.prototype.add = funksjon (verdi) var node = ny Node (verdi), currentNode = this.head; // Første brukstilstand: En tom liste hvis (! CurrentNode) this.head = node; this._length ++; returknutepunkt; // 2. brukskasse: en ikke-tom liste mens (currentNode.next) currentNode = currentNode.next; currentNode.next = node; this._length ++; returknutepunkt; ;
Å legge til en node i vår liste innebærer mange trinn. La oss starte fra begynnelsen av vår metode. Vi bruker argumentet til Legg til verdi) å opprette en ny forekomst av a node, som er tildelt en navngitt variabel node. Vi erklærer også en variabel som heter currentNode og initialiser den til _hode av vår liste. Hvis det ikke er noen noder i listen, så verdien av hode er null.
Etter dette punktet i koden håndterer vi to brukstilfeller.
Første brukstilfelle vurderer å legge til en node i en tom liste. Hvis hode peker ikke på en node, og tildeler deretter node som leder av listen vår, øke lengden på listen vår, og returner node.
Den andre brukssaken vurderer å legge til en node i en ikke-tom liste. Vi går inn i samtidig som loop, og under hver iterasjon vurderer vi om currentNode.next peker til en annen knutepunkt. (Under den første iterasjonen, currentNode peker alltid på hodet på en liste.)
Hvis svaret er nei, tildeler vi node til currentNode.next og returnere node.
Hvis svaret er ja, går vi inn i legemet samtidig som sløyfe. Innenfor kroppen overfører vi igjen currentNode til currentNode.next. Denne prosessen gjentas til currentNode.next peker ikke lenger på en annen knutepunkt. Med andre ord, currentNode peker til siste knutepunkt i vår liste.
De samtidig som sløyfe Til slutt tildeler vi node til currentNode.next, vi øker _lengde av en, og så kommer vi tilbake node.
2 av 3: searchNodeAt (stilling)
Vi kan nå legge til noder på vår liste, men vi kan ikke søke etter noder på bestemte stillinger i vår liste. La oss legge til denne funksjonaliteten og opprette en metode som heter searchNodeAt (stilling), som aksepterer et argument som heter stilling. Argumentet forventes å være et heltall som indikerer en node på n-posisjon i vår liste.
SinglyList.prototype.searchNodeAt = funksjon (posisjon) var currentNode = this.head, lengde = this.length, count = 1, message = failure: 'Feil: ikke-eksisterende node i denne listen.'; // Første brukstilstand: En ugyldig stilling hvis (lengde === 0 || posisjon < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: en gyldig posisjon mens (telle < position) currentNode = currentNode.next; count++; return currentNode; ;
De hvis setningskontroll for første brukstilfelle: En ugyldig stilling er bestått som et argument.
Hvis indeksen passerte til searchNodeAt (stilling) er gyldig, da kommer vi til den andre brukstilfeller-den samtidig som sløyfe. Under hver iterasjon av samtidig som sløyfe, currentNode-som først peker på hode-er tilordnet til neste knutepunkt i listen. Denne iterasjonen fortsetter til tellingen er lik posisjonen.
Når sløyfen endelig bryter, currentNode returneres.
3 av 3: fjerne (stilling)
Den endelige metoden vi skal opprette, heter fjerne (stilling).
SinglyList.prototype.remove = funksjon (posisjon) var currentNode = this.head, lengde = this._length, count = 0, message = feil: 'Feil: ikke-eksisterende node i denne listen.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // Første brukstilstand: En ugyldig stilling hvis (posisjon < 0 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: den første noden er fjernet hvis (posisjon === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; returner deletedNode; // 3. brukskode: en hvilken som helst annen knutepunkt blir fjernet mens (telle < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Vår implementering av fjerne (stilling) innebærer tre brukstilfeller:
hode av en liste) er gått som et argument.Det første og andre brukssaker er det enkleste å håndtere. Når det gjelder det første scenariet, hvis en liste er tom eller en ikke-eksisterende posisjon er passert, blir en feil kastet.
Den andre brukssaken håndterer fjerningen av den første noden i listen, som også er hode. Hvis dette er tilfelle, skjer følgende logikk:
hode er tilordnet til currentNode.next.deletedNode poeng til currentNode. currentNode er tilordnet til null. _lengde av vår liste av en.deletedNode returneres. Det tredje scenariet er det vanskeligste å forstå. Kompleksiteten stammer fra nødvendigheten av å spore to noder under hver iterasjon av a samtidig som sløyfe. Under hver iterasjon av vår løkke sporer vi både noden før noden skal slettes og noden som skal slettes. Når sløyfen til slutt når noden på stillingen vi vil fjerne, slår sløyfen seg.
På dette punktet holder vi referanser til tre noder: beforeNodeToDelete, nodeToDelete, og deletedNode. Før du sletter nodeToDelete, Vi må tildele verdien av neste til neste verdi av beforeNodeToDelete. Hvis formålet med dette trinnet virker uklart, må du minne deg på at vi har en liste over koblede noder; bare å fjerne en node bryter lenken fra den første noden til listen til den siste noden i listen.
Deretter tildeler vi deletedNode til nodeToDelete. Da setter vi verdien av nodeToDelete til null, redusere lengden på listen med en, og returner deletedNode.
Den komplette implementeringen av listen vår er her:
funksjonsnode (data) this.data = data; this.next = null; funksjon SinglyList () this._length = 0; this.head = null; SinglyList.prototype.add = funksjon (verdi) var node = ny Node (verdi), currentNode = this.head; // Første brukstilstand: En tom liste hvis (! CurrentNode) this.head = node; this._length ++; returknutepunkt; // 2. brukskasse: en ikke-tom liste mens (currentNode.next) currentNode = currentNode.next; currentNode.next = node; this._length ++; returknutepunkt; ; SinglyList.prototype.searchNodeAt = funksjon (posisjon) var currentNode = this.head, lengde = this.length, count = 1, message = failure: 'Feil: ikke-eksisterende node i denne listen.'; // Første brukstilstand: En ugyldig stilling hvis (lengde === 0 || posisjon < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: en gyldig posisjon mens (telle < position) currentNode = currentNode.next; count++; return currentNode; ; SinglyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: den første noden er fjernet hvis (posisjon === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; returner deletedNode; // 3. brukskode: en hvilken som helst annen knutepunkt blir fjernet mens (telle < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Fantastisk, vår implementering av en enkeltlinket liste er fullført. Vi kan nå bruke en datastruktur som legger til, fjerner og søker noder i en liste som opptar ikke-sammenhengende plass i minnet.
Men i øyeblikket begynner alle våre operasjoner fra begynnelsen av en liste og går til slutten av en liste. Med andre ord, de er uni-directional.
Det kan være tilfeller hvor vi vil at vår virksomhet skal være toveis. Hvis du vurderte dette brukstilfellet, har du nettopp beskrevet en dobbeltkoblet liste.
En dobbeltkoblet liste tar all funksjonaliteten til en enkeltkoblet liste og strekker den for toveisbevegelse i en liste. Vi kan krysse, med andre ord en koblet liste fra den første noden i listen til siste node i listen; og vi kan krysse fra den siste noden i listen til den første noden i listen.
I denne delen vil vi opprettholde vårt fokus først og fremst på forskjellene mellom en dobbeltkoblet liste og en enkeltkoblet liste.
Vår liste vil inneholde to konstruktører: node og DoublyList. La oss skissere deres operasjoner.
data lagrer en verdi.neste peker til neste knutepunkt i listen.tidligere peker til forrige node i listen._lengde henter antall noder i en liste.hode tilordner en node som leder av en liste.hale tilordner en node som halen på en liste.Legg til verdi) legger til en node i en liste.searchNodeAt (stilling) søker etter en node på n-posisjon i vår liste.fjerne (stilling) fjerner en node fra en liste.La oss skrive noen kode!
For implementeringen skal vi opprette en konstruktør som heter node:
funksjonsknute (verdi) this.data = value; this.previous = null; this.next = null;
For å opprette toveisbevegelsen til en dobbeltkoblet liste, trenger vi egenskaper som peker i begge retninger av en liste. Disse egenskapene er oppkalt tidligere og neste.
Deretter må vi implementere en DoublyList og legg til tre egenskaper: _lengde, hode, og hale. I motsetning til en enkeltlinket liste, har en dobbeltkoblet liste en referanse til både begynnelsen på en liste og enden av en liste. Siden hver forekomst av a DoublyList er instantiated uten noder, standardverdiene for hode og hale er satt til null.
funksjon DoublyList () this._length = 0; this.head = null; this.tail = null;
Vi vil nå utforske følgende metoder: Legg til verdi), fjerne (stilling), og searchNodeAt (stilling). Alle disse metodene ble brukt til en enkeltkoblet liste; De må imidlertid omskrives for toveisbevegelser.
1 av 3: Legg til verdi)
DoublyList.prototype.add = funksjon (verdi) var node = ny Node (verdi); hvis (this.length) this.tail.next = node; node.previous = this.tail; this.tail = node; ellers this.head = node; this.tail = node; this.length ++; returknutepunkt; ;
I denne metoden har vi to scenarier. Først, hvis en liste er tom, så tilordnes den til hode og hale noden blir lagt til. For det andre, hvis listen inneholder noder, så finn halen på listen og tilordne til tail.next noden blir lagt til; På samme måte må vi konfigurere den nye halen for toveisbevegelse. Vi må sette med andre ord, tail.previous til den opprinnelige halen.
2 av 3: searchNodeAt (stilling)
Gjennomføringen av searchNodeAt (stilling) er identisk med en enkeltkoblet liste. Hvis du har glemt hvordan du implementerer den, har jeg tatt med den nedenfor:
DoublyList.prototype.searchNodeAt = funksjon (posisjon) var currentNode = this.head, lengde = this.length, count = 1, message = failure: 'Feil: ikke-eksisterende node i denne listen.'; // Første brukstilstand: En ugyldig stilling hvis (lengde === 0 || posisjon < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: en gyldig posisjon mens (telle < position) currentNode = currentNode.next; count++; return currentNode; ;
3 av 3: fjerne (stilling)
Denne metoden vil være den mest utfordrende å forstå. Jeg vil vise koden og deretter forklare den.
DoublyList.prototype.remove = funksjon (posisjon) var currentNode = this.head, lengde = this.length, count = 1, message = failure: 'Feil: ikke-eksisterende node i denne listen.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // Første brukstilstand: En ugyldig stilling hvis (lengde === 0 || posisjon < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: den første noden er fjernet hvis (posisjon === 1) this.head = currentNode.next; // 2. brukskasse: det er en andre node hvis (! This.head) this.head.previous = null; // 2. brukskasse: det er ingen andre node annet this.tail = null; // 3. brukskasse: den siste noden er fjernet annet hvis (posisjon === this.length) this.tail = this.tail.previous; this.tail.next = null; // Fjerde brukstilstand: En mellomnode er fjernet ellers mens (telle < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
fjerne (stilling) håndterer fire brukstilfeller:
fjerne (stilling) er ikke-eksisterende. I dette tilfellet kaster vi en feil. fjerne (stilling) er den første noden (hode) av en liste. Hvis dette er tilfelle, vil vi tildele deletedNode til hode og deretter tilordne hode til neste knutepunkt i listen. For øyeblikket må vi vurdere om listen vår har mer enn én node. Hvis svaret er nei, hode vil bli tildelt til null og vi kommer inn i hvis en del av vår if-else uttalelse. I kroppen av hvis, vi må også sette hale til null-med andre ord, vi går tilbake til den opprinnelige tilstanden til en tom dobbeltkoblet liste. Hvis vi fjerner den første noden i en liste og vi har mer enn én node i vår liste, skriver vi inn ellers delen av vår if-else uttalelse. I dette tilfellet må vi riktig sette inn tidligere tilhører hode til null-det er ingen noder før hodet på en liste. fjerne (stilling) er halen av en liste. Først, deletedNode er tildelt til hale. Sekund, hale er tilordnet til noden tidligere til halen. For det tredje har den nye halen ingen node etter den og trenger verdien av neste å bli satt til null. samtidig som loop en gang currentNode peker til noden på stillingen som blir sendt som argument til fjerne (stilling). I øyeblikket overfører vi verdien av beforeNodeToDelete.next til noden etter nodeToDelete og omvendt overfører vi verdien av afterNodeToDelete.previous til noden før nodeToDelete. Med andre ord fjerner vi pekere til den fjernede noden og overfører dem til de riktige noderne. Deretter tildeler vi deletedNode til nodeToDelete. Til slutt tildeler vi nodeToDelete til null. Endelig reduserer vi lengden på vår liste og returnerer deletedNode.
Her er hele implementeringen:
funksjonsknute (verdi) this.data = value; this.previous = null; this.next = null; funksjonen DoublyList () this._length = 0; this.head = null; this.tail = null; DoublyList.prototype.add = funksjon (verdi) var node = ny Node (verdi); hvis (this.length) this.tail.next = node; node.previous = this.tail; this.tail = node; ellers this.head = node; this.tail = node; this.length ++; returknutepunkt; ; DoublyList.prototype.searchNodeAt = funksjon (posisjon) var currentNode = this.head, lengde = this.length, count = 1, message = failure: 'Feil: ikke-eksisterende node i denne listen.'; // Første brukstilstand: En ugyldig stilling hvis (lengde === 0 || posisjon < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: en gyldig posisjon mens (telle < position) currentNode = currentNode.next; count++; return currentNode; ; DoublyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > lengde) kaste ny feil (message.failure); // 2. brukskasse: den første noden er fjernet hvis (posisjon === 1) this.head = currentNode.next; // 2. brukskasse: det er en andre node hvis (! This.head) this.head.previous = null; // 2. brukskasse: det er ingen andre node annet this.tail = null; // 3. brukskasse: den siste noden er fjernet annet hvis (posisjon === this.length) this.tail = this.tail.previous; this.tail.next = null; // Fjerde brukstilstand: En mellomnode er fjernet ellers mens (telle < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
Vi har dekket mye informasjon i denne artikkelen. Hvis noe av det virker forvirrende, les det igjen, og eksperimenter med koden. Når det til slutt gir mening, føler du deg stolt. Du har nettopp avdekket mysteriene til både en enkeltlinket liste og en dobbeltkoblet liste. Du kan legge til disse datastrukturene til kodingsverktøyet ditt!
