Vectorii (tablourile de memorie) sunt structuri simple şi eficiente de memorare a obiectelor într-o anumită ordine, dar au şi dezavantaje. Nu sunt foarte adaptabili, de exemplu, inserarea şi ştergerea elementelor sunt dificile deoarece elementele trebuie să fie deplasate pentru a face loc inserţiei sau pentru a umple poziţiile rămase libere după ştergere. De aceea avem nevoie de o alternativă la vectori care să implementeze o secvenţă de elemente. În acest tutorial voi prezenta lista liniară simplu înlănţuită.
O listă simplu înlănţuită este o colecţie de noduri aşezate într-o ordine liniară (dar NU în locaţii succesive din memorie - aşa cum se întâmplă la vectori). Fiecare nod are cel puţin un pointer către următorul nod, pe care îl voi numi next (în imagine este urm). Primul nod se numeşte head (sau prim), iar ultimul nod se numeşte tail (sau ultim), dar bineînţeles că nu există o regulă strictă cu privire la aceste nume (puteţi să le numiţi cum vreţi). Lista se numeşte simplu înlănţuită deoarece fiecare nod memorează un singur pointer către următorul nod. Spre deosebire de vectori, lista nu are o mărime fixă. Poate fi redimensionată prin adăugarea sau ştergerea nodurilor. Gândiţi-vă la un nod ca la un obiect (item) care conţine atât informaţia pe care vreţi s-o stocaţi cât şi legătura către următorul obiect. Pentru a semnala sfârşitul listei folosim NULL. Pointerului next al ultimului nod (nodul terminal) îi atribuim adresa NULL (Pentru cei care folosiţi compilatoare noi, cum ar fi cel din Visual Studio, folosiţi nullptr în loc de NULL, deoarece NULL este doar un simplu macro, este 0, este un întreg şi nu reprezintă concret o adresă inexistentă). Mai jos este o imagine ce ilustrează conceptul de listă simplu înlănţuită (LSÎ):
Implementarea Listei Simplu Înlănţuite
Voi defini o clasă numită Lista, ce implementează LSÎ. Fiecare nod va memora două valori, membrul data care stochează informaţia propriu-zisă (în acest caz va fi un întreg) şi membrul next care este un pointer către următorul nod al listei (legătura).class Lista { public: struct Iterator; // Declaratie forward Lista(); // Constructor - Initializarea listei ~Lista(); // Destructor - Distrugerea listei void push_front(int elem); // Inserare in fata primului nod void push_back(int elem); // Inserare dupa ultimul nod void insert_before(int elem, Iterator nod); // Inserare inainte de nod void insert_after(int elem, Iterator nod); // Inserare dupa nod Iterator search(int value) const; // Lista contine value? void pop_front(); // Elimina nodul din fata void pop_back(); // Elimina ultimul nod void remove(Iterator nod); // Elimina nodul nod Iterator front() const; // Returneaza un iterator catre inceputul listei Iterator end() const; // Returneaza un iterator catre sfarsitul listei bool isEmpty() const; // 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 Lista; // 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; }; };Clasa Nod şi cei doi pointeri sunt privaţi deoarece nu vreau ca utilizatorul clasei să aibă acces direct la ei; nu vreau să fie alteraţi de codul client. De asemenea declar clasa Iterator, pentru a putea parcurge lista (Iterator este membru static public al clasei Lista). De ce fac asta? Deoarece Nod este privat, nu pot folosi un pointer simplu către Lista deoarece ar trebui ca Nod să fie public în acel caz, ori eu nu vreau asta, vreau să respect principiul încapsulării şi să protejez datele interne ale clasei. Dacă Nod ar fi public există riscul ca cel care foloseşte clasa mea să modifice (poate face asta fără să vrea, din greşeală, sau intenţionat) adresa către care pointează next (membrul lui Nod), iar în acest caz lista nu ar mai fi listă, deoarece ar exista o ruptură. Aceeaşi explicaţie pentru head şi tail (aceste detalii ţin de POO, nicidecum de LSÎ, deci pot fi ignorate). Din această cauză implementez clasa Iterator. Dacă tot nu înţelegeţi de ce am declarat această clasă, mai aşteptaţi puţin şi veţi înţelege. Ok, acum să trecem la lista simplu înlănţuită.
Lista vidă
Dacă lista este vidă înseamnă că atât head cât şi tail au valoarea NULL (nullptr). Deci trebuie să testez dacă head este NULL. Funcţia isEmpty() returnează true dacă lista este vidă şi false dacă nu este.bool Lista::isEmpty() const { // Se evalueaza expresia si se returneaza rezultatul return head == nullptr; }
Iniţializarea listei
Voi iniţializa lista în constructorul clasei Lista. Iniţializarea presupune crearea listei vide; head şi tail au valoarea NULL.Lista::Lista() { // Se creeaza lista vida head = tail = nullptr; }
Adăugarea unui nod la listă
Avem 3 cazuri:- Inserarea în faţa primului nod;
- Inserarea după ultimul nod;
- Inserarea în interiorul listei.
void Lista::push_front(int elem) { // Daca lista este vida, atunci if(isEmpty()) { head = new Nod; // Aloc memorie pentru primul nod head->data = elem; head->next = nullptr; // 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; // Leg nod de head head = nod; // nod devine noul head } }
Inserarea după ultimul nod [push_back()]. Şi aici avem cele două cazuri. Dacă lista nu este vidă, adăugăm nodul la sfârşitul listei. Se alocă memorie pentru noul nod p -> Scriu informaţia în nod -> Leg ultimul nod de nodul p -> p devine noul tail (adică p se leagă de NULL şi tail indică acum nodul p).
void Lista::push_back(int elem) { // Daca lista este vida, atunci if(isEmpty()) { head = new Nod; // Aloc memorie pentru primul nod head->data = elem; head->next = nullptr; // 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 = nullptr; // Devenind nod terminal, va fi legat de NULL tail->next = nod; // Fostul tail este legat de noul tail tail = nod; // nod devine tail } }
Inserarea în interiorul listei.
Inserarea după nodul q (unde q este un nod al listei pe care îl obţineţi iterând prin listă). Se alocă memorie pentru noul nod (newNod) -> Leg nodul newNod de succesorul nodului q -> Nodul q se leagă de nodul newNod. Dacă q a fost nod terminal, atunci newNod este acum nod terminal.
void Lista::insert_after(int elem, Iterator nod) { Nod * newNod = new Nod; // Aloc memorie pentru noul nod newNod->data = elem; // Scriu informatia in data newNod->next = nod.list->next; // newNod se leaga de succesorul lui 'nod' nod.list->next = newNod; // Nodul 'nod' se leaga de newNod // Daca nodul 'nod' a fost ultimul nod, atunci nodul newNod devine nod terminal if(newNod->next == nullptr) tail = newNod; }
Chiar dacă am spus nodul nod, nod nu este de fapt Nod, este un obiect Iterator. Prin nodul nod mă refer la nodul încapsulat în obiectul Iterator nod (adică membrul list).
Inserarea înainte de nodul q. Pentru a adăuga nodul newNod înainte de nodul p, ar trebui să leg predecesorul nodului q de newNod, dar eu nu cunosc acest predecesor. În acest caz voi insera nodul newNod după nodul p şi voi interschimba informaţia din cele două noduri dând impresia unei inserări înainte. Algoritmul este acelaşi, dar cu mici modificări.
void Lista::insert_before(int elem, Iterator nod) { Nod * newNod = new Nod; // Aloc memorie pentru noul nod // --- Interschimb informatia --- // newNod->data = nod.list->data; // Copiez informatia din 'nod' in newNod nod.list->data = elem; // 'nod' va memora informatia care trebuie adaugata la lista // ------------------------------ // newNod->next = nod.list->next; // newNod se leaga de succesorul lui 'nod' nod.list->next = newNod; // Nodul 'nod' se leaga de newNod // Daca nodul 'nod' a fost ultimul nod, atunci nodul newNod devine nod terminal if(nod.list == tail) tail = newNod; }Inserţia (cei patru algoritmi) în listă se realizează în timp constant \(O(1)\).
Parcurgerea listei
Lista se parcurge folosind un Iterator. Algoritmul de parcurgere l-am implementat deja în funcţia operator++() (ambele) a clasei Iterator. Ideea este următoarea: Se obţine un pointer (în cazul meu un Iterator) către primul nod (head), apoi se parcurge lista actualizând pointerul (iteratorul) curent cu următorul element (nod = nod->next) până când pointerul curent indică NULL (în cazul meu iteratorul ajunge la end()), adică pointerul curent indică nodul imediat următor după tail.Iterator& operator++() { list = list->next; return *this; }Împreună cu funcţiile front() şi end() putem parcurge lista. Cele două funcţii sunt definite în felul următor:
Lista::Iterator Lista::front() const { return Iterator(head); } Lista::Iterator Lista::end() const { return Iterator(nullptr); }Observaţi că funcţia end() returnează un Iterator ce încapsulează un Nod NULL. Acesta este nodul imediat următor după nodul tail al listei. Deci de fiecare dată când prelucrez lista, voi prelucra informaţiile din intervalul \([front, end)\). Iată algoritmul general de parcurgere a listei:
Lista myList; // declar o lista for(Lista::Iterator iter = myList.front(); iter != myList.end(); iter++) { // Se prelucreaza (*iter) }
Căutarea unui nod în listă
Căutarea este destul de simplă. Pur şi simplu parcurgem lista şi verificăm dacă valoarea care ne interesează se află în nodul curent. Dacă o găsim, returnăm un iterator către acest nod. Căutarea o voi implementa în funcţia search().Lista::Iterator Lista::search(int value) const { for(Nod* it = head; it != nullptr; it = it->next) { if(it->data == value) return Iterator(it); // Daca am gasit nodul il returnez } return end(); // Nu am gasit nimic }
Algoritmul de căutare este liniar $O(n)$
Eliminarea unui nod din listă
Avem 3 cazuri:- Eliminarea primului nod;
- Eliminarea ultimuluiu nod;
- Eliminarea unui nod din interiorul listei.
Eliminarea primului nod [pop_front()]. Sunt câteva cazuri care trebuie luate în considerare: lista este vidă sau lista are un singur nod.
Oricum ar fi, algoritmul general este următorul: Salvez nodul head într-un nod oarecare temp -> Succesorul nodului head devine nod head -> Se eliberează memoria ocupată de obiectul referit de nodul temp (fostul head).void Lista::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 delete temp; // Eliberez memoria ocupata de vechiul obiect head }Algoritmul de eliminare a primului nod este constant $O(1)$.
Eliminarea ultimului nod [pop_back()]
Caut predecesorul nodului tail prin parcurgerea listei -> Predecesorul nodului tail devine nod terminal -> Eliberez zona de memorie ocupată de fostul tail -> Predecesorul devine nod tail.void Lista::pop_back() { if(isEmpty()) throw "Empty List"; // Daca lista este vida if(head == tail) // Daca lista are un singur nod { delete head; head = tail = nullptr; return; } // Caut predecesorul lui tail Nod * pred; for(pred = head; pred->next->next != nullptr; pred = pred->next); // For Vid pred->next = nullptr; // Predecesorul devine nod terminal delete tail; // Eliberez memoria ocupata de vechiul obiect tail tail = pred; // Predecesorul devine tail }Algoritmul de eliminare a ultimului nod este liniar $O(n)$.
Eliminarea unui nod din interiorul listei
Deoarece nu cunosc predecesorul unui nod, eliminarea unui nod înseamnă de fapt eliminarea informaţiei acelui nod. Aşadar, din listă nu va fi eliminat nodul nod ci succesorul său (care este cunoscut), asta după ce informaţia din succesor este salvată în nod. Dacă succesorul nodului nod era nodul tail, atunci nodul nod devine nod tail. Algoritmul este implementat în funcţia remove() care ia ca parametru un obiect de tip Iterator.void Lista::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; // Salvez adresa succesorului lui 'nod' // Copiez toata informatia succesorului in 'nod' nod.list->data = nod.list->next->data; nod.list->next = nod.list->next->next; delete temp; // Eliberez memoria ocupata de succesor; il elimin if(nod.list->next == nullptr) tail = nod.list; }Algoritmul de eliminare al unui nod din interiorul listei este constant \(O(1)\).
Ştergerea listei
Algoritmul pentru eliberarea spaţiului de memorie ocupat de listă (ştergerea listei) este următorul:void Lista::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 }Algoritmul de ştergere a listei este liniar \(O(n)\). Şi să nu uităm de destructorul clasei:
Lista::~Lista() { if(!isEmpty()) clear(); }În continuare vă propun să creaţi un nou fişier Liste.h (header) şi să-l adăugaţi la proiectul vostru, după care în fişierul main (unde aveţi funcţia main) să adăugaţi, la început, directiva: #include "Liste.h". Adăugaţi următorul cod în Liste.h:
class Lista { public: struct Iterator; // Declaratie forward // Constructor - Initializarea listei Lista() { head = tail = nullptr; /*Se creeaza lista vida*/ } // Destructor - Distrugerea listei ~Lista() { if(!isEmpty()) clear(); } void push_front(int elem); // Inserare in fata primului nod void push_back(int elem); // Inserare dupa ultimul nod void insert_before(int elem, Iterator nod); // Inserare inainte de nod void insert_after(int elem, Iterator nod); // Inserare dupa nod Iterator search(int value) const; // Cauta value in lista void pop_front(); // Elimina nodul din fata void pop_back(); // Elimina ultimul nod void remove(Iterator nod); // Elimina nodul nod // Returneaza un iterator catre inceputul listei Iterator front() const { return Iterator(head); } // Returneaza un iterator catre sfarsitul listei Iterator end() const { return Iterator(nullptr); } 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 Lista; // 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 Lista::push_front(int elem) { // Daca lista este vida, atunci if(isEmpty()) { head = new Nod; // Aloc memorie pentru primul nod head->data = elem; head->next = nullptr; // 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; // Leg nod de head head = nod; // nod devine noul head } } void Lista::push_back(int elem) { // Daca lista este vida, atunci if(isEmpty()) { head = new Nod; // Aloc memorie pentru primul nod head->data = elem; head->next = nullptr; // 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 = nullptr; // Devenind nod terminal, va fi legat de NULL tail->next = nod; // Fostul tail este legat de noul tail tail = nod; // nod devine tail } } void Lista::insert_after(int elem, Iterator nod) { Nod * newNod = new Nod; // Aloc memorie pentru noul nod newNod->data = elem; // Scriu informatia in data newNod->next = nod.list->next; // newNod se leaga de succesorul lui 'nod' nod.list->next = newNod; // Nodul 'nod' se leaga de newNod // Daca nodul 'nod' a fost ultimul nod, atunci nodul newNod devine nod terminal if(nod.list == tail) tail = newNod; } void Lista::insert_before(int elem, Iterator nod) { Nod * newNod = new Nod; // Aloc memorie pentru noul nod // --- Interschimb informatia --- // newNod->data = nod.list->data; // Copiez informatia din 'nod' in newNod nod.list->data = elem; // 'nod' va memora informatia care trebuie adaugata la lista // ------------------------------ // newNod->next = nod.list->next; // newNod se leaga de succesorul lui 'nod' nod.list->next = newNod; // Nodul 'nod' se leaga de newNod // Daca nodul 'nod' a fost ultimul nod, atunci nodul newNod devine nod terminal if(nod.list == tail) tail = newNod; } Lista::Iterator Lista::search(int value) const { for(Nod* it = head; it != nullptr; it = it->next) { if(it->data == value) return Iterator(it); // Daca am gasit nodul il returnez } return end(); // Nu am gasit nimic } void Lista::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 delete temp; // Eliberez memoria ocupata de vechiul obiect head } void Lista::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; // Salvez adresa succesorului lui 'nod' // Copiez toata informatia succesorului in 'nod' nod.list->data = nod.list->next->data; nod.list->next = nod.list->next->next; delete temp; // Eliberez memoria ocupata de succesor; il elimin if(nod.list->next == nullptr) tail = nod.list; } void Lista::pop_back() { if(isEmpty()) throw "Empty List"; // Daca lista este vida if(head == tail) // Daca lista are un singur nod { delete head; head = tail = nullptr; return; } // Caut predecesorul lui tail Nod * pred; for(pred = head; pred->next->next != nullptr; pred = pred->next); // For Vid pred->next = nullptr; // Predecesorul devine nod terminal delete tail; // Eliberez memoria ocupata de vechiul obiect tail tail = pred; // Predecesorul devine tail } void Lista::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 }În final, iată un exemplu cu liste:
#include <iostream> #include "Liste.h" using namespace std; int main() { Lista myList; // Declar o lista myList.push_back(4); myList.push_back(3); myList.push_front(7); for(Lista::Iterator it = myList.front(); it != myList.end(); it++) cout << *it << ' '; cout << '\n'; Lista::Iterator p = myList.search(4); myList.insert_after(5, p); myList.insert_before(2, p); for(Lista::Iterator it = myList.front(); it != myList.end(); it++) cout << *it << ' '; cout << '\n'; myList.pop_back(); myList.pop_front(); p = myList.search(4); myList.remove(p); for(Lista::Iterator it = myList.front(); it != myList.end(); it++) cout << *it << ' '; cout << '\n'; myList.clear(); if(myList.isEmpty()) cout << "Lista vida!\n"; system("PAUSE"); return 0; }Output:
7 4 3
7 2 4 5 3
2 5
Lista vida!
Dacă aveţi probleme cu nullptr, atunci folosiţi NULL. De asemenea vă recomand să folosiţi Visual Studio.
Niciun comentariu:
Trimiteți un comentariu
Rețineți: Numai membrii acestui blog pot posta comentarii.