Datastrukturer og algoritmer i Java, del 4: Enkelt forbundne lister

Ligesom arrays, der blev introduceret i del 3 i denne tutorial-serie, er sammenkædede lister en grundlæggende datastrukturkategori, som mere komplekse datastrukturer kan baseres på. I modsætning til en række af elementer er a linket liste er en sekvens af noder, hvor hver node er knyttet til den forrige og næste node i sekvensen. Husk at en knude er et objekt oprettet fra en selvhenvisende klasse, og en selvhenvisende klasse har mindst et felt, hvis referencetype er klassens navn. Noder på en sammenkædet liste er knyttet via en nodehenvisning. Her er et eksempel:

 klassemedarbejder {privat int empno; privat strengnavn; privat dobbelt løn offentlig ansat næste; // Andre medlemmer. }

I dette eksempel Medarbejder er en selvhenvisende klasse, fordi dens Næste felt har type Medarbejder. Dette felt er et eksempel på en linkfelt fordi det kan gemme en henvisning til et andet objekt i sin klasse - i dette tilfælde et andet Medarbejder objekt.

Denne vejledning introducerer ind og ud af enkeltlinkede lister i Java-programmering. Du lærer operationer til oprettelse af en enkeltkædet liste, indsættelse af noder i en enkeltkædet liste, sletning af noder fra en enkeltkædet liste, sammenkædning af en enkeltkædet liste til en anden enkeltkædet liste og invertering af en enkeltkædet liste. Vi undersøger også algoritmer, der oftest bruges til sortering af enkeltlænkede lister, og afsluttes med et eksempel, der viser Insertion Sort-algoritmen.

download Hent koden Download de tre eksempler på applikationer til denne artikel. Oprettet af Jeff Friesen til JavaWorld.

Hvad er en enkelt linket liste?

EN enkeltkædet liste er en sammenkædet liste over noder, hvor hver node har et enkelt linkfelt. I denne datastruktur indeholder en referencevariabel en henvisning til den første (eller øverste) node; hver node (undtagen den sidste eller nederste node) linker til den næste; og det sidste knudepunkts linkfelt indeholder nulreferencen for at angive slutningen af listen. Selvom referencevariablen almindeligvis er navngivet top, kan du vælge et hvilket som helst navn, du ønsker.

Figur 1 viser en enkelt forbundet liste med tre noder.

Nedenfor er pseudokode for en enkelt linket liste.

 ERKLÆRING KLASSE Knude ERKLÆRING STRING navn DEKLARER Knude næste SLUT ERKLÆRING ERKLÆRING Knude top = NULL

Node er en selvhenvisende klasse med en navn datafelt og a Næste linkfelt. top er en referencevariabel af typen Node der indeholder en henvisning til det første Node objekt i en enkelt linket liste. Fordi listen endnu ikke findes, topoprindelige værdi er NUL.

Oprettelse af en enkelt linket liste i Java

Du opretter en enkelt linket liste ved at vedhæfte en enkelt Node objekt. Følgende pseudokode opretter en Node objekt, tildeler sin henvisning til top, initialiserer datafeltet og tildeler NUL til sit linkfelt:

 top = NY Knude top.name = "A" top.next = NULL

Figur 2 viser den oprindelige enkeltstående link, der fremgår af denne pseudokode.

Denne operation har en tidskompleksitet på O (1) - konstant. Husk at O (1) udtales "Big Oh of 1." (Se del 1 for en påmindelse om, hvordan tid og rums kompleksitetsmålinger bruges til at evaluere datastrukturer.)

Indsættelse af noder på en enkelt linket liste

At indsætte en node i en enkeltkædet liste er noget mere kompliceret end at oprette en enkeltkædet liste, fordi der er tre tilfælde at overveje:

Indsættelse før den første node.
Indsættelse efter den sidste node.
Indsættelse mellem to noder.

Indsættelse før den første node

En ny node indsættes før den første node ved at tildele topnodens reference til den nye nodes linkfelt og tildele den nye nodes reference til top variabel. Denne handling demonstreres af følgende pseudokode:

 ERKLÆRING Knude temp temp = NY Knude temp.name = "B" temp.next = top top = temp

Den resulterende to-Node listen vises i figur 3.

Denne operation har en tidskompleksitet på O (1).

Indsættelse efter den sidste node

En ny node indsættes efter den sidste node ved at tildele nul til den nye knudepunkts linkfelt, krydser den enkeltkædede liste for at finde den sidste knudepunkt og tildeler den nye knudepunkts reference til den sidste knudepunkts linkfelt, som følgende pseudokode viser:

 temp = NY Knude temp.navn = "C" temp.next = NULL DEKLARE Node temp2 temp2 = top // Vi antager, at top (og temp2) ikke er NULL // på grund af den forrige pseudokode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 refererer nu til den sidste node. temp2.next = temp

Figur 4 viser listen efter indsættelsen af Node C efter Node EN.

Denne operation har en tidskompleksitet på O (n) - lineær. Dens tidskompleksitet kunne forbedres til O (1) ved at opretholde en henvisning til den sidste node. I så fald ville det ikke være nødvendigt at søge efter den sidste node.

Indsættelse mellem to noder

Indsættelse af en node mellem to noder er den mest komplekse sag. Du indsætter en ny node mellem to noder ved at krydse listen for at finde den node, der kommer før den nye node, tildele referencen i den fundne nodes linkfelt til den nye nodes linkfelt og tildele den nye nodes reference til den fundne nodes link Mark. Følgende pseudokode viser disse opgaver:

 temp = NEW Node temp.name = "D" temp2 = top // Vi antager, at den nyoprettede Node indsættes efter Node // A, og at Node A eksisterer. I den virkelige verden er der ingen // garanti for, at der findes en node, så vi bliver nødt til at kontrollere // for temp2, der indeholder NULL i både WHILE-sløjfens overskrift // og efter at WHILE-sløjfen er afsluttet. HVILLIGE temp2.navn NE "A" temp2 = temp2.next END WHILE // temp2 refererer nu til node A. temp.next = temp2.next temp2.next = temp

Figur 5 viser listen efter indsættelsen af Node D mellem Nodes A og C.

Denne operation har en tidskompleksitet på O (n).

Sletning af noder fra en enkelt linket liste

Sletning af en node fra en enkeltkædet liste er også noget mere kompliceret end at oprette en enkeltkædet liste. Der er dog kun to tilfælde at overveje:

Sletning af den første node.
Sletning af en hvilken som helst node undtagen den første node.

Sletning af den første node

Sletning af den første node indebærer at tildele linket i den første node's linkfelt til den variabel, der refererer til den første node, men kun når der er en første node:

 IF top NE NULL THEN top = top.next; // Henvis til den anden node (eller NULL, når der kun er en node). AFSLUT HVIS

Figur 6 viser før og efter visninger af en liste, hvor den første Node er blevet slettet. Node B forsvinder og Node A bliver den første Node.

Denne operation har en tidskompleksitet på O (1).

Sletning af en hvilken som helst node undtagen den første node

Sletning af en hvilken som helst knude, men den første knude involverer lokalisering af den knude, der går forud for den knude, der skal slettes, og tildeling af referencen i knudefeltet, der skal slettes, til det foregående knudefeltets linkfelt. Overvej følgende pseudokode:

 HVIS top NE NULL DANN temp = top MENS temp.navn NE "A" temp = temp.næste END WHILE // Vi antager, at tempreferencer Node A. temp.næste = temp.næste.næste // Knude D findes ikke længere. AFSLUT HVIS

Figur 7 viser før og efter visninger af en liste, hvor et mellemliggende Node slettes. Node D forsvinder.

Denne operation har en tidskompleksitet på O (n).

Eksempel nr. 1: Opret, indsæt og slet på en enkelt linket liste

Jeg har oprettet et Java-program med navnet SLLDemo der demonstrerer, hvordan man opretter, indsætter og sletter noder på en enkelt linket liste. Liste 1 viser applikationens kildekode.

Liste 1. Java-applikationsdemo til enkeltlinkede lister (SSLDemo.java, version 1)

 offentlig endelig klasse SLLDemo {privat statisk klasse Node {Strengnavn; Node næste; } public static void main (String [] args) {Node top = null; // 1. Den enkeltlinkede liste findes ikke. top = ny node (); top.name = "A"; top.next = null; dump ("Sag 1", øverst); // 2. Den enkeltlinkede liste findes, og noden skal indsættes // før den første node. Node temp; temp = ny node (); temp.name = "B"; temp.next = top; top = temp; dump ("Sag 2", øverst); // 3. Den enkeltlinkede liste findes, og noden skal indsættes // efter den sidste node. temp = ny node (); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; mens (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; dump ("Sag 3", øverst); // 4. Den enkeltlinkede liste findes, og noden skal indsættes // mellem to noder. temp = ny node (); temp.name = "D"; temp2 = top; mens (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump ("Sag 4", øverst); // 5. Slet den første node. top = top.næste; dump ("Efter første sletning af node", øverst); // 5.1 Gendan node B. temp = ny Node (); temp.name = "B"; temp.next = top; top = temp; // 6. Slet enhver node undtagen den første node. temp = top; mens (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Efter D-sletning", øverst); } privat statisk ugyldig dump (String msg, Node topNode) {System.out.print (msg + ""); mens (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }}

Kompilér liste 1 som følger:

 javac SLLDemo.java

Kør den resulterende applikation som følger:

 java SLLDemo

Du skal overholde følgende output:

 Sag 1 A Sag 2 B A Sag 3 B A C Sag 4 B A D C Efter første sletning af node A D C Efter D node-sletning B A C

Sammenkædning af enkeltkædede lister

Du skal muligvis lejlighedsvis sammenkæde en enkeltkædet liste til en anden enkeltkædet liste. Antag for eksempel, at du har en liste med ord, der starter med bogstaverne A til M, og en anden liste med ord, der starter med bogstaverne N til Z, og at du vil kombinere disse lister til en enkelt liste. Følgende pseudokode beskriver en algoritme til sammenkædning af en enkelt linket liste til en anden:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Antag kode, der opretter top1-refereret enkeltkædet liste. // Antag kode, der opretter top2-refereret enkeltstående liste. // Sammenkæd top2-refereret liste til top1-refereret liste. IF top1 EQ NULL top1 = top2 END END IF // Find final Node i top1-refereret liste. ERKLÆRING Knude temp = top1 MILJØ temp.næste NE NULL temp = temp.næste END WHILE // Sammenkæd top2 til top1. temp.next = top2 END

I det trivielle tilfælde er der ingen top1-henvist liste, og så top1 er tildelt top2værdi, hvilket ville være NUL hvis der ikke var nogen top2-henvist liste.

Denne operation har en tidskompleksitet på O (1) i det trivielle tilfælde og en tidskompleksitet på O (n) Ellers. Men hvis du opretholder en henvisning til den sidste node, er det ikke nødvendigt at søge på listen efter denne node. tidskompleksiteten ændres til O (1).

Invertering af en enkelt linket liste

En anden nyttig handling på en enkelt linket liste er inversion, som vender listens links for at lade dig krydse dens noder i den modsatte retning. Følgende pseudokode vender top1-henviste liste links:

 DEKLARER Knude p = top1 // Øverst på den oprindelige enkeltstående link. DEKLARER Knude q = NULL // Øverst på den omvendte enkeltstående liste. DECLARE Node r // Midlertidig node-referencevariabel. HVILS p NE NULL // For hver node i den oprindeligt enkelt linkede liste ... r = q // Gem fremtidig efterfølger Nodes reference. q = p // Reference fremtidig forgænger Node. p = p.next // Reference næste knude i den oprindeligt sammenkædede liste. q.next = r // Link fremtidig forgænger Node til fremtidig efterfølger Node. END WHILE top1 = q // Foretag top1 reference først Knude i omvendt enkelt linket liste. ENDE

Denne operation har en tidskompleksitet på O (n).