Podatkovne strukture in algoritmi v Javi, 4. del: Enotno povezani seznami

Tako kot nizi, ki so bili predstavljeni v 3. delu te vadnice, so povezani seznami temeljna kategorija podatkovne strukture, na kateri lahko temeljijo bolj zapletene podatkovne strukture. Za razliko od zaporedja elementov pa a povezan seznam je zaporedje vozlišč, kjer je vsako vozlišče povezano s prejšnjim in naslednjim vozliščem v zaporedju. Spomnimo se, da a vozlišče je objekt, ustvarjen iz samoreferenčnega razreda, in samoreferenčni razred ima vsaj eno polje, katerega referenčni tip je ime razreda. Vozlišča na povezanem seznamu so povezana prek reference vozlišča. Tu je primer:

 razred Zaposleni {private int empno; ime zasebnega niza; zasebna dvojna plača; javni uslužbenec naslednji; // Drugi člani. }

V tem primeru Zaposleni je samoreferenčni razred, ker je njegov Naslednji polje ima tip Zaposleni. To polje je primer a polje povezave ker lahko shrani sklic na drug predmet svojega razreda - v tem primeru drugega Zaposleni predmet.

Ta vadnica predstavlja podrobnosti o posamezno povezanih seznamih v programiranju Java. Naučili se boste postopkov za ustvarjanje posamezno povezanega seznama, vstavljanje vozlišč v posamezno povezan seznam, brisanje vozlišč s posamezno povezanega seznama, združevanje posamezno povezanega seznama v drug samostojno povezan seznam in obračanje posamezno povezanega seznama. Raziskali bomo tudi algoritme, ki se najpogosteje uporabljajo za razvrščanje posamezno povezanih seznamov, in zaključili s primerom, ki prikazuje algoritem za razvrščanje po vstavitvi.

prenos Prenesite kodo Prenesite tri primere aplikacij za ta članek. Ustvaril Jeff Friesen za JavaWorld.

Kaj je posamezno povezan seznam?

A enojno povezan seznam je povezan seznam vozlišč, kjer ima vsako vozlišče eno vezno polje. V tej podatkovni strukturi referenčna spremenljivka vsebuje sklic na prvo (ali zgornje) vozlišče; vsako vozlišče (razen zadnjega ali spodnjega) se poveže z naslednjim; in polje povezave zadnjega vozlišča vsebuje ničelno referenco, ki označuje konec seznama. Čeprav je referenčna spremenljivka pogosto imenovana vrh, lahko izberete poljubno ime.

Slika 1 predstavlja posamezno povezan seznam s tremi vozlišči.

Spodaj je psevdokoda za posamezno povezan seznam.

 IZJAVA RAZREDNEGA vozlišča IZJAVA STRANSKEGA imena DECLARE Vozlišče na koncu KONČNO IZJAVLJIVO IZGLAVNO Vozlišče = NULL

Vozlišče je samoreferenčni razred z a ime podatkovno polje in a Naslednji polje povezave. vrh je referenčna spremenljivka tipa Vozlišče ki vsebuje sklic na prvo Vozlišče predmet na posamezno povezanem seznamu. Ker seznam še ne obstaja, vrhZačetna vrednost je NIČ.

Ustvarjanje enojno povezanega seznama v Javi

S povezavo ustvarite posamezno povezan seznam Vozlišče predmet. Naslednja psevdokoda ustvari Vozlišče predmet, dodeli sklic na vrh, inicializira svoje podatkovno polje in dodeli NIČ na njegovo povezavno polje:

 top = NOVO vozlišče top.name = "A" top.next = NULL

Slika 2 prikazuje začetni posamično povezan seznam, ki izhaja iz te psevdokode.

Ta operacija ima časovno zahtevnost O (1) - konstantna. Spomnimo se, da se O (1) izgovarja "Big Oh of 1." (Glejte 1. del za opomnik, kako se meritve zapletenosti časa in prostora uporabljajo za ovrednotenje podatkovnih struktur.)

Vstavljanje vozlišč v posamezno povezan seznam

Vstavljanje vozlišča v posamezno povezan seznam je nekoliko bolj zapleteno kot ustvarjanje posamezno povezanega seznama, ker je treba upoštevati tri primere:

Vstavitev pred prvo vozlišče.
Vstavitev po zadnjem vozlišču.
Vstavljanje med dvema vozliščema.

Vstavitev pred prvo vozlišče

Novo vozlišče se vstavi pred prvo vozlišče tako, da se sklicu zgornjega vozlišča dodeli polje povezave novega vozlišča in referenca novega vozlišča dodeli vrh spremenljivka. Ta postopek je prikazan z naslednjo psevdokodo:

 IZJAVA Vozlišče temp temp = NOVO vozlišče temp.name = "B" temp.next = top top = temp

Nastali dvo-Vozlišče seznam je prikazan na sliki 3.

Ta operacija ima časovno zapletenost O (1).

Vstavitev po zadnjem vozlišču

Za zadnjim vozliščem se z dodelitvijo vstavi novo vozlišče nič na polje povezave novega vozlišča, prehod po posamezno povezanem seznamu, da bi našli zadnje vozlišče, in dodeljevanje reference novega vozlišča na polje povezave zadnjega vozlišča, kot dokazuje naslednja psevdokoda:

 temp = NOVO vozlišče temp.name = "C" temp.next = NULL DECLARE Vozlišče temp2 temp2 = top // Predpostavljamo, da vrh (in temp2) zaradi prejšnje psevdokode nista NULL //. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 se zdaj sklicuje na zadnje vozlišče. temp2.next = temp

Slika 4 razkriva seznam po vstavitvi Vozlišče C po Vozlišče A.

Ta operacija ima časovno zapletenost O (n) - linearno. Njeno časovno zapletenost bi lahko izboljšali na O (1) z ohranjanjem sklica na zadnje vozlišče. V tem primeru ne bi bilo treba iskati zadnjega vozlišča.

Vstavljanje med dvema vozliščema

Vstavljanje vozlišča med dve vozlišči je najbolj zapleten primer. Novo vozlišče vstavite med dve vozlišči tako, da s prehodom po seznamu poiščete vozlišče, ki prihaja pred novim vozliščem, dodelite referenco v polju povezave najdenega vozlišča v polje povezave novega vozlišča in dodelite referenco novega vozlišča povezavi najdenega vozlišča polje. Naslednja psevdokoda prikazuje te naloge:

 temp = NOVO vozlišče temp.name = "D" temp2 = top // Predpostavljamo, da se novo ustvarjeno vozlišče vstavi za vozlišče // A in da vozlišče A obstaja. V resničnem svetu ni nobenega // zagotovila, da obstaja katero koli vozlišče, zato bi morali // preveriti, ali temp2 vsebuje NULL v glavi zanke WHILE // in po zaključku zanke WHILE. WHILE temp2.name NE "A" temp2 = temp2.next KONEC WHILE // temp2 se zdaj sklicuje na vozlišče A. temp.next = temp2.next temp2.next = temp

Slika 5 predstavlja seznam po vstavitvi Vozlišče D med Vozliščes A in C.

Ta operacija ima časovno zapletenost O (n).

Brisanje vozlišč s posamično povezanega seznama

Brisanje vozlišča s posamično povezanega seznama je tudi nekoliko bolj zapleteno kot ustvarjanje posamično povezanega seznama. Vendar je treba upoštevati le dva primera:

Izbris prvega vozlišča.
Izbris katerega koli vozlišča, razen prvega.

Izbris prvega vozlišča

Brisanje prvega vozlišča vključuje dodelitev povezave v polju povezave prvega vozlišča spremenljivki, ki se sklicuje na prvo vozlišče, vendar le, če obstaja prvo vozlišče:

 ČE na vrhu NE NULL, Nato top = top.next; // Sklic na drugo vozlišče (ali NULL, če je samo eno vozlišče). KONEC ČE

Slika 6 prikazuje poglede seznama, kjer je prvi, pred in po njem Vozlišče je bil izbrisan. Vozlišče B izgine in Vozlišče A postane prvi Vozlišče.

Ta operacija ima časovno zapletenost O (1).

Izbris katerega koli vozlišča, razen prvega

Brisanje katerega koli vozlišča, razen prvega, vključuje iskanje vozlišča, ki je pred vozliščem, ki ga je treba izbrisati, in dodelitev sklica v polju povezave vozlišča, ki ga je treba izbrisati, na polje povezave prejšnjega vozlišča. Upoštevajte naslednjo psevdokodo:

 ČE na vrh NE NULL, TEMP temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // Predpostavljamo, da se temp sklicuje na vozlišče A. temp.next = temp.next.next // vozlišče D ne obstaja več. KONEC ČE

Na sliki 7 so prikazani pred in po pogledi na seznam, ki je vmesni Vozlišče je izbrisan. Vozlišče D izgine.

Ta operacija ima časovno zapletenost O (n).

Primer # 1: Ustvarite, vstavite in izbrišite na enem samem seznamu

Ustvaril sem aplikacijo Java z imenom SLLDemo ki prikazuje, kako ustvariti, vstaviti in izbrisati vozlišča na posamezno povezanem seznamu. Seznam 1 predstavlja izvorno kodo te aplikacije.

Seznam 1. Predstavitev aplikacije Java za posamezno povezane sezname (SSLDemo.java, različica 1)

 javni končni razred SLLDemo {private static class Node {String name; Vozlišče naslednje; } public static void main (String [] args) {Node top = null; // 1. Posamezno povezan seznam ne obstaja. top = novo vozlišče (); top.name = "A"; top.next = null; smetišče ("Primer 1", zgoraj); // 2. Enotno povezan seznam obstaja in vozlišče je treba vstaviti // pred prvo vozlišče. Temp vozlišča; temp = novo vozlišče (); temp.name = "B"; temp.next = top; vrh = temp; smetišče ("Primer 2", zgoraj); // 3. Enotno povezan seznam obstaja in vozlišče je treba vstaviti // za zadnjim vozliščem. temp = novo vozlišče (); temp.name = "C"; temp.next = null; Vozlišče temp2; temp2 = vrh; while (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; smetišče ("Primer 3", zgoraj); // 4. Enotno povezan seznam obstaja in vozlišče je treba vstaviti // med dvema vozliščema. temp = novo vozlišče (); temp.name = "D"; temp2 = vrh; while (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; smetišče ("Primer 4", zgoraj); // 5. Izbriši prvo vozlišče. top = top.next; dump ("Po prvem brisanju vozlišča", zgoraj); // 5.1 Obnovi vozlišče B. temp = novo vozlišče (); temp.name = "B"; temp.next = top; vrh = temp; // 6. Izbriši katero koli vozlišče, razen prvega. temp = vrh; while (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Po izbrisu vozlišča D", zgoraj); } zasebno statično izpraznitev praznine (String msg, Node topNode) {System.out.print (msg + ""); while (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }}

Sestavite seznam 1, kot sledi:

 javac SLLDemo.java

Nastalo aplikacijo zaženite na naslednji način:

 java SLLDemo

Upoštevati morate naslednje rezultate:

 Primer 1 A Primer 2 B A Primer 3 B A C Primer 4 B A D C Po prvem brisanju vozlišča A D C Po brisanju vozlišča D A A

Združevanje posamezno povezanih seznamov

Občasno boste morda morali povezati posamezno povezan seznam z drugim samostojno povezanim seznamom. Recimo, da imate na primer seznam besed, ki se začnejo s črkami A do M, in drug seznam besed, ki se začne s črkami N do Ž, in želite te sezname združiti v en seznam. Naslednja psevdokoda opisuje algoritem za združevanje enega posamezno povezanega seznama z drugim:

 DECLARE Vozlišče top1 = NULL DECLARE Vozlišče top2 = NULL // Predpostavimo kodo, ki ustvari enojno povezan seznam s sklicevanjem na top1. // Predpostavimo kodo, ki ustvari enojno povezan seznam z referenco na top2. // Združi seznam z referencami top2 na seznam z referenco top1. IF top1 EQ NULL top1 = top2 END END IF // Poiščite končno vozlišče na seznamu, na katerega se sklicuje top1. IZJAVA Vozlišče temp = top1, medtem ko je temp.next NE NULL temp = temp.next END WHILE // Združi top2 v top1. temp.next = top2 END

V nepomembnem primeru ni vrh1-referenčni seznam itd vrh1 je dodeljena vrh2vrednost, ki bi bila NIČ če ne bi bilo vrh2-referenčni seznam.

Ta operacija ima časovno zapletenost O (1) v nepomembnem primeru in časovno zapletenost O (n) drugače. Če pa se sklicujete na zadnje vozlišče, za to vozlišče ni treba iskati po seznamu; časovna zapletenost se spremeni v O (1).

Pretvorba posamezno povezanega seznama

Druga koristna operacija na posamezno povezanem seznamu je inverzija, ki obrne povezave seznama, tako da lahko vozite po njegovih vozliščih v nasprotno smer. Naslednja psevdokoda razveljavi vrh1povezave do referenčnega seznama:

 IZJAVA Vozlišče p = top1 // Vrh izvirnega posamično povezanega seznama. DECLARE Vozlišče q = NULL // Vrh obrnjenega enojno povezanega seznama. DECLARE Vozlišče r // Referenčna spremenljivka začasnega vozlišča. WHILE p NE NULL // Za vsako vozlišče na izvirnem enojno povezanem seznamu ... r = q // Shrani referenco prihodnjega naslednika vozlišča. q = p // Referenca na prihodnje vozlišče predhodnika. p = p.next // Referenca na naslednje vozlišče v izvirnem enojno povezanem seznamu. q.next = r // Poveži prihodnje vozlišče predhodnika s vozliščem naslednika. END WHILE top1 = q // Ustvari referenco top1 kot prvo vozlišče na obrnjenem posamezno povezanem seznamu. KONEC

Ta operacija ima časovno zapletenost O (n).