Tietorakenteet ja algoritmit Javassa, osa 4: Yksin linkitetyt luettelot

Kuten taulukot, jotka otettiin käyttöön tämän opetusohjelman osassa 3, linkitetyt luettelot ovat perustietorakenne, johon monimutkaisemmat tietorakenteet voivat perustua. Toisin kuin alkioiden sarja, a linkitetty luettelo on solmujen sarja, jossa kukin solmu on linkitetty sarjan edelliseen ja seuraavaan solmuun. Muista, että a solmu on objekti, joka on luotu itseviittausluokasta, ja a itseviittausluokka on vähintään yksi kenttä, jonka viittaustyyppi on luokan nimi. Linkitetyn luettelon solmut linkitetään solmuviitteen avulla. Tässä on esimerkki:

 luokka Työntekijä {private int empno; yksityinen merkkijono nimi; yksityinen kaksinkertainen palkka; julkinen työntekijä seuraavaksi; // Muut jäsenet. }

Tässä esimerkissä Työntekijä on itseviittausluokka, koska se Seuraava kentällä on tyyppi Työntekijä. Tämä kenttä on esimerkki a linkkikenttä koska se voi tallentaa viitteen luokan toiseen esineeseen - tässä tapauksessa toiseen Työntekijä esine.

Tämä opetusohjelma esittelee Java-ohjelmoinnin yksitellen linkitettyjen luetteloiden sisäpiirit. Opit yksittäisen linkitetyn luettelon luomisen, solmujen lisäämisen yksitellen linkitettyyn luetteloon, solmujen poistamisen yksitellen linkitetystä luettelosta, yhdistämisen yksittäisesti linkitetyn luettelon toiseen yksin linkitettyyn luetteloon ja kääntämisen yksittäin linkitetyn luettelon kääntämiseksi. Tutkimme myös algoritmeja, joita yleisimmin käytetään yksin linkitettyjen luetteloiden lajittelussa, ja lopuksi esimerkillä, joka osoittaa lisäyslajittelualgoritmin.

lataa Hanki koodi Lataa tämän artikkelin kolme esimerkkisovellusta. Luonut Jeff Friesen JavaWorldille.

Mikä on yksittäisesti linkitetty luettelo?

A linkitetty luettelo on linkitetty luettelo solmuista, joissa jokaisella solmulla on yksi linkkikenttä. Tässä tietorakenteessa viitemuuttuja sisältää viittauksen ensimmäiseen (tai ylimpään) solmuun; kukin solmu (paitsi viimeinen tai alin solmu) linkittää seuraavaan; ja viimeisen solmun linkkikenttä sisältää nollaviitteen, joka merkitsee luettelon loppua. Vaikka viitemuuttuja on yleisesti nimetty alkuun, voit valita haluamasi nimen.

Kuvassa 1 on yksi linkitetty luettelo, jossa on kolme solmua.

Alla on pseudokoodi yksittäisesti linkitetylle luettelolle.

 ILMOITA LUOKASolmu ILMOITA STRING-nimi ILMOITA Solmu seuraava LOPETA ILMOITA ILMOITA Solmu alkuun = NULL

Solmu on itseviittausluokka, jolla on a nimi tietokenttä ja a Seuraava linkkikenttä. alkuun on tyypin viitemuuttuja Solmu siinä on viittaus ensimmäiseen Solmu objekti linkitetyssä luettelossa. Koska luetteloa ei ole vielä olemassa, alkuunalkuperäinen arvo on TYHJÄ.

Yksin linkitetyn luettelon luominen Java-sovelluksessa

Voit luoda yhden linkitetyn luettelon liittämällä siihen yhden Solmu esine. Seuraava pseudokoodi luo a Solmu objektin, määrittää sen viitteen alkuun, alustaa tietokentän ja määrittää TYHJÄ linkkikenttään:

 top = UUSI Solmu top.name = "A" top.next = NULL

Kuvassa 2 on esitetty ensimmäinen pseudokoodista syntyvä yksittäisesti linkitetty luettelo.

Tämän operaation aikakompleksi on O (1) - vakio. Muista, että O (1) lausutaan "Big Oh of 1". (Katso osasta 1 muistutus siitä, kuinka ajan ja tilan monimutkaisuusmittauksia käytetään tietorakenteiden arvioimiseen.)

Lisätään solmut yksittäisesti linkitettyyn luetteloon

Solmun lisääminen yksin linkitettyyn luetteloon on jonkin verran monimutkaisempaa kuin yksin linkitetyn luettelon luominen, koska on otettava huomioon kolme tapausta:

Lisäys ennen ensimmäistä solmua.
Lisäys viimeisen solmun jälkeen.
Lisäys kahden solmun väliin.

Lisäys ennen ensimmäistä solmua

Uusi solmu lisätään ennen ensimmäistä solmua osoittamalla ylimmän solmun viite uuden solmun linkkikenttään ja osoittamalla uuden solmun viite alkuun muuttuja. Tämän toiminnan osoittaa seuraava pseudokoodi:

 ILMOITA Solmun temp temp = UUSI Solmun temp.nimi = "B" temp.seuraava = ylh. Ylin = lämpötila

Tuloksena olevatSolmu luettelo näkyy kuvassa 3.

Tämän operaation aikakompleksi on O (1).

Lisäys viimeisen solmun jälkeen

Uusi solmu lisätään viimeisen solmun jälkeen osoittamalla tyhjä uuden solmun linkkikenttään, kulkemalla yksi linkitetty luettelo viimeisen solmun löytämiseksi ja osoittamalla uuden solmun viittaus viimeisen solmun linkkikenttään, kuten seuraava pseudokoodi osoittaa:

 temp = NEW Solmu temp.name = "C" temp.next = NULL DECLARE Solmu temp2 temp2 = top // Oletetaan, että top (ja temp2) eivät ole NULL // edellisen pseudokoodin takia. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 viittaa nyt viimeiseen solmuun. temp2.seuraava = lämpötila

Kuva 4 paljastaa luettelon lisäämisen jälkeen Solmu C jälkeen Solmu A.

Tällä operaatiolla on O-ajan monimutkaisuus (n)--lineaarinen. Sen aikakompleksisuutta voitaisiin parantaa O: ksi (1) ylläpitämällä viittaus viimeiseen solmuun. Siinä tapauksessa ei ole tarpeen etsiä viimeistä solmua.

Lisäys kahden solmun väliin

Solmun lisääminen kahden solmun väliin on monimutkaisin tapaus. Voit lisätä uuden solmun kahden solmun väliin kulkemalla luetteloa etsimään uuden solmun edelle tuleva solmu, määrittämällä löydetyn solmun linkkikentän viite uuden solmun linkkikenttään ja osoittamalla uuden solmun viittaus löydetyn solmun linkkiin ala. Seuraava näennäiskoodi osoittaa nämä tehtävät:

 temp = UUSI Solmu temp.name = "D" temp2 = alkuun // Oletetaan, että uusi luotu solmu lisää solmun // A perään ja että solmu A on olemassa. Todellisessa maailmassa ei ole // takuuta siitä, että jokin solmu on olemassa, joten meidän on tarkistettava // temp2, joka sisältää NULL sekä WHILE-silmukan otsikossa // että sen jälkeen, kun WHILE-silmukka on valmis. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 viittaa nyt solmuun A. temp.next = temp2.next temp2.next = temp

Kuvassa 5 on luettelo lisäyksen jälkeen Solmu D välillä Solmus A ja C.

Tällä operaatiolla on O-ajan monimutkaisuus (n).

Solmujen poistaminen linkitetystä luettelosta

Solmun poistaminen yksin linkitetystä luettelosta on myös jonkin verran monimutkaisempaa kuin yksin linkitetyn luettelon luominen. Harkittavia tapauksia on kuitenkin vain kaksi:

Ensimmäisen solmun poisto.
Poistetaan kaikki solmut paitsi ensimmäinen solmu.

Ensimmäisen solmun poisto

Ensimmäisen solmun poistaminen tarkoittaa linkin osoittamista ensimmäisen solmun linkkikentässä muuttujalle, joka viittaa ensimmäiseen solmuun, mutta vain silloin, kun on olemassa ensimmäinen solmu:

 JOS alkuun EI NULL SITTU top = top.sext; // Viittaus toiseen solmuun (tai NULL, kun solmuja on vain yksi). LOPPU JOS

Kuva 6 esittää luettelon näkymiä ennen ja jälkeen, joista ensimmäinen Solmu on poistettu. Solmu B katoaa ja Solmu A: sta tulee ensimmäinen Solmu.

Tämän operaation aikakompleksi on O (1).

Poistetaan kaikki solmut paitsi ensimmäinen solmu

Minkä tahansa solmun poistaminen, mutta ensimmäinen solmu sisältää poistettavan solmun edeltävän solmun paikantamisen ja viittauksen osoittamisen poistettavan solmun linkkikentässä edellisen solmun linkkikenttään. Harkitse seuraavaa pseudokoodia:

 JOS ylhäältä NE TYHJÄ Sitten temp = alkuun KUN Temp.nimi EI "A" temp = temp.seuraava LOPETTAA, kun taas // Oletetaan, että lämpötila viittaa Solmu A. temp.next = temp.next.next // Solmua D ei enää ole. LOPPU JOS

Kuvassa 7 esitetään ennen ja jälkeen luettelonäkymät, joissa välituote Solmu poistetaan. Solmu D katoaa.

Tällä operaatiolla on O-ajan monimutkaisuus (n).

Esimerkki 1: Luo, lisää ja poista linkitetty luettelo

Olen luonut Java-sovelluksen nimeltä SLLDemo joka osoittaa, kuinka luoda, lisätä ja poistaa solmuja linkitettyyn luetteloon. Listaus 1 esittää tämän sovelluksen lähdekoodin.

Listaus 1. Java-sovellusten esittely yksin linkitetyille luetteloille (SSLDemo.java, versio 1)

 julkinen lopullinen luokka SLLDemo {yksityinen staattinen luokka Solmu {Merkkijonon nimi; Seuraava solmu; } public static void main (Merkkijono [] argumentit) {Solmu ylhäällä = tyhjä; // 1. Yksittäisesti linkitettyä luetteloa ei ole olemassa. top = uusi solmu (); top.name = "A"; top.next = null; dump ("tapaus 1", yläosa); // 2. Yksin linkitetty luettelo on olemassa ja solmu on lisättävä // ennen ensimmäistä solmua. Solmun lämpötila; temp = uusi solmu (); temp.nimi = "B"; temp.seuraava = yläosa; yläosa = lämpötila; dump ("tapaus 2", yläosa); // 3. Yksin linkitetty luettelo on olemassa ja solmu on lisättävä // viimeisen solmun jälkeen. temp = uusi solmu (); temp.nimi = "C"; temp.next = null; Solmu temp2; temp2 = yläosa; while (temp2.next! = null) temp2 = temp2.next; temp2.seuraava = temp; dump ("tapaus 3", yläosa); // 4. Yksin linkitetty luettelo on olemassa ja solmu on lisättävä // kahden solmun väliin. temp = uusi solmu (); temp.nimi = "D"; temp2 = yläosa; while (temp2.nimi. on yhtä suuri ("A") == false) temp2 = temp2.seuraava; temp.next = temp2.next; temp2.seuraava = temp; dump ("tapaus 4", yläosa); // 5. Poista ensimmäinen solmu. alkuun = ylh. seuraava; dump ("Ensimmäisen solmun poiston jälkeen", ylhäältä); // 5.1 Palauta solmu B. temp = new Node (); temp.nimi = "B"; temp.seuraava = yläosa; yläosa = lämpötila; // 6. Poista kaikki solmut paitsi ensimmäinen solmu. lämpötila = yläosa; while (temp.nimi. on yhtä suuri ("A") == false) temp = temp.seuraava; temp.next = temp.next.next; dump ("D-solmun poiston jälkeen", ylhäältä); } private static void dump (String msg, Node topNode) {System.out.print (msg + ""); while (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }}

Koosta Listaus 1 seuraavasti:

 javac SLLDemo.java

Suorita tuloksena oleva sovellus seuraavasti:

 java SLLDemo

Ota huomioon seuraava tulos:

 Tapaus 1 A Tapaus 2 B A Tapaus 3 B A C Tapaus 4 B A D C ensimmäisen solmupoiston jälkeen A D C D-solmun poiston jälkeen B A C

Yhdistettyjen linkitettyjen luetteloiden yhdistäminen

Saatat joutua joskus liittämään yhteen linkitetyn luettelon toiseen yksin linkitettyyn luetteloon. Oletetaan esimerkiksi, että sinulla on luettelo sanoista, jotka alkavat kirjaimista A - M ja toinen luettelo sanoista, jotka alkavat kirjaimista N - Z, ja haluat yhdistää nämä luettelot yhdeksi luetteloksi. Seuraava pseudokoodi kuvaa algoritmia yksittäisen linkitetyn luettelon liittämiseen toiseen:

 DECLARE-solmu top1 = NULL DECLARE-solmu top2 = NULL // Oletetaan koodi, joka luo top1-viitatun yksittäisesti linkitetyn luettelon. // Oletetaan koodi, joka luo top2-viitatun yksittäisesti linkitetyn luettelon. // Yhdistä top2-viitattu luettelo top1-viitattuun luetteloon. JOS top1 EQ NULL top1 = top2 END END IF // Etsi viimeinen solmu top1-viitteellisestä luettelosta. ILMOITA Solmun lämpötila = top1 KUN Lämpötila seuraava EI NULL temp = Lämpötila seuraava END WHILE // Yhdistä top2 to top1. temp.sext = top2 END

Triviaalissa tapauksessa ei ole alkuun 1-viitattu luettelo, ja niin alkuun 1 on osoitettu alkuun2arvo, joka olisi TYHJÄ jos ei olisi alkuun2-viitattu luettelo.

Tällä operaatiolla on O (1): n aikakompleksi triviaalissa tapauksessa ja O: n aikakompleksi (n) muuten. Jos kuitenkin ylläpidät viittausta viimeiseen solmuun, ei tarvitse etsiä luetteloa tälle solmulle. ajan monimutkaisuus muuttuu arvoksi O (1).

Yhden linkitetyn luettelon kääntäminen

Toinen hyödyllinen operaatio linkitetyllä luettelolla on käänteinen, joka kääntää luettelon linkit päinvastaiseksi, jotta voit siirtyä sen solmuista vastakkaiseen suuntaan. Seuraava pseudokoodi kääntää alkuun 1-viitatun luettelon linkit:

 ILMOITA Solmu p = top1 // Alkuperäisen linkitetyn luettelon alkuun. ILMOITA Solmu q = NULL // Käänteisen yksittäisesti linkitetyn luettelon yläreuna. DECLARE Node r // Väliaikainen solmu -viitemuuttuja. WHOLE p NE NULL // Jokaiselle solmulle alkuperäisessä yksitellen linkitetyssä luettelossa ... r = q // Tallenna tulevan seuraajan solmun viite. q = p // Viittaus tulevaan edeltäjään Solmu. p = p.seuraava // Seuraava seuraava solmu alkuperäisessä yksittäisesti linkitetyssä luettelossa. q.next = r // Linkitä tuleva edeltäjän solmu tulevaan seuraajaan. END WHILE top1 = q // Tee ensimmäinen1-viite ensin Solmu päinvastaisessa linkitetyssä luettelossa. LOPPU

Tällä operaatiolla on O-ajan monimutkaisuus (n).