Lista Circulară Simplu Înlanţuită

Lista Circulară Simplu Înlănţuită este aproape similară cu Lista Liniară Simplu Înlănţuită. Diferenţele sunt următoarele: nodul tail (ultim) este legat de nodul head (prim), în acest caz lista nu mai are început sau sfârşit. Vedeţi tutorialul despre listele simplu înlănţuite înainte de a-l citi pe acesta. Mai jos este o imagine ce ilustrează conceptul de listă circulară simplu înlănţuită (LCÎ):

În continuare voi implementa numai algoritmii care diferă faţă de algoritmii listei simplu înlănţuite.

Adăugarea unui nod la listă

Algoritmii sunt aceeiaşi singura diferenţa fiind că ultimul nod va fi legat de primul nod. Mai jos voi implementa algoritmul de eliminare al ultimului nod:

void ListaC::push_back(int elem)
{
    // Daca lista este vida, atunci 
    if(isEmpty()) 
    {
        head = new Nod; // Aloc memorie pentru primul nod
        head->data = elem;
        head->next = head; // Fiind singurul nod, urmatorul este head
        tail = head; // si tail == head
    }
    else  // altfel
    {
        Nod * nod = new Nod; // Aloc memorie pentru noul nod
        nod->data = elem;    // Scriu informatia in data
        nod->next = head;  // Ultimul nod va fi mereu legat de primul
        tail->next = nod;    // Fostul tail este legat de noul tail
        tail = nod;          // nod devine tail
    }
}

Parcurgerea listei

Lista va fi parcursă tot cu Iterator, dar de data aceasta avem nevoie de un nod care să termine lista sau, mai bine zis, parcurgerea. Vom considera nodul head ca nod terminator. Acesta este algoritmul general: Mai întâi prelucrăm nodul prim, apoi prelucrăm toate celelalte noduri până când ajungem din nou la prim (head).

ListaC mylist;
// Mai intai se prelucreaza nodul prim
// *mylist.front()
// Se prelucreaza celelalte noduri
for(ListaC::Iterator it = ++mylist.front(); it != mylist.front(); it++)
{
 // Se prelucreaza *it
}

Nu uitaţi că front() returnează un Iterator.

Eliminarea unui nod din listă

Vom elimina de fapt nodul următor nodului curent q. Trebuie să verificăm dacă succesorul lui q nu este cumva nodul head, caz în care actualizăm nodul head. Voi folosi funcţia searchPrevious() pentru a obţine un iterator către nodul precedent nodului pe care vreau să-l şterg.

void ListaC::remove(Iterator nod)
{
    if(isEmpty()) throw "Empty List"; // Daca lista este vida
    if(head == tail) // Daca lista are un singur nod
    { delete head; head = tail = nullptr; return; } 
    Nod * temp = nod.list->next;
    nod.list->next = nod.list->next->next;
    if(temp == head) head = head->next;
    delete temp;
}

Funcţia searchPrevious():

ListaC::Iterator ListaC::searchPrevious(int value) const
{
    if(head->next->data == value) return front();
    for(Nod* it = head->next; it != head; it = it->next)
    {
        if(it->next->data == value) return Iterator(it); // Daca am gasit nodul il returnez
    }
    return Iterator(nullptr); // Nu am gasit nimic
}

În final, iată clasa ListaC:

class ListaC
{
public:
    struct Iterator; // Declaratie forward
    // Constructor - Initializarea listei
    ListaC() { head = tail = nullptr; /*Se creeaza lista vida*/ }
    // Destructor - Distrugerea listei
    ~ListaC() { if(!isEmpty()) clear(); }  
    void push_front(int elem); // Inserare in fata primului nod
    void push_back(int elem);  // Inserare dupa ultimul nod
    Iterator search(int value) const; // Cauta value in lista
    Iterator searchPrevious(int value) const; // Cauta predecesorul lui value
    void pop_front(); // Elimina nodul din fata
    void remove(Iterator nod); // Elimina nodul nod
    // Returneaza un iterator catre inceputul listei
    Iterator front() const { return Iterator(head); } 
    // Returneaza un iterator catre nodul tail
    Iterator back() const { return Iterator(tail); }
    bool isEmpty() const { return head == nullptr; } // Este lista vida?
    void clear(); // Stergerea completa a listei

private:
    struct Nod  // Clasa Helper; Implementeaza un nod de lista
    {
    int data;   // informatia propriu-zisa
    Nod * next; // urm
    };
    Nod * head; // prim
    Nod * tail; // ultim
public:
    struct Iterator // Un pointer inteligent
    {
        friend class ListaC; // Lista are acces la membrii privati ai lui Iterator
        Iterator() { list = nullptr; }
        Iterator(Nod * ls) { list = ls; }
        // Supraincarc operatorul * (dereferentiere)
        int& operator*() { if(list != nullptr) return list->data; else throw "Null iterator!"; }
        // Prefix - Trec la urmatorul nod
        Iterator& operator++() { list = list->next; return *this; }  
        // Postfix
        Iterator operator++(int) { Iterator temp = *this; ++(*this); return temp; }
        bool operator==(const Iterator& it) const { if(it.list == this->list) return true; else return false; }
        bool operator!=(const Iterator& it) const { if(!(it == *this)) return true; else return false; }
    private:
        Nod * list;
    };
};

void ListaC::push_front(int elem)
{
    // Daca lista este vida, atunci 
    if(isEmpty()) 
    {
        head = new Nod; // Aloc memorie pentru primul nod
        head->data = elem;
        head->next = head; // Fiind singurul nod, urmatorul este head
        tail = head; // si tail == head
    }
    else  // altfel
    {
        Nod * nod = new Nod; // Aloc memorie pentru noul nod
        nod->data = elem;    // Scriu informatia in data
        nod->next = head;    // Leg nod de head
        head = nod;          // nod devine noul head
        tail->next = head;   // Actualizez legatura lui tail
    }
}

void ListaC::push_back(int elem)
{
    // Daca lista este vida, atunci 
    if(isEmpty()) 
    {
        head = new Nod; // Aloc memorie pentru primul nod
        head->data = elem;
        head->next = head; // Fiind singurul nod, urmatorul este NIMIC adica NULL
        tail = head; // si tail == head
    }
    else  // altfel
    {
        Nod * nod = new Nod; // Aloc memorie pentru noul nod
        nod->data = elem;    // Scriu informatia in data
        nod->next = head;  // Ultimul nod va fi mereu legat de primul
        tail->next = nod;    // Fostul tail este legat de noul tail
        tail = nod;          // nod devine tail
    }
}

ListaC::Iterator ListaC::search(int value) const
{
    if(head->data == value) return front();
    for(Nod* it = head->next; it != head; it = it->next)
    {
        if(it->data == value) return Iterator(it); // Daca am gasit nodul il returnez
    }
    return Iterator(nullptr); // Nu am gasit nimic
}

void ListaC::pop_front()
{
    if(isEmpty()) throw "Empty List"; // Daca lista este vida
    if(head == tail) // Daca lista are un singur nod
    { delete head; head = tail = nullptr; return; } 
    Nod * temp = head; // Salvez adresa obiectului head
    head = head->next; // Succesorul lui head devine noul head
    tail->next = head; // Actualizez legatura lui tail
    delete temp; // Eliberez memoria ocupata de vechiul obiect head
}

void ListaC::remove(Iterator nod)
{
    if(isEmpty()) throw "Empty List"; // Daca lista este vida
    if(head == tail) // Daca lista are un singur nod
    { delete head; head = tail = nullptr; return; } 
    Nod * temp = nod.list->next;
    nod.list->next = nod.list->next->next;
    if(temp == head) head = head->next;
    delete temp;
}

void ListaC::clear()
{
    Nod *it = head, *temp; 
    while(it != nullptr)
    {
        temp = it; // Salvez adresa nodului curent
        it = it->next; // Trec mai departe
        delete temp; // Distrug nodul curent
    }
    head = tail = nullptr; // Lista Vida
}

ListaC::Iterator ListaC::searchPrevious(int value) const
{
    if(head->next->data == value) return front();
    for(Nod* it = head->next; it != head; it = it->next)
    {
        if(it->next->data == value) return Iterator(it); // Daca am gasit nodul il returnez
    }
    return Iterator(nullptr); // Nu am gasit nimic
}

Iată un exemplu cu lista circulară simplu înlănţuită:

#include <iostream>
#include "ListaC.h"
using namespace std;

int main()
{
    ListaC mylist;
    mylist.push_back(3);
    mylist.push_back(12);
    mylist.push_front(18);
    mylist.push_front(56);
 
    cout << *mylist.front() << ' ';
    for(ListaC::Iterator it = ++mylist.front(); it != mylist.front(); it++)
    cout << *it << ' ';
    cout << '\n';

    ListaC::Iterator p = mylist.searchPrevious(18);
    mylist.remove(p);
    mylist.pop_front();

    cout << *mylist.front() << ' ';
    for(ListaC::Iterator it = ++mylist.front(); it != mylist.front(); it++)
    cout << *it << ' ';
    cout << '\n';

    system("PAUSE");
    return 0;
}

Output:

56 18 3 12
3 12