* Conoscenza del computer >> sistemi >  >> Windows 2016

Struttura dati per foglio di calcolo in Java: Liste collegate vs Array 2D

Il problema degli array 2D

Un array bidimensionale (`String[][]`) sembra la scelta ovvia per una griglia foglio-calcolo, ma inserire/eliminare righe o colonne richiede O(n×m) perché Java deve ricreare l'intera struttura. Inaccettabile per fogli dinamici.

Soluzione: Lista collegata di liste collegate

Una `LinkedList>` permette:

  • Inserimento/rimozione righe: O(1) (solo riallocazione puntatori)
  • Inserimento/rimozione colonne: O(righe) (scansione liste interne)
  • Ridimensionamento: naturale, senza ricopiatura massiva

Trade-off: accesso cella casuale `get(x,y)` diventa O(x+y) vs O(1) dell'array. Accettabile se le operazioni strutturali sono frequenti.

Implementazione core (estratto)

public class Spreadsheet {
    private LinkedList> data = new LinkedList<>();

    public Spreadsheet() { addRow(); addColumn(); } // almeno 1x1

    public void addRow() { data.addLast(new LinkedList<>()); }
    public void addRow(int index) { data.add(index, new LinkedList<>()); }
    public void removeRow(int index) { data.remove(index); }

    public void addColumn() { 
        for (LinkedList row : data) row.addLast(""); 
    }
    public void addColumn(int index) { 
        for (LinkedList row : data) row.add(index, ""); 
    }
    public void removeColumn(int index) { 
        for (LinkedList row : data) row.remove(index); 
    }

    public void setCell(int x, int y, String val) { data.get(x).set(y, val); }
    public int getWidth()  { return data.isEmpty() ? 0 : data.getFirst().size(); }
    public int getHeight() { return data.size(); }
    // toString() per stampa tabellare...
}

Quando usare quale

ScenarioStruttura consigliata
Foglio statico, solo lettura/scrittura celleArray 2D o `ArrayList`
Inserimenti/eliminazioni righe/colonne frequentiLinkedList di LinkedList
Foglio enorme (10k+ righe), accesso casuale criticoLibreria specializzata (Apache POI, JExcelApi)

Windows 2016