Strutture Dati Dinamiche

#include <iostream>
using namespace std;
int main() {
    int x = 42;
    int* p = &x;  // p ora contiene l'indirizzo di memoria di x

    cout << x    << endl;  // 42       — valore di x letto direttamente
    cout << &x   << endl;  // 0x...    — indirizzo di x in memoria (esadecimale)
    cout << p    << endl;  // 0x...    — contenuto di p: lo stesso indirizzo di &x
    cout << *p   << endl;  // 42       — *p: vai all'indirizzo in p e leggi il valore

    *p = 100;  // vai all'indirizzo in p (= &x) e SCRIVI 100 in quella cella.
              // Equivale a "x = 100" ma fatto tramite puntatore.
              // Questo dimostra la dereferenziazione in scrittura.
    cout << x    << endl;  // 100      — x è cambiato perché p puntava a lui
    return 0;
}

int* p = new int;       // riserva spazio per un int in heap, restituisce l'indirizzo
*p = 42;                 // scrivi 42 nella cella appena allocata
cout << *p << endl;      // 42
delete p;                 // OBBLIGATORIO: libera la memoria, altrimenti memory leak
p = nullptr;             // buona prassi: evita uso accidentale dopo delete

int* q = new int(99);   // alloca e inizializza in un solo passo
delete q; q = nullptr;

int* p = nullptr;   // puntatore che non punta a nessun indirizzo valido
if (p != nullptr) {
    cout << *p;     // sicuro: accediamo solo se p è valido
}
// dereferenziare nullptr = segmentation fault a runtime

struct Nodo {
    int   valore;   // campo dati: il valore intero memorizzato nel nodo
    Nodo* next;     // puntatore al nodo successivo (nullptr = fine catena)
};                  // la struct si riferisce a sé stessa: struttura ricorsiva

Nodo* n1 = new Nodo;   // alloca un nodo in heap, restituisce l'indirizzo → n1
n1->valore = 15;       // tramite n1, scrivi 15 nel campo valore di quel nodo
n1->next   = nullptr;  // tramite n1, nessun successore per ora

Nodo* n2 = new Nodo;   // alloca un secondo nodo in heap → n2
n2->valore = 8;        // scrivi 8 nel campo valore di n2
n2->next   = nullptr;  // n2 è l'ultimo nodo: nessun successore

n1->next = n2;          // collega i nodi: n1→next ora punta a n2 → catena n1→n2→nullptr

cout << n1->valore        << endl;  // legge n1.valore        → 15
cout << n1->next->valore  << endl;  // n1->next è n2, quindi n2.valore → 8

Nodo* curr = testa;   // curr inizia dalla testa della lista
while (curr != nullptr) {   // continua finché non si raggiunge la fine
    cout << curr->valore << " ";
    curr = curr->next;        // avanza: curr ora punta al nodo successivo
}
// il ciclo termina quando curr è nullptr: nessun successore

#include <iostream>
using namespace std;
struct Nodo { int valore; Nodo* next; };

// inserimento in testa — O(1)
void inserisciTesta(Nodo*& testa, int val) {
    Nodo* nuovo  = new Nodo;
    nuovo->valore = val;
    nuovo->next   = testa;  // nuovo → vecchio primo
    testa         = nuovo;
}

// inserimento in coda — O(n)
void inserisciCoda(Nodo*& testa, int val) {
    Nodo* nuovo = new Nodo;
    nuovo->valore = val; nuovo->next = nullptr;
    if (testa == nullptr) { testa = nuovo; return; }
    Nodo* curr = testa;
    while (curr->next != nullptr) curr = curr->next;
    curr->next = nuovo;
}

// inserimento ordinato (crescente) — O(n)
void inserisciOrdinato(Nodo*& testa, int val) {
    Nodo* nuovo = new Nodo;
    nuovo->valore = val; nuovo->next = nullptr;
    if (testa == nullptr || val <= testa->valore) {
        nuovo->next = testa; testa = nuovo; return;
    }
    Nodo* curr = testa;
    while (curr->next != nullptr && curr->next->valore < val)
        curr = curr->next;  // confronto su curr->NEXT->valore, non curr->valore
    nuovo->next = curr->next;  // PRIMA: nuovo punta al resto (due puntatori allo stesso nodo)
    curr->next  = nuovo;       // DOPO: curr punta a nuovo (se invertissi perderei il resto!)
}

// cancellazione per valore — O(n)
void cancella(Nodo*& testa, int val) {
    if (testa == nullptr) return;
    if (testa->valore == val) {
        Nodo* tmp = testa; testa = testa->next; delete tmp; return;
    }
    Nodo* curr = testa;
    while (curr->next != nullptr && curr->next->valore != val)
        curr = curr->next;
    if (curr->next != nullptr) {
        Nodo* tmp = curr->next;
        curr->next = tmp->next;
        delete tmp;
    }
}

void libera(Nodo*& testa) {
    while (testa != nullptr) {
        Nodo* tmp = testa; testa = testa->next; delete tmp;
    }
}

struct Nodo { int valore; Nodo* next; };
struct Stack { Nodo* top; };

void init(Stack& s)    { s.top = nullptr; }
bool isEmpty(Stack& s) { return s.top == nullptr; }

void push(Stack& s, int val) {
    Nodo* nuovo   = new Nodo;
    nuovo->valore = val;
    nuovo->next   = s.top;  // nuovo punta al vecchio top
    s.top         = nuovo;
}

int pop(Stack& s) {
    if (isEmpty(s)) { cout << "Errore!" << endl; return -1; }
    int   val = s.top->valore;
    Nodo* tmp = s.top;
    s.top     = s.top->next;
    delete tmp;
    return val;
}

#include <iostream>
using namespace std;

/* Nodo: il mattone base, identico alla lista concatenata */
struct Nodo {
    int   valore;  // dato memorizzato
    Nodo* next;    // puntatore al successivo (nullptr = fine catena)
};

/* Non serve una struct Coda: bastano due puntatori separati.
   testa → nodo da cui si estrae (dequeue) — avanza verso destra
   coda  → nodo dove si inserisce (enqueue) — avanza verso destra
   Le funzioni li ricevono per riferimento (&) perché devono modificarli nel chiamante. */

bool isEmpty(Nodo* testa) {
    return testa == nullptr;   // coda vuota se testa non punta a nessun nodo
}

void enqueue(Nodo*& testa, Nodo*& coda, int val) {
    Nodo* nuovo   = new Nodo;  // alloca il nodo in heap
    nuovo->valore = val;         // inizializza il dato
    nuovo->next   = nullptr;    // è l'ultimo: nessun successore
    if (isEmpty(testa)) {
        testa = coda = nuovo;    // primo nodo: testa e coda coincidono
        return;
    }
    coda->next = nuovo;          // aggancia nuovo in fondo alla catena
    coda       = nuovo;          // coda avanza al nuovo ultimo nodo
}

int dequeue(Nodo*& testa, Nodo*& coda) {
    if (isEmpty(testa)) { cout << "Errore!" << endl; return -1; }
    int   val  = testa->valore;  // salva il valore da restituire
    Nodo* tmp  = testa;          // segnaposto: serve per fare delete dopo
    testa      = testa->next;    // testa avanza al nodo successivo
    if (testa == nullptr)
        coda = nullptr;         // coda svuotata: anche coda → nullptr (altrimenti punta a memoria liberata!)
    delete tmp;                  // libera il nodo rimosso — FONDAMENTALE
    return val;
}

int main() {
    Nodo* testa = nullptr;       // coda vuota all'inizio
    Nodo* coda  = nullptr;

    enqueue(testa, coda, 5);     // testa → [5|∅] ← coda
    enqueue(testa, coda, 3);     // testa → [5|→] → [3|∅] ← coda
    enqueue(testa, coda, 8);     // testa → [5|→] → [3|→] → [8|∅] ← coda
    cout << dequeue(testa, coda) << endl;  // estrae 5, delete, testa avanza a [3]
    cout << dequeue(testa, coda) << endl;  // estrae 3, delete, testa avanza a [8]
    return 0;
}