Selv om enkeltlinkede lister har mange bruksområder, gir de også noen begrensninger. For det første begrenser enkeltkoblede lister nodepassering til en enkelt retning: du kan ikke krysse en enkeltkoblet liste bakover, med mindre du først reverserer nodekoblingene, noe som tar tid. Hvis du gjør en omvendt traversal og trenger å gjenopprette node-traversal til den opprinnelige retningen, må du gjenta inversjonen, noe som tar mer tid. Enkeltkoblede lister begrenser også sletting av noder. I denne typen liste kan du ikke slette en vilkårlig node uten tilgang til nodens forgjenger.
Heldigvis tilbyr Java flere typer lister som du kan bruke til å søke og sortere lagrede data i Java-programmene dine. Denne siste opplæringen i Datastrukturer og algoritmer serien introduserer søk og sortering med dobbeltkoblede lister og sirkulært lister. Som du ser, bygger disse to datastrukturkategoriene på enkeltkoblede lister for å tilby et bredere spekter av søke- og sorteringsatferd i Java-programmene dine.
Dobbeltkoblede lister
EN dobbeltkoblet liste er en koblet liste over noder der hver node har et par lenkefelt. Ett koblingsfelt lar deg krysse listen i en fremoverretning, mens den andre noden lar deg krysse listen i bakoverretning. For fremoverretningen inneholder en referansevariabel en referanse til den første noden. Hver node lenker til neste node via "neste" lenkefelt, bortsett fra den siste noden, hvis "neste" lenkefelt inneholder nullreferansen for å indikere slutten på listen (i fremoverretningen). Bakoverretningen fungerer på samme måte. En referansevariabel inneholder en referanse til fremoverretningens siste node, som du tolker som den første node. Hver node knytter seg til den forrige noden via det "forrige" lenkefeltet. Den første nodens "forrige" koblingsfelt inneholder null for å betegne slutten på listen.
Prøv å tenke på en dobbeltkoblet liste som et par enkeltkoblede lister, som hver sammenkobler de samme nodene. Diagrammet i figur 1 viser topForward-henvist og topBackwardrefererte enkeltlister.
CRUD-operasjoner i dobbeltkoblede lister
Å opprette, sette inn og slette noder er alle vanlige operasjoner i en dobbeltkoblet liste. De ligner på operasjonene du lærte for enkeltkoblede lister. (Husk at en dobbeltkoblet liste bare er et par enkeltkoblede lister som kobler sammen de samme nodene.) Følgende pseudokode viser opprettelsen og innsettingen av noder i den dobbeltkoblede listen vist i figur 1. Pseudokoden viser også noden sletting:
AVKLARE KLASSE Knutep. AVKLARE STRING navn AVKLARE Node neste AVKLARE Node prev END DEKLARER DEKLARERE Node topForward DECLARE Node temp DEKLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward .name = "C" // Opprett fremad enkeltkoblet liste topForward.next = temp temp.next = topBackward topBackward.next = NULL // Lag backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Slett node B. temp.prev.next = temp.next; // Bypass Node B i fremover enkeltkoblet liste. temp.next.prev = temp.prev; // Bypass Node B i den bakoverliggende enkeltkoblede listen. SLUTT Eksempel på applikasjon: CRUD i en dobbeltkoblet liste
Eksemplet Java-applikasjon DLLDemo demonstrerer hvordan du oppretter, setter inn og sletter noder i en dobbeltkoblet liste. Applikasjonens kildekode vises i Oppføring 1.
Oppføring 1. Et Java-program som viser CRUD i en dobbeltkoblet liste
offentlig sluttklasse DLLDemo {privat statisk klasse Node {Strengnavn; Node neste; Node prev; } public static void main (String [] args) {// Bygg en dobbeltkoblet liste. Node topForward = ny Node (); topForward.name = "A"; Node temp = ny Node (); temp.name = "B"; Node topBackward = ny Node (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump frem enkeltstående liste. System.out.print ("Videresend enkeltkoblet liste:"); temp = toppForover; mens (temp! = null) {System.out.print (temp.name); temp = temp.neste; } System.out.println (); // Dump bakover enkeltstående liste. System.out.print ("Bakover enkeltkoblet liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Referansenode B. temp = topForward.next; // Slett node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump frem enkeltstående liste. System.out.print ("Videresend enkeltkoblet liste (etter sletting):"); temp = toppForover; mens (temp! = null) {System.out.print (temp.name); temp = temp.neste; } System.out.println (); // Dump bakover enkeltstående liste. System.out.print ("Bakover enkeltkoblet liste (etter sletting):"); temp = topBackward; mens (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} Sett opp liste 4 som følger:
javac DLLDemo.java Kjør den resulterende applikasjonen som følger:
java DLLDemo Du bør følge følgende utdata:
Fremover enkeltkoblet liste: ABC Bakover enkeltkoblet liste: CBA Fremover enkeltkoblet liste (etter sletting): AC Bakover enkeltkoblet liste (etter sletting): CA Bland i dobbeltkoblede lister
Java Collections Framework inkluderer en Samlinger klasse av bruksmetoder, som er en del av java.util pakke. Denne klassen inkluderer en void shuffle (Liste liste) metode som "tillater tilfeldig den angitte listen ved hjelp av en standard tilfeldighetskilde. "For eksempel kan du bruke denne metoden til å blande en kortstokk uttrykt som en dobbeltkoblet liste ( java.util.LinkedList klasse er et eksempel). I pseudokoden nedenfor kan du se hvordan Tilfeldig algoritme kan blande en dobbeltkoblet liste:
ERKLÆR RANDOM rnd = ny RANDOM DEKLARER INTEGER i FOR i = 3 NED 2 bytte (topForward, i - 1, rnd.nextInt (i)) END FOR FUNCTION swap (Node top, int i, int j) DEKLARE Node nodei, nodej DEKLARE INTEGER k // Finn det noden. Node nodei = topp FOR k = 0 TO i - 1 nodei = nodei.neste SLUT FOR // Finn jth node. Node nodej = topp FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Utfør byttet. ERKLÆR STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION SLUT Shuffle-algoritmen får en tilfeldighetskilde og krysser deretter listen bakover, fra den siste noden og opp til den andre. Det bytter gjentatte ganger en tilfeldig valgt node (som egentlig bare er navnefeltet) til "gjeldende posisjon." Noder velges tilfeldig fra den delen av listen som går fra den første noden til gjeldende posisjon, inkludert. Merk at denne algoritmen er grovt utdraget fra void shuffle (Liste liste)kildekoden.
Shuffle-algoritmen pseudokode er lat fordi den kun fokuserer på den fremovergående enkeltlinkede listen. Det er en rimelig designbeslutning, men vi betaler en pris for det i tidskompleksitet. Tidskompleksiteten er O (n2). Først har vi O (n) loop som ringer bytte(). For det andre, innenfor bytte(), har vi de to sekvensielle O (n) sløyfer. Husk følgende regel fra del 1:
Hvis f1(n) = O (g(n)) og f2(n) = O (h(n)) deretter en) f1(n)+f2(n) = maks (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). Del (a) omhandler sekvensielle algoritmer. Her har vi to O (n) sløyfer. I følge regelen vil den resulterende tidskompleksiteten være O (n). Del (b) omhandler nestede algoritmer. I dette tilfellet har vi O (nmultiplisert med O (n), noe som resulterer i O (n2).
Merk at Shuffles romkompleksitet er O (1), som følge av hjelpervariablene som er erklært.
Eksempel på bruk: Bland i en dobbeltkoblet liste
De Tilfeldig rekkefølge applikasjon i Listing 2 er en demonstrasjon av Shuffle-algoritmen.
Oppføring 2. Shuffle-algoritmen i Java
importere java.util.Random; offentlig sluttklasse Shuffle {private static class Node {Strengnavn; Node neste; Node prev; } public static void main (String [] args) {// Bygg en dobbeltkoblet liste. Node topForward = ny Node (); topForward.name = "A"; Node temp = ny Node (); temp.name = "B"; Node topBackward = ny Node (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump frem enkeltstående liste. System.out.print ("Videresend enkeltkoblet liste:"); temp = toppForover; mens (temp! = null) {System.out.print (temp.name); temp = temp.neste; } System.out.println (); // Dump bakover enkeltstående liste. System.out.print ("Bakover enkeltkoblet liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Tilfeldig liste. Tilfeldig rnd = ny Random (); for (int i = 3; i> 1; i--) bytte (topForward, i - 1, rnd.nextInt (i)); // Dump frem enkeltstående liste. System.out.print ("Videresend enkeltkoblet liste:"); temp = toppForover; mens (temp! = null) {System.out.print (temp.name); temp = temp.neste; } System.out.println (); // Dump bakover enkeltstående liste. System.out.print ("Bakover enkeltkoblet liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); } public static void swap (Node top, int i, int j) {// Finn med node. Node nodei = topp; for (int k = 0; k <i; k ++) nodei = nodei.next; // Finn jth node. Node nodej = topp; for (int k = 0; k <j; k ++) nodej = nodej.next; String namei = nodei.name; Strengnavnj = nodej.name; nodej.name = namei; nodei.name = namej; }} Sammensett oppføring 5 som følger:
javac Shuffle.java Kjør den resulterende applikasjonen som følger:
java Shuffle Du bør observere følgende utdata fra en kjøring:
Fremover enkeltkoblet liste: ABC Bakover enkeltkoblet liste: CBA Fremover enkeltkoblet liste: BAC Bakover enkeltkoblet liste: CAB Rundkoblede lister
Koblingsfeltet i den siste noden i en enkeltkoblet liste inneholder en nullkobling. Dette gjelder også i en dobbeltkoblet liste, som inneholder koblingsfeltene i de siste nodene i fremover og bakover enkeltkoblede lister. Anta i stedet at de siste nodene inneholdt lenker til de første nodene. I denne situasjonen vil du ende opp med en sirkulært knyttet liste, som er vist i figur 2.
Rundkoblede lister, også kjent som sirkulære buffere eller sirkulære køer, har mange bruksområder. For eksempel brukes de av operativsystemavbruddshåndterere for å buffer tastetrykk. Multimedia-applikasjoner bruker sirkulært lister for å buffere data (for eksempel buffering av data som skrives til et lydkort). Denne teknikken brukes også av LZ77-familien med tapsfri algoritmer for datakomprimering.
Koblede lister kontra matriser
Gjennom hele denne serien om datastrukturer og algoritmer har vi vurdert styrker og svakheter ved forskjellige datastrukturer. Siden vi har fokusert på matriser og koblede lister, kan det hende du har spørsmål om disse typene spesielt. Hvilke fordeler og ulemper tilbyr koblede lister og matriser? Når bruker du en koblet liste, og når bruker du en matrise? Kan datastrukturer fra begge kategorier integreres i en nyttig hybrid datastruktur? Jeg prøver å svare på disse spørsmålene nedenfor.
Koblede lister gir følgende fordeler i forhold til matriser:
- De krever ikke ekstra minne for å støtte utvidelse. Derimot krever matriser ekstra minne når utvidelse er nødvendig. (Når alle elementene inneholder dataelementer, kan ingen nye dataelementer legges til en matrise.)
- De tilbyr raskere nodinnsetting / sletting enn tilsvarende array-baserte operasjoner. Bare koblinger trenger å oppdateres etter at du har identifisert inn- / slettposisjonen. Fra et matriseperspektiv krever innsetting av dataelementer flytting av alle andre dataelementer for å skape et tomt element. Tilsvarende krever sletting av et eksisterende dataelement flytting av alle andre dataelementer for å fjerne et tomt element. All dataelementbevegelse tar tid.
I motsetning har arrays følgende fordeler i forhold til lenkede lister:
- Array-elementer opptar mindre minne enn noder fordi elementer ikke krever koblingsfelt.
- Arrays gir raskere tilgang til dataelementer via heltalsbaserte indekser.
