Vaikka yksin linkitetyillä luetteloilla on monia käyttötarkoituksia, niissä on myös joitain rajoituksia. Ensinnäkin yksitellen linkitetyt luettelot rajoittavat solmun kulkemisen yhteen suuntaan: et voi liikkua yksitellen linkitetyn luettelon taaksepäin, ellet ensin muuta sen solmulinkkejä, mikä vie aikaa. Jos teet taaksepäin liikkumisen ja sinun on palautettava solmun kulku alkuperäiseen suuntaan, sinun on toistettava inversio, joka vie enemmän aikaa. Yksin linkitetyt luettelot myös rajoittavat solmun poistamista. Tämän tyyppisessä luettelossa et voi poistaa mielivaltaista solmua ilman pääsyä solmun edeltäjälle.
Onneksi Java tarjoaa monenlaisia luetteloita, joiden avulla voit etsiä ja lajitella Java-ohjelmiesi tallennettuja tietoja. Tämä viimeinen opetusohjelma Tietorakenteet ja algoritmit -sarja esittelee etsinnän ja lajittelun kaksinkertaisesti linkitettyjen luetteloiden ja kiertolinkkien avulla. Kuten näette, nämä kaksi tietorakenneluokkaa perustuvat yksitellen linkitettyihin luetteloihin, jotka tarjoavat laajemman valikoiman haku- ja lajittelutapoja Java-ohjelmissasi.
Kaksinkertaisesti linkitetyt luettelot
A kaksinkertaisesti linkitetty luettelo on linkitetty luettelo solmuista, joissa jokaisella solmulla on pari linkkikenttää. Yhden linkkikentän avulla voit liikkua luettelossa eteenpäin, kun taas toinen solmu antaa sinun liikkua luettelossa taaksepäin. Eteenpäin suuntaa varten viitemuuttuja pitää sisällään viittauksen ensimmäiseen solmuun. Jokainen solmu linkittää seuraavaan solmuun "seuraavan" linkkikentän kautta lukuun ottamatta viimeistä solmua, jonka "seuraava" linkkikenttä sisältää nollaviitteen, joka merkitsee luettelon loppua (eteenpäin). Taaksepäin suunta toimii samalla tavalla. Viitemuuttujassa on viittaus eteenpäin suuntautuvan viimeiseen solmuun, jonka tulkitset ensimmäisenä solmuna. Jokainen solmu linkittää edelliseen solmuun "edellisen" linkkikentän kautta. Ensimmäisen solmun "edellinen" linkkikenttä sisältää nollan, joka merkitsee luettelon loppua.
Yritä ajatella kaksinkertaisesti linkitetty luettelo yhtenä linkitettyjen luetteloiden pariksi, joista kukin yhdistää samat solmut. Kuvan 1 kaavio osoittaa topForward-viitattu ja alkuunTakaisin- viittaavat yksitellen linkitettyihin luetteloihin.
CRUD-operaatiot kaksoislinkitetyissä luetteloissa
Solmujen luominen, lisääminen ja poistaminen ovat kaikki kaksinkertaisesti linkitetyn luettelon yleisiä toimintoja. Ne ovat samanlaisia kuin toiminnot, jotka olet oppinut yksin linkitetyille luetteloille. (Muista, että kaksinkertaisesti linkitetty luettelo on vain pari yksinkytkettyjä luetteloita, jotka yhdistävät samat solmut.) Seuraava pseudokoodi osoittaa solmujen luomisen ja lisäämisen kuvassa 1 esitettyyn kaksinkertaisesti linkitettyyn luetteloon. Pseudokoodi osoittaa myös solmun poisto:
DECLARE CLASS Solmu DECLARE STRING nimi DECLARE solmu seuraava DECLARE solmu edellinen END DECLARE DECLARE solmu topForward DECLARE solmu temp DECLARE solmu topBackward topForward = NEW solmu topForward.name = "A" temp = NEW solmu temp.name = "B" topbackback = .name = "C" // Luo eteenpäin yksitellen linkitetty luettelo topForward.next = temp temp.next = topBackward topBackward.next = NULL // Luo taaksepäin yksittäin linkitetty luettelo topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Poista solmu B. temp.prev.next = temp.next; // Ohita solmu B eteenpäin linkitetyssä luettelossa. temp.sext.prev = temp.prev; // Ohita solmu B taaksepäin yksilinkityssä luettelossa. LOPPU Esimerkkisovellus: CRUD kaksinkertaisesti linkitetyssä luettelossa
Esimerkki Java-sovelluksesta DLL-demo osoittaa kuinka luoda, lisätä ja poistaa solmuja kaksinkertaisesti linkitetyssä luettelossa. Sovelluksen lähdekoodi näkyy luettelossa 1.
Luettelointi 1. Java-sovellus, joka osoittaa CRUD: n kaksoislinkityssä luettelossa
public final class DLLDemo {private static class Node {String name; Seuraava solmu; Solmu prev; } public static void main (String [] args) {// Luo kaksinkertaisesti linkitetty luettelo. Solmu topForward = uusi solmu (); topForward.name = "A"; Solmun lämpötila = uusi Solmu (); temp.nimi = "B"; Solmu topBackward = uusi solmu (); topBackward.name = "C"; topForward.next = lämpötila; temp.next = topBackward; topBackward.next = null; topBackward.prev = lämpötila; temp.prev = topForward; topForward.prev = null; // Siirrä eteenpäin yksitellen linkitetty luettelo. System.out.print ("Lähetä edelleen linkitetty luettelo:"); temp = topForward; while (temp! = null) {System.out.print (temp.nimi); temp = temp. seuraava; } System.out.println (); // Tyhjennä taaksepäin linkitetty luettelo. System.out.print ("Taaksepäin linkitetty luettelo:"); temp = topBackback; while (temp! = null) {System.out.print (temp.nimi); temp = temp.prev; } System.out.println (); // Viitesolmu B. temp = topForward.next; // Poista solmu B. temp.prev.next = temp.next; temp.sext.prev = temp.prev; // Siirrä eteenpäin yksitellen linkitetty luettelo. System.out.print ("Lähetä edelleen linkitetty luettelo (poiston jälkeen):"); temp = topForward; while (temp! = null) {System.out.print (temp.nimi); temp = temp. seuraava; } System.out.println (); // Tyhjennä taaksepäin linkitetty luettelo. System.out.print ("Taaksepäin linkitetty luettelo (poiston jälkeen):"); temp = topBackback; while (temp! = null) {System.out.print (temp.nimi); temp = temp.prev; } System.out.println (); }} Koosta Listaus 4 seuraavasti:
javac DLLDemo.java Suorita tuloksena oleva sovellus seuraavasti:
java DLLDemo Ota huomioon seuraava tulos:
Siirrä edelleen linkitetty luettelo eteenpäin: ABC Taaksepäin yksittäin linkitetty luettelo: CBA Lähetä edelleen linkitetty luettelo eteenpäin (poiston jälkeen): AC Taaksepäin yksittäin linkitetty luettelo (poiston jälkeen): CA Sekoittaminen kaksoislinkitetyissä luetteloissa
Java Collections Framework sisältää a Kokoelmat luokan hyödyllisyysmenetelmiä, joka on osa java.util paketti. Tähän luokkaan kuuluvat void shuffle (luetteloluettelo) menetelmä "satunnaisesti läpäisee määritetyn luettelon käyttämällä satunnaisuuden oletuslähdettä"" Voit esimerkiksi käyttää tätä menetelmää sekoittamaan kaksoislinkillä ( java.util.LinkedList luokka on esimerkki). Alla olevasta pseudokoodista näet kuinka Sekoita algoritmi saattaa sekoittaa kaksoislinkitetyn luettelon:
ILMOITA RANDOM-rnd = uusi RANDOM-ILMOITA INTEGER i FOR i = 3 DOWNTO 2 -vaihtoa (topForward, i - 1, rnd.nextInt (i)) END TO FUNCTION swap (Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Etsi i-solmu. Solmu nodei = alkuun FOR k = 0 TO i - 1 nodei = nodei.seuraava LOPPU // Paikanna j. solmu. Solmu solmu = alkuun FOR k = 0 TO i - 1 solmu = solmu. Seuraava LOPPU // Suorita vaihto. DECLARE STRING namei = nodei.name DECLARE STRING namej = solmunimi.nimi solmun_nimi = namei solmionimi.nimi = namej LOPPU FUNCTION END Shuffle-algoritmi saa satunnaisuuden lähteen ja kulkee sitten luettelon taaksepäin viimeisestä solmusta toiseen. Se vaihtaa satunnaisesti valitun solmun (joka on oikeastaan vain nimikenttä) toistuvasti "nykyiseen sijaintiin". Solmut valitaan satunnaisesti luettelon osasta, joka kulkee ensimmäisestä solmusta nykyiseen sijaintiin lukien. Huomaa, että tämä algoritmi on karkeasti otettu void shuffle (luetteloluettelo)lähdekoodi.
Shuffle-algoritmin pseudokoodi on laiska, koska se keskittyy vain eteenpäin kulkevaan yksinkytkettyyn luetteloon. Se on kohtuullinen suunnittelupäätös, mutta maksamme siitä hinnan ajoissa. Ajan monimutkaisuus on O (n2). Ensinnäkin meillä on O (n) silmukka, joka kutsuu vaihtaa(). Toiseksi sisällä vaihtaa(), meillä on kaksi peräkkäistä O (n) silmukoita. Muista seuraava sääntö osasta 1:
Jos f1(n) = O (g(n)) ja f2(n) = O (h(n)) sitten eräs) f1(n)+f2(n) = max (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). Osa (a) käsittelee peräkkäisiä algoritmeja. Täällä meillä on kaksi O (n) silmukoita. Säännön mukaan tuloksena oleva ajan monimutkaisuus olisi O (n). Osa (b) käsittelee sisäkkäisiä algoritmeja. Tässä tapauksessa meillä on O (n) kerrottuna O: lla (n), jolloin saadaan O (n2).
Huomaa, että Shufflen avaruuskompleksi on O (1), joka johtuu ilmoitetuista auttajamuuttujista.
Esimerkkisovellus: Sekoittaminen kaksinkertaisesti linkitetyssä luettelossa
Sekoita Listing 2 -sovellus on osoitus Shuffle-algoritmista.
Luettelo 2. Shuffle-algoritmi Javassa
tuo java.util.Random; public final class Shuffle {yksityinen staattinen luokka Solmu {Merkkijonon nimi; Seuraava solmu; Solmu prev; } public static void main (String [] args) {// Luo kaksinkertaisesti linkitetty luettelo. Solmu topForward = uusi solmu (); topForward.name = "A"; Solmun lämpötila = uusi Solmu (); temp.nimi = "B"; Solmu topBackward = uusi solmu (); topBackward.name = "C"; topForward.next = lämpötila; temp.next = topBackward; topBackward.next = null; topBackward.prev = lämpötila; temp.prev = topForward; topForward.prev = null; // Siirrä eteenpäin yksitellen linkitetty luettelo. System.out.print ("Lähetä edelleen linkitetty luettelo:"); temp = topForward; while (temp! = null) {System.out.print (temp.nimi); temp = temp. seuraava; } System.out.println (); // Tyhjennä taaksepäin linkitetty luettelo. System.out.print ("Taaksepäin linkitetty luettelo:"); temp = topBackback; while (temp! = null) {System.out.print (temp.nimi); temp = temp.prev; } System.out.println (); // Sekoita luettelo. Satunnainen rnd = uusi Satunnainen (); for (int i = 3; i> 1; i--) -vaihto (topForward, i - 1, rnd.sextInt (i)); // Siirrä eteenpäin yksitellen linkitetty luettelo. System.out.print ("Lähetä edelleen linkitetty luettelo:"); temp = topForward; while (temp! = null) {System.out.print (temp.nimi); temp = temp. seuraava; } System.out.println (); // Tyhjennä taaksepäin linkitetty luettelo. System.out.print ("Taaksepäin linkitetty luettelo:"); temp = topBackback; while (temp! = null) {System.out.print (temp.nimi); temp = temp.prev; } System.out.println (); } public static void swap (Solmun yläosa, int i, int j) {// Etsi i-solmu. Solmu nodei = yläosa; for (int k = 0; k <i; k ++) nodei = nodei.seuraava; // Etsi j. solmu. Solmu solmu = yläosa; for (int k = 0; k <j; k ++) solmu j = solmu seuraava. Merkkijono namei = nodei.name; Merkkijonon nimi j = solmun nimi; solmun nimi = nimi; nodei.nimi = nimij; }} Koosta Listaus 5 seuraavasti:
javac Shuffle.java Suorita tuloksena oleva sovellus seuraavasti:
java Shuffle Sinun tulisi tarkkailla seuraavaa lähtöä yhdestä ajosta:
Eteenpäin linkitetty luettelo: ABC Taaksepäin yksittäin linkitetty luettelo: CBA Eteenpäin linkitetty luettelo eteenpäin: BAC Taaksepäin yksittäin linkitetty luettelo: CAB Pyöreät linkitetyt luettelot
Yksin linkitetyn luettelon viimeisen solmun linkkikenttä sisältää tyhjän linkin. Tämä pätee myös kaksinkertaisesti linkitettyyn luetteloon, joka sisältää linkkikentät eteenpäin ja taaksepäin linkitettyjen luetteloiden viimeisissä solmuissa. Oletetaan sen sijaan, että viimeiset solmut sisälsivät linkkejä ensimmäisiin solmuihin. Tässä tilanteessa päädyt a kiertolinkit, joka on esitetty kuvassa 2.
Kiertolinkit, jotka tunnetaan myös nimellä pyöreät puskurit tai pyöreät jonot, on monia käyttötarkoituksia. Esimerkiksi käyttöjärjestelmän keskeytyskäsittelijät käyttävät niitä puskuroimaan näppäinpainalluksia. Multimediasovellukset käyttävät pyöreään linkitettyjä luetteloita puskuroidakseen tietoja (esimerkiksi puskurointitiedot kirjoitetaan äänikortille). Tätä tekniikkaa käyttävät myös häviöttömän datan pakkausalgoritmit LZ77-perhe.
Linkitetyt luettelot vs. taulukot
Tässä tietorakenteita ja algoritmeja koskevassa sarjassa olemme tarkastelleet eri tietorakenteiden vahvuuksia ja heikkouksia. Koska olemme keskittyneet matriiseihin ja linkitettyihin luetteloihin, sinulla saattaa olla kysyttävää nimenomaan näistä tyypeistä. Mitä etuja ja haittoja linkitetyt luettelot ja taulukot tarjoavat? Milloin käytät linkitettyä luetteloa ja milloin taulukkoa? Voivatko molempien luokkien tietorakenteet integroida hyödylliseen hybrididatarakenteeseen? Yritän vastata näihin kysymyksiin alla.
Linkitetyt luettelot tarjoavat seuraavat edut matriiseihin verrattuna:
- Ne eivät vaadi ylimääräistä muistia laajennuksen tukemiseksi. Sitä vastoin matriisit vaativat ylimääräistä muistia, kun laajennus on tarpeen. (Kun kaikki elementit sisältävät dataelementtejä, uusia tietoja ei voida liittää taulukkoon.)
- Ne tarjoavat nopeamman solmun lisäyksen / poistamisen kuin vastaavat matriisipohjaiset toiminnot. Vain linkit on päivitettävä, kun lisäys- / poistokohta on tunnistettu. Matriisin näkökulmasta tietoerien lisääminen vaatii kaikkien muiden tietoelementtien liikkumisen tyhjän elementin luomiseksi. Vastaavasti olemassa olevan tietoerän poistaminen edellyttää kaikkien muiden tietoelementtien siirtämistä tyhjän elementin poistamiseksi. Kaikki tietoerien siirtäminen vie aikaa.
Taulukot sen sijaan tarjoavat seuraavat edut linkitettyihin luetteloihin verrattuna:
- Taulukkoelementit vievät vähemmän muistia kuin solmut, koska elementit eivät vaadi linkkikenttiä.
- Taulukot tarjoavat nopeamman pääsyn tietoihin, kokonaislukuihin perustuvien hakemistojen kautta.
