Lista recursivă

Listele studiate în secțiunile anterioare au fost concepute ca structuri iterative, cum sunt toate structurile care implementează, direct sau indirect, interfața java.util.Collection. Vom arăta acum că lista înlanțuită poate fi concepută și ca structură recursivă.

Schema unei liste recursive realizată ca structură înlănțuită este reprezentată in figura 8. Lista conține două referințe: una către capul listei care este un obiect, iar alta către coada listei, care este tot o listă. Recursivitatea structurală constă tocmai în faptul că în listă se face referința la o alta listă.


- Figura 8 -

Dacă RLista este o clasă de liste recursive, singurele ei câmpuri sunt:
    private Object cap;
    private RLista coada;
O astfel de structură permite folosirea cu precădere a metodelor recursive.
 
Exemplu
In fișierul RLista.java este dat un exemplu de clasă de listă recursivă. În același fisier există și aplicația TestRLista, în care se testează metodele clasei RLista.

Se poate remarca faptul că în unele din metodele clasei RLista s-a utilizat recursivitatea. Astfel sunt metodele recursive conține, concat si clone. Metodele puneCap, eliminaCap și toString(), deși nu sunt recursive, folosesc totuși în algoritmii lor proprietatea de recursivitate structurală a listei, conform căreia coada listei este tot o listă.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați