Datastrukturer og algoritmer i Java, del 4: Enkelinkede lister

I likhet med matriser, som ble introdusert i del 3 av denne opplæringsserien, er koblede lister en grunnleggende datastrukturkategori som mer komplekse datastrukturer kan baseres på. I motsetning til en sekvens av elementer, imidlertid en koblet liste er en sekvens av noder, der hver node er knyttet til forrige og neste node i sekvensen. Husk at en node er et objekt opprettet fra en selvhenvisende klasse, og en selvhenvisende klasse har minst ett felt hvis referansetype er klassenavnet. Noder i en koblet liste er koblet via en nodereferanse. Her er et eksempel:

 klasse Ansatt {private int empno; privat strengnavn; privat dobbeltlønn; offentlig ansatt neste; // Andre medlemmer. }

I dette eksemplet, Ansatt er en selvhenvisende klasse fordi dens neste feltet har type Ansatt. Dette feltet er et eksempel på en lenkefelt fordi den kan lagre en referanse til et annet objekt i sin klasse - i dette tilfellet et annet Ansatt gjenstand.

Denne opplæringen introduserer inn og ut av enkeltkoblede lister i Java-programmering. Du lærer operasjoner for å lage en enkeltkoblet liste, sette inn noder i en enkeltkoblet liste, slette noder fra en enkeltkoblet liste, sammenkoble en enkeltkoblet liste til en annen enkeltkoblet liste og invertere en enkeltkoblet liste. Vi vil også utforske algoritmer som oftest brukes til å sortere enkeltkoblede lister, og avslutte med et eksempel som viser Insertion Sort-algoritmen.

last ned Få koden Last ned de tre eksemplene på applikasjoner for denne artikkelen. Skapt av Jeff Friesen for JavaWorld.

Hva er en enkeltkoblet liste?

EN enkeltkoblet liste er en koblet liste over noder der hver node har et enkelt lenkefelt. I denne datastrukturen inneholder en referansevariabel en referanse til den første (eller øverste) noden; hver node (unntatt den siste eller nederste noden) lenker til den neste; og den siste nodens lenkefelt inneholder nullreferansen for å indikere slutten på listen. Selv om referansevariabelen ofte heter topp, kan du velge hvilket navn du vil.

Figur 1 presenterer en enkelt koblet liste med tre noder.

Nedenfor er pseudokode for en enkelt koblet liste.

 AVKLARE KLASSE Knutep. ERKLÆRE STRING navn AVKLARE Knutepunkt neste SLUTT ERKLÆRE ERKLÆRING Node topp = NULL

Node er en selvhenvisende klasse med en Navn datafelt og a neste lenkefelt. topp er en referansevariabel av typen Node som har en referanse til det første Node objekt i en enkelt koblet liste. Fordi listen ikke eksisterer ennå, toppstartverdien er NULL.

Opprette en enkelt koblet liste i Java

Du oppretter en enkeltkoblet liste ved å legge ved en singel Node gjenstand. Følgende pseudokode oppretter en Node objekt, tildeler sin referanse til topp, initialiserer datafeltet og tilordner NULL til koblingsfeltet:

 top = NEW Node top.name = "A" top.next = NULL

Figur 2 viser den første enkeltstående lenken som kommer frem fra denne pseudokoden.

Denne operasjonen har en tidskompleksitet på O (1) - konstant. Husk at O (1) uttales "Big Oh of 1." (Se del 1 for en påminnelse om hvordan målinger av tid og romkompleksitet brukes til å evaluere datastrukturer.)

Sette inn noder i en enkelt koblet liste

Å sette inn en node i en enkeltkoblet liste er noe mer komplisert enn å lage en enkeltkoblet liste fordi det er tre tilfeller å vurdere:

Innsetting før den første noden.
Innsetting etter siste node.
Innsetting mellom to noder.

Innsetting før den første noden

En ny node settes inn før den første noden ved å tilordne toppnodens referanse til den nye nodens lenkefelt og tildele den nye nodens referanse til topp variabel. Denne operasjonen demonstreres av følgende pseudokode:

 ERKLÆRING Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp

De resulterende to-Node listen vises i figur 3.

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

Innsetting etter siste node

En ny node settes inn etter den siste noden ved å tilordne null til den nye nodens koblingsfelt, krysse den enkeltkoblede listen for å finne den siste noden, og tilordne den nye nodens referanse til den siste nodens lenkefelt, som følgende pseudokode demonstrerer:

 temp = NY Node temp.navn = "C" temp.next = NULL DEKLARERE Node temp2 temp2 = topp // Vi antar at topp (og temp2) ikke er NULL // på grunn av forrige pseudokode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 refererer nå til den siste noden. temp2.next = temp

Figur 4 viser listen etter innsettingen av Node C etter Node EN.

Denne operasjonen har en tidskompleksitet på O (n) - lineær. Dens tidskompleksitet kan forbedres til O (1) ved å opprettholde en referanse til den siste noden. I så fall ville det ikke være nødvendig å søke etter den siste noden.

Innsetting mellom to noder

Å sette inn en node mellom to noder er det mest komplekse tilfellet. Du setter inn en ny node mellom to noder ved å krysse listen for å finne noden som kommer før den nye noden, tildele referansen i det funnet nodenes lenkefelt til den nye nodenes lenkefelt, og tildele den nye nodenes henvisning til den funnet nodenes lenke felt. Følgende pseudokode demonstrerer disse oppgavene:

 temp = NEW Node temp.name = "D" temp2 = top // Vi antar at den nyopprettede Node setter inn etter Node // A og at Node A eksisterer. I den virkelige verden er det ingen // garanti for at noen node eksisterer, så vi må sjekke // for temp2 som inneholder NULL i både WHILE-sløyfens overskrift // og etter at WHILE-sløyfen er fullført. HELT temp2.navn NE "A" temp2 = temp2.neste SLUTT MENS // temp2 refererer nå til node A. temp.next = temp2.next temp2.next = temp

Figur 5 presenterer listen etter innsettingen av Node D mellom Nodes A og C.

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

Slette noder fra en enkelt koblet liste

Slette en node fra en enkeltkoblet liste er også noe mer komplisert enn å lage en enkeltkoblet liste. Det er imidlertid bare to tilfeller å vurdere:

Sletting av den første noden.
Sletting av en hvilken som helst node bortsett fra den første noden.

Sletting av den første noden

Å slette den første noden innebærer å tilordne lenken i den første nodens lenkefelt til variabelen som refererer til den første noden, men bare når det er en første node:

 HVIS topp NE NULL SÅ topp = topp.neste; // Henvis til den andre noden (eller NULL når det bare er en node). SLUTT OM

Figur 6 presenterer før og etter visninger av en liste der den første Node har blitt slettet. Node B forsvinner og Node A blir den første Node.

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

Sletting av en hvilken som helst node bortsett fra den første noden

Slette en hvilken som helst node, men den første noden, innebærer å lokalisere noden som går foran noden som skal slettes, og tilordne referansen i knutefeltet til noden som skal slettes til det foregående nodens lenkefelt. Tenk på følgende pseudokode:

 HVIS topp NE NULL SÅ temp = topp HVIS temp.navn NE "A" temp = temp.neste END WHILE // Vi antar at tempreferanser Node A. temp.neste = temp.neste.neste // Node D ikke lenger eksisterer. SLUTT OM

Figur 7 viser før og etter visninger av en liste der et mellomliggende Node blir slettet. Node D forsvinner.

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

Eksempel 1: Opprett, sett inn og slett i en enkelt koblet liste

Jeg har opprettet et Java-program som heter SLLDemo som demonstrerer hvordan du oppretter, setter inn og sletter noder i en enkelt koblet liste. Oppføring 1 viser kildekoden til dette programmet.

Oppføring 1. Java-applikasjonsdemo for enkeltkoblede lister (SSLDemo.java, versjon 1)

 offentlig sluttklasse SLLDemo {privat statisk klasse Node {Strengnavn; Node neste; } public static void main (String [] args) {Node top = null; // 1. Den enkeltkoblede listen eksisterer ikke. topp = ny Node (); top.name = "A"; top.next = null; dump ("Sak 1", topp); // 2. Den enkeltkoblede listen eksisterer og noden må settes inn // før den første noden. Node temp; temp = ny Node (); temp.name = "B"; temp.next = topp; topp = temp; dump ("Sak 2", topp); // 3. Den enkeltkoblede listen eksisterer, og noden må settes inn // etter den siste noden. temp = ny Node (); temp.name = "C"; temp.next = null; Node temp2; temp2 = topp; mens (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; dump ("Sak 3", topp); // 4. Den enkeltkoblede listen eksisterer og noden må settes inn // mellom to noder. temp = ny Node (); temp.name = "D"; temp2 = topp; mens (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump ("Sak 4", topp); // 5. Slett den første noden. topp = topp.neste; dump ("Etter første node-sletting", øverst); // 5.1 Gjenopprett node B. temp = ny Node (); temp.name = "B"; temp.next = topp; topp = temp; // 6. Slett en hvilken som helst node bortsett fra den første noden. temp = topp; mens (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Etter D-sletting", ø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 (); }}

Sammensett oppføring 1 som følger:

 javac SLLDemo.java

Kjør den resulterende applikasjonen som følger:

 java SLLDemo

Du bør følge følgende utdata:

 Tilfelle 1 A Tilfelle 2 B A Tilfelle 3 B A C Tilfelle 4 B A D C Etter første node-sletting A D C Etter D node-sletting B A C

Sammenslåing av enkeltkoblede lister

Du kan av og til trenge å sammenkoble en enkeltkoblet liste til en annen enkeltkoblet liste. Anta for eksempel at du har en liste over ord som begynner med bokstavene A til M og en annen ordliste som begynner med bokstavene N til Z, og at du vil kombinere disse listene i en enkelt liste. Følgende pseudokode beskriver en algoritme for sammenkobling av en enkelt koblet liste til en annen:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Anta kode som oppretter top1-referert enkeltkoblet liste. // Anta kode som oppretter topp2-referert enkeltkoblet liste. // Sammenslå topp2-referert liste til topp1-referert liste. IF top1 EQ NULL top1 = top2 END END IF // Finn endelig node i topp1-referert liste. ERKLÆRING Node temp = topp1 MENN temp.neste NE NULL temp = temp.neste SLUTTE MILJØ // Sammenkoble topp2 til topp1. temp.next = top2 END

I det trivielle tilfellet er det ingen topp1-henvist liste, og så topp1 er tildelt topp2verdi, som ville være NULL hvis det ikke var noen topp2-henvist liste.

Denne operasjonen har en tidskompleksitet på O (1) i det trivielle tilfellet og en tidskompleksitet på O (n) ellers. Men hvis du opprettholder en referanse til den siste noden, er det ikke nødvendig å søke i listen etter denne noden. tidskompleksiteten endres til O (1).

Invertere en enkelt koblet liste

En annen nyttig operasjon på en enkelt koblet liste er inversjon, som reverserer lenkene for å la deg krysse nodene i motsatt retning. Følgende pseudokode reverserer topp1lenker til referert liste:

 ERKLÆRING Knutepunkt p = topp1 // Øverst på originalen enkeltkoblet liste. ERKLÆRING Knutepunkt q = NULL // Topp på reversert enkeltkoblet liste. DECLARE Node r // Midlertidig node-referansevariabel. WHILE p NE NULL // For hver node i original enkeltkoblet liste ... r = q // Lagre fremtidig etterfølger Nodes referanse. q = p // Referanse fremtidig forgjenger Node. p = p.next // Referanse neste node i original enkeltkoblet liste. q.next = r // Koble fremtidig forgjenger Node til fremtidig etterfølger Node. END WHILE top1 = q // Gjør top1 referanse først Node i omvendt enkeltkoblet liste. SLUTT

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