Dacă implementarea structurii de listă circulară se face prin tehnici de alocare dinamică, se obţine o listă circulară alocată dinamic, sau, simplu o listă circulară dinamică.
    
Declaraţiile tipului "element de listă circulară" în C++:

struct Element {
TipOarecare data; // informatia utila
Element* leg;  // legatura
};
In C va trebui sa scriem:
typedef struct _Element {
TipOarecare data;
struct _Element* leg;
} Element;

Având declaraţiile de mai sus (una din forme), şi

Element* p; // un pointer la Element

în urma unei operaţii:

p = (Element*) malloc( sizeof(Element) ); // in C
sau, simplu
p = new Element; // in C++

p a fost iniţializat cu adresa unei variabile de tip Element alocată în zona de alocare dinamică:

Atunci, acesta din urmă va fi identificat prin expresia *p iar cimpurile sale prin expresiile
p->data si respectiv p->leg.

Pentru a manevra o listă, avem nevoie doar de un pointer la primul element al listei. Pentru a indica o listă vidă acest pointer va primi valoarea 0 (NULL).

Up Home Structura Site   
           

Operaţii în liste circulare

Fară a restrânge generalitatea, vom detalia doar implementarea prin pointeri.
Considerăm declaraţiile de tipuri de mai sus şi variabilele:

Element* cap;      // pointer la primul element al unei liste
Element* p;
Element* q;

Operaţiile primitive pentru acces la o listă înlănţuită sunt:

1. Parcurgerea listei

Consideram: cap - conţine adresa primului element din listă. O parcurgere înseamnă prelucrarea pe rând a tuturor elementelor listei, în ordinea în care acestea apar în listă. Vom avea o variabilaă pointer care va indica pe riând fiecare element al listei:

if (cap!=0){
p=cap;
Prelucreaza p->data;
while (p -> leg -> ! = cap) {
p=p -> leg;
Prelucreaza p -> data;
}

Un caz special apare atunci cind dorim să facem o parcurgere care să se oprească în faţa unui element care să îndeplinească o condiţie (ca în cazul când inserăm un element într-o poziţie dată printr-o condiţie, sau ştergem un element care îndeplineşte o condiţie).
Presupunem că lista are cel puţin un element.
p = cap;
while (p->leg!=cap && !conditie(p->leg))
p = p->leg;


Bucla while se poate opri pe condiţia "p->leg==cap", ceea ce însemnă că nici un element din listă nu îndeplineşte condiţia, iar pointerul p indică ultimul element din listă, sau pe condiţia "conditie(p->leg)", ceea ce însemnă că pointerul p va conţine adresa elementului din faţa primului element care indeplineşte condiţia.

Up Home Structura Site

2. Inserarea unui element în listă

Consideram:

cap - conţine adresa primului element din listă;
q - conţine adresa unui element izolat, care dorim să fie inserat în listă

Fiecare săgeată nou creată însemnă o atribuire: se atribuie varibilei în care săgeata nou creată îşi are originea, valoarea luată dintr-o variabilă în care se află originea unei săgeţi cu aceeaşi destinaţie.
În cazul nostru, avem atribuirile (fiecare atribuire corespunde săgeţii cu acelaşi număr dina):

    (1) parcurge lista (p = adresa elemenului ce conţine în câmpul leg adresa conţinută de pointerul cap)
    (2) p->leg = q;
    (3) q->leg = cap;
    (4) cap=q
           

Up Home Structura Site

Să detaliem:

Prima operaţie:

Parcugerea listei are rolul de a depista elementul care pointează capul listei (conţine în câmpul leg adresa conţinută de pointerul cap). Adresa acestui element va fi conţinută de pointerul p.

A doua operaţie:

p->leg=q

A treia operaţie:

q->leg = cap;

leagă elementul de inserat de restul listei. În urma acestei atribuiri, cap şi q->leg vor indica ambii începutul listei iniţiale (vezi figura de mai jos).

A patra operaţie:

cap = q;

pune în pointerul cap adresa elementului inserat în faţa listei.

Observaţie: Dacă lista în care se face inserţia este vidă, atunci trebuie efectuate câteva modificări în secvenţa 1 - 4, pentru ca rezultatul să fie corect.

Observaţii:

1. Nu se poate face inserarea în faţa unui element dat (prin q) fără a parcurge lista de la capăt.
2. Nu există nici o diferenţă între inserarea în interior, în cazul listelor liniare simplu înlănţuite şi cel al listelor circulare.

Up Home Structura Site

3. Ştergerea unui element din listă

Considerăm: cap - conţine adresa primului element din listă.

[A] Ştergerea la începutul listei.
Prin operaţia de ştergere se înţelege scoaterea unui element din înlănţuire. Elementul care a fost izolat de listă trebuie să fie procesat în continuare, cel puţin pentru a fi eliberată zona de memorie pe care o ocupă, de aceea adresa lui trebuie salvată (să zicem în variabila pointer p).

Observaţii:

1. Atunci când q indică penultimul element dintr-o listă, atribuirile de mai sus funcţionează corect şi sterg ultimul element din listă.                           
2. Nu se poate face ştergerea în faţa unui element dat (prin q), fără a parcurge lista de la capăt.                        
3. Nu există nici o diferenţă între ştergera în interior în cazul listelor liniare simplu înlănţuite şi cel al listelor circulare.

Up Home Structura Site