Hvordan Rekursivt Traverse i en lenket liste

Den lenket liste datastruktur er et kraftig alternativ til enkle matriser. I motsetning til matriser, kan data raskt kan legges til og fjernes fra en lenket liste uten å opprette en liste ett element om gangen. Men i motsetning til arrays, kan bare nås data i en lenket liste i orden. Du kan gjøre dette med en enkel sløyfe eller med en rekursiv (eller selv calling) -funksjonen. Dette vil bli skrevet i Java, men koden kan implementeres i alle språk med kun mindre modifikasjoner for å dekke syntaks forskjeller.

Bruksanvisning

1 Åpne en teksteditor.

2 Lim inn følgende Java-kode:

public class RecursiveLLTraverser {

public static void traverseList(LinkedList l) {

}

}

All koden vil gå innenfor "traverseList" metoden.

3 Lim inn følgende på innsiden av "traverseList" metoden:

if (l.size () == 0) return;

if (l.size ()> 0) {

LinkedList n = l.clone();

Object o = n.removeFirst ();

o.doSomething ();

traverseList (n);

}

Dette tar en lenket liste, og gjør et grunt klone av det med det første elementet fjernet (og noen behandling utføres på det.) Det klone blir deretter kjørt gjennom traversen List selv. Etter hvert vil klon være tom, i hvilket tilfelle traversen List metoden vil bare gå tilbake.

Hint

• Alle rekursive algoritmer krever minst to tilfeller: en base case, som må returnere, og en rekursiv case, noe som reduserer datastørrelsen til noe mer letthåndterlig. En vanlig feil i rekursive metoder er å glemme base case. Dette fører til en uendelig løkke som til slutt krasjer når datamaskinen går ut av stabelen plass.
• Rekursive metoder avhenge en systeminnstilling som heter "stack size" som endres med operativsystemet og språket. Denne delen av minnet holder styr på alle kjørende metoder. Forsøk på en rekursiv algoritme på en svært lang liste kan produsere stakkfeil.