Progetto APSD 2025/2026 – Libreria di Strutture Dati in Java

Repository del progetto universitario per il corso di Analisi e Progettazione di Strutture Dati (APSD), Università degli Studi di Napoli Federico II, a.a. 2025/2026.

Docenti: M. Benerecetti, F. Mogavero
Titolo dell’esercizio:

“Vettori, liste, deq e insiemi di dati generici”

---

Obiettivo del progetto

Implementare, in Java, una libreria di strutture dati generiche, sia statiche sia dinamiche, per la gestione di:

• vettori (array) di dimensione fissa e/o ridimensionabili
• liste (tipicamente semplicemente / doppiamente collegate)
• pile (stack LIFO)
• code (queue FIFO, eventualmente con varianti)
• deques (double-ended queue)
• insiemi ordinati e non ordinati (set / sorted set)

Tutte le strutture devono essere parametriche sul tipo di dato (generics) e funzionare correttamente con interi, stringhe e tipi definiti dall’utente, nel rispetto delle specifiche del template fornito.

---

Vincoli di implementazione

Il progetto segue scrupolosamente:

1. Il template ufficiale Template.zip fornito dai docenti:

   • stessi nomi di package, file .java, interfacce e classi
   • stessa gerarchia di interfacce e classi
   • stessa organizzazione delle directory (inclusa la cartella zapsdtest/)

2. Il diagramma di interfacce e classi presente in Diagrams.pdf nella root del repository:

   • specifica le principali interfacce (es. strutture generiche, interfacce per collezioni, liste, insiemi, ecc.)
   • specifica le classi concrete che le implementano
   • definisce i principali metodi (nome, firma, semantica a livello di interfaccia)

3. La traccia dell’esercizio riportata nel documento Exercise.pdf:

   • descrive gli obiettivi didattici
   • puntualizza l’obbligo di seguire il template
   • fornisce indicazioni per i test (simpletest, JUnit 5)

L’implementazione non introduce nuove interfacce o classi pubbliche fuori dal diagramma, ma eventualmente solo elementi di supporto interni (private / package-private) dove necessario.

---

Strutture dati implementate

In coerenza con il diagramma del template e con la traccia, la libreria include (in termini generali):

Strutture statiche

• Vettori generici
  • implementati tramite array Java (T[])
  • operazioni tipiche: accesso indicizzato, aggiornamento, dimensione, scansione
  • gestione sicura di indici non validi (eccezioni controllate o runtime secondo specifica)

Strutture dinamiche

• Liste generiche

  • realizzate tramite nodi collegati
  • supporto a inserimento/rimozione in testa, in coda e in posizione intermedia
  • iterazione sugli elementi

• Pile (Stack)

  • implementate sia su array che su lista, secondo quanto previsto dal template
  • operazioni: push, pop, top/peek, test di vuotezza

• Code (Queue)

  • implementazioni tipiche:
    • code su array circolare
    • code su liste
  • operazioni: enqueue, dequeue, front, test di vuotezza

• Deques (Double-Ended Queue)

  • inserimento e rimozione ad entrambe le estremità
  • possibili implementazioni tramite lista doppiamente collegata o array circolare

• Insiemi (Set) di dati generici

  • non ordinati:
    • ad es. implementati tramite tabelle hash o strutture lineari, secondo diagramma
    • operazioni: inserimento, rimozione, appartenenza, cardinalità, iterazione
  • ordinati:
    • ad es. implementati con alberi di ricerca / strutture ordinate, secondo diagramma
    • operazioni: ricerca, inserimento ordinato, rimozione, visita in ordine

Tutte le implementazioni rispettano le interfacce comuni definite dal template, in modo da risultare intercambiabili lato utente.

---

Test e validazione

Il template fornito dai docenti include una semplice suite di test nella directory:

zapsdtest/simpletest

Estensione della suite simpletest

Come indicato nella traccia, i test di partenza:

• sono minimali e servono solo come base di esempio;
• sono stati estesi in questo progetto per:
  • coprire tutti i metodi esposti dalle interfacce principali,
  • testare più casi limite (strutture vuote, strutture piene, uso intensivo),
  • testare diversi tipi parametrici (es. Integer, String, oggetti semplici).

I test sono implementati con JUnit 5 (org.junit.jupiter):

• ogni struttura dati ha una o più classi di test dedicate;
• i test sono automatizzabili tramite build tool (ad es. Maven/Gradle) o eseguibili dall’IDE.

---

Requisiti e compilazione

• Linguaggio: Java (versione coerente con il template, tipicamente Java 8+)
• Framework di test: JUnit 5

Build ed esecuzione in generale

A seconda di come è stato integrato il progetto, sono possibili diversi scenari tipici:

• Compilazione via IDE (IntelliJ IDEA, Eclipse, VS Code):

  • importare il progetto come progetto Java/esistente;
  • assicurarsi che il classpath includa JUnit 5 (se non già previsto dal template);
  • compilare l’intero progetto;
  • eseguire le classi di test nella cartella zapsdtest/simpletest.

• Compilazione via CLI (se forniti script o se si vuole usare javac direttamente):

  • posizionarsi nella root del progetto;
  • compilare rispettando la struttura dei package, includendo JUnit nel classpath;
  • eseguire i test tramite java org.junit.platform.console.ConsoleLauncher ... o strumento equivalente.

I dettagli esatti dipendono dall’organizzazione del template originale (eventuali file pom.xml, build.gradle, script .sh / .bat).

---

Organizzazione del repository

Struttura tipica (semplificata):

ProgettoAPSD/
├─ src/                    # codice sorgente principale (interfacce e classi delle strutture dati)
│  └─ ...
├─ zapsdtest/
│  └─ simpletest/          # suite di test JUnit 5 (fornita e poi estesa)
├─ Diagrams.pdf            # diagramma di interfacce e classi (dal template/docenti)
├─ Exercise.pdf            # traccia ufficiale dell'esercizio
└─ README.md               # questo file

La struttura reale è esattamente quella prescritta in Template.zip, con in più questo README.md e gli eventuali file di configurazione del proprio ambiente di sviluppo.

---

Riferimenti bibliografici

Come da traccia del docente, l’implementazione e le scelte progettuali seguono:

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
   Introduction to Algorithms, MIT Press, 4th Edition, 2022.

   • in particolare le sezioni 10.1 e 10.2.

2. Clifford A. Shaffer,
   Data Structures and Algorithm Analysis, Edition 3.2 (Java Version), 2013.

   • in particolare le sezioni 4.1, 4.2, 4.3 e 4.4.

---

Stato del progetto

Il progetto è stato completato secondo la traccia:

• tutte le interfacce e le classi previste dal template risultano implementate;
• i test unitari simpletest sono stati estesi per aumentare la copertura e individuare errori;
• la struttura delle directory e i nomi dei file seguono rigorosamente il template ufficiale.

Per eventuali migliorie (ottimizzazioni, nuove strategie di implementazione, benchmark, ecc.) è possibile aprire issue o pull request su questo repository.