Mens enkeltbundne lister har mange anvendelser, præsenterer de også nogle begrænsninger. For det første begrænser enkeltkædede lister node-traversal til en enkelt retning: du kan ikke krydse en enkelt-linket liste bagud, medmindre du først vender dens node-links, hvilket tager tid. Hvis du foretager en omvendt traversal og har brug for at gendanne node-traversal til den oprindelige retning, bliver du nødt til at gentage inversionen, hvilket tager mere tid. Enkeltkædede lister begrænser også sletning af noder. I denne type liste kan du ikke slette en vilkårlig node uden adgang til nodens forgænger.
Heldigvis tilbyder Java flere typer lister, som du kan bruge til at søge og sortere lagrede data i dine Java-programmer. Denne sidste tutorial i Datastrukturer og algoritmer serien introducerer søgning og sortering med dobbeltkædede lister og cirkulærkædede lister. Som du vil se, bygger disse to datastrukturkategorier på enkeltkædede lister for at tilbyde et bredere udvalg af søge- og sorteringsadfærd i dine Java-programmer.
Dobbeltkædede lister
EN dobbeltkoblet liste er en sammenkædet liste over noder, hvor hver node har et par linkfelter. Et linkfelt giver dig mulighed for at krydse listen i en fremadrettet retning, mens den anden node giver dig mulighed for at krydse listen i en baglæns retning. For fremadretningen indeholder en referencevariabel en reference til den første node. Hver knude linker til den næste knude via det "næste" linkfelt undtagen den sidste knude, hvis "næste" linkfelt indeholder nulreferencen for at angive slutningen af listen (i fremadgående retning). Den bagudgående retning fungerer på samme måde. En referencevariabel indeholder en henvisning til den forreste retnings sidste node, som du fortolker som den første node. Hver node linker til den tidligere node via det "forrige" linkfelt. Den første knudes "forrige" linkfelt indeholder null for at betegne slutningen af listen.
Prøv at tænke på en dobbeltkoblet liste som et par enkeltkædede lister, der hver sammenkobler de samme knudepunkter. Diagrammet i figur 1 viser topForward-henvist og top Bagud-omtalte enkeltlinkede lister.
CRUD-operationer i dobbeltkoblede lister
Oprettelse, indsættelse og sletning af noder er alle almindelige handlinger på en dobbeltkoblet liste. De ligner de operationer, du har lært for enkeltkædede lister. (Husk, at en dobbeltkoblet liste kun er et par enkeltkædede lister, der forbinder de samme knudepunkter.) Følgende pseudokode demonstrerer oprettelse og indsættelse af knudepunkter i den dobbeltkoblede liste vist i figur 1. Pseudokoden viser også knude sletning:
DEKLARER KLASSE Knude DEKLARERER STRING navn DEKLARER Knude næste DEKLARER Knude forrige END DEKLARER DEKLARER Node topForward DECLARE Knude temp DECLARE Knude topBackward topForward = NY Knude topForward.name = "A" temp = NY Knude temp.navn = "B" topBackward = NY Node topBackward .name = "C" // Opret fremad enkeltkædet liste topForward.next = temp temp.next = topBackward topBackward.next = NULL // Opret bagud singly-link liste topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Slet node B. temp.prev.next = temp.next; // Bypass-node B i den fremadgående enkeltlinkede liste. temp.next.prev = temp.prev; // Bypass-node B på den bagudgående enkeltlinkede liste. ENDE Eksempel på anvendelse: CRUD i en dobbeltkoblet liste
Eksemplet Java-applikation DLLDemo demonstrerer, hvordan man opretter, indsætter og sletter noder på en dobbeltkoblet liste. Applikationens kildekode vises i liste 1.
Fortegnelse 1. En Java-applikation, der demonstrerer CRUD på en dobbeltkoblet liste
offentlig endelig klasse DLLDemo {privat statisk klasse Node {String name; Node næste; Node tidligere; } public static void main (String [] args) {// Byg en dobbeltkædet 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 fremad enkeltlistet liste. System.out.print ("Videresend en enkelt linket liste:"); temp = topForward; mens (temp! = null) {System.out.print (temp.navn); temp = temp. næste; } System.out.println (); // Dump bagud enkeltstående link. System.out.print ("Bagudgående enkeltlinket liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.navn); temp = temp. forrige; } System.out.println (); // Referenceknude B. temp = topForward.next; // Slet node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump fremad enkeltlistet liste. System.out.print ("Videresend enkeltstående link (efter sletning):"); temp = topForward; mens (temp! = null) {System.out.print (temp.navn); temp = temp. næste; } System.out.println (); // Dump bagud enkeltstående link. System.out.print ("Bagudgående enkeltlinket liste (efter sletning):"); temp = topBackward; mens (temp! = null) {System.out.print (temp.navn); temp = temp.forrige; } System.out.println (); }} Kompilér liste 4 som følger:
javac DLLDemo.java Kør den resulterende applikation som følger:
java DLLDemo Du skal overholde følgende output:
Fremad enkeltstående link: ABC Tilbage enkeltstående link: CBA Fremad enkeltstående link (efter sletning): AC Bagud enkeltstående liste (efter sletning): CA Bland i dobbeltkædede lister
Java Collections Framework inkluderer en Samlinger klasse af hjælpemetoder, som er en del af java.util pakke. Denne klasse inkluderer en ugyldig blanding (liste liste) metode, der "tillader tilfældigt den specificerede liste ved hjælp af en standard tilfældighedskilde. "For eksempel kan du muligvis bruge denne metode til at blande et kort kort udtrykt som en dobbeltkoblet liste ( java.util.LinkedList klasse er et eksempel). I pseudokoden nedenfor kan du se, hvordan Bland algoritme blander muligvis en dobbeltkoblet liste:
ERKLÆR RANDOM rnd = ny RANDOM DEKLARER INTEGER i FOR i = 3 NED 2 swap (topForward, i - 1, rnd.nextInt (i)) END FOR FUNCTION swap (Node top, int i, int j) DEKLARER node nodei, nodej DEKLARER INTEGER k // Find det node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Find jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Udfør swap. ERKLÆR STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END Shuffle-algoritmen opnår en tilfældighedskilde og krydser derefter listen bagud, fra den sidste node op til den anden. Det bytter gentagne gange en tilfældigt valgt node (som faktisk kun er navnet på feltet) til den "aktuelle position." Noder vælges tilfældigt fra den del af listen, der løber fra den første node til den aktuelle position inklusive. Bemærk, at denne algoritme er groft uddrag af ugyldig blanding (liste liste)kildekode.
Shuffle-algoritmens pseudokode er doven, fordi den kun fokuserer på den fremadgående enkeltlistede liste. Det er en rimelig designbeslutning, men vi betaler en pris for det i tidskompleksitet. Tidskompleksiteten er O (n2). For det første har vi O (n) loop, der kalder bytte rundt(). For det andet indenfor bytte rundt(), vi har de to sekventielle O (n) sløjfer. Husk følgende regel fra del 1:
Hvis f1(n) = O (g(n)) og f2(n) = O (h(n)) derefter (a) f1(n)+f2(n) = max (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). Del (a) beskæftiger sig med sekventielle algoritmer. Her har vi to O (n) sløjfer. Ifølge reglen vil den resulterende tidskompleksitet være O (n). Del (b) omhandler indlejrede algoritmer. I dette tilfælde har vi O (n) ganget med O (nresulterer i O (n2).
Bemærk, at Shuffles rumkompleksitet er O (1), der skyldes de hjælpevariabler, der er deklareret.
Eksempel på anvendelse: Bland i en dobbeltkoblet liste
Det Bland applikation i Listing 2 er en demonstration af Shuffle-algoritmen.
Notering 2. Shuffle-algoritmen i Java
importere java.util.Random; offentlig endelig klasse Shuffle {privat statisk klasse Node {Strengnavn; Node næste; Node tidligere; } public static void main (String [] args) {// Byg en dobbeltkædet 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 fremad enkeltstående link. System.out.print ("Videresend enkeltstående link:"); temp = topForward; mens (temp! = null) {System.out.print (temp.navn); temp = temp.næste; } System.out.println (); // Dump bagud enkeltstående link. System.out.print ("Bagudgående enkeltlinket liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.navn); temp = temp.forrige; } System.out.println (); // Tilfældig liste. Tilfældig rnd = ny tilfældig (); for (int i = 3; i> 1; i--) swap (topForward, i - 1, rnd.nextInt (i)); // Dump fremad enkeltlistet liste. System.out.print ("Videresend enkeltstående link:"); temp = topForward; mens (temp! = null) {System.out.print (temp.navn); temp = temp. næste; } System.out.println (); // Dump bagud enkeltstående link. System.out.print ("Bagudgående enkeltlinket liste:"); temp = topBackward; mens (temp! = null) {System.out.print (temp.navn); temp = temp. forrige; } System.out.println (); } offentlig statisk tomrumsudskiftning (Node top, int i, int j) {// Find det med node. Node nodei = top; for (int k = 0; k <i; k ++) nodei = nodei.next; // Find jth node. Node nodej = top; for (int k = 0; k <j; k ++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; }} Kompilér liste 5 som følger:
javac Shuffle.java Kør den resulterende applikation som følger:
java Shuffle Du skal overholde følgende output fra en kørsel:
Fremad enkeltstående liste: ABC Tilbage enkeltstående liste: CBA Fremad enkeltstående liste: BAC Tilbage enkeltstående link: CAB Cirkulære sammenkædede lister
Linkfeltet i den sidste node på en enkeltkædet liste indeholder et null-link. Dette gælder også i en dobbeltkoblet liste, der indeholder linkfelterne i de sidste noder på de fremadgående og bagudgående enkeltkædede lister. Antag i stedet for, at de sidste noder indeholdt links til de første noder. I denne situation vil du ende med en cirkel-knyttet liste, som er vist i figur 2.
Cirkelbundne lister, også kendt som cirkulære buffere eller cirkulære køer, har mange anvendelser. For eksempel bruges de af operativsystems afbrydere til at buffer tastetryk. Multimedieapplikationer bruger cirkelbundne lister til bufferdata (f.eks. Buffering af data, der skrives til et lydkort). Denne teknik bruges også af LZ77-familien af tabsfri datakomprimeringsalgoritmer.
Sammenkædede lister versus arrays
I hele denne serie om datastrukturer og algoritmer har vi overvejet styrkerne og svaghederne ved forskellige datastrukturer. Da vi har fokuseret på arrays og sammenkædede lister, har du muligvis spørgsmål om disse typer specifikt. Hvilke fordele og ulemper tilbyder sammenkædede lister og arrays? Hvornår bruger du en sammenkædet liste, og hvornår bruger du en matrix? Kan datastrukturer fra begge kategorier integreres i en nyttig hybrid datastruktur? Jeg prøver at besvare disse spørgsmål nedenfor.
Tilknyttede lister tilbyder følgende fordele i forhold til arrays:
- De kræver ikke ekstra hukommelse for at understøtte udvidelse. I modsætning hertil kræver arrays ekstra hukommelse, når udvidelse er nødvendig. (Når alle elementer indeholder dataelementer, kan der ikke føjes nye dataelementer til en matrix.)
- De tilbyder hurtigere indsættelse / sletning af noder end tilsvarende array-baserede operationer. Kun links skal opdateres efter identificering af indsæt / slet-positionen. Fra et matrixperspektiv kræver indsættelse af dataelementer flytning af alle andre dataelementer for at oprette et tomt element. Tilsvarende kræver sletning af et eksisterende dataelement flytning af alle andre dataelementer for at fjerne et tomt element. Al dataelementbevægelse tager tid.
I modsætning hertil tilbyder arrays følgende fordele i forhold til sammenkædede lister:
- Matrixelementer optager mindre hukommelse end noder, fordi elementer ikke kræver linkfelter.
- Arrays giver hurtigere adgang til dataelementer via heltal-baserede indekser.
