Pensieri su una struttura dati personalizzata per un'implementazione nodo / catena

Question

Pensieri su una struttura dati personalizzata per un'implementazione nodo / catena

#1 da (2 voti)
#2 da (1 voti)

2

Sto progettando una semplice GUI che consentirà a un utente di creare un percorso GPX facendo clic ripetutamente su un pannello mappa. Mi trovo di fronte a un dilemma progettuale su come rappresentare i nodi e il percorso. Questo costrutto può essere astratto come segue:

l'utente fa clic su n volte sullo schermo in sequenza per creare una catena di n nodi
dopo che una catena è stata completata, un utente può aggiungere altri nodi ad esso, selezionando i nodi nel mezzo (inserendo tra i nodi esistenti) o semplicemente aggiungendo automaticamente alla fine con il suo clic successivo

All'inizio ero determinato a utilizzare una classe di collezioni Java per rappresentare la catena, ma ci sono difficoltà inaspettate. Sulla superficie, questo sembrerebbe essere un perfetto esempio di LinkedList , ma considera come segue. Se l'utente desidera inserire un nodo nel mezzo della catena, sceglie prima un nodo sullo schermo che desidera inserire prima un nuovo nodo. Se il nodo appartiene a una lista collegata, sarà necessario mantenere un riferimento alla sua lista che comprende (una pratica piuttosto insolita, direi), e anche allora dovremo ancora individuare il nodo nella lista prima di poter inserire . Quindi dobbiamo:

trova il nodo (tempo lineare)
inserisci il nuovo nodo (tempo costante)

O se provo la stessa cosa con un ArrayList , si comporta anche al meglio nel tempo lineare.

trova il nodo (tempo lineare)
inserisci il nuovo nodo (tempo lineare)

Ma nessuno dei due casi sembra davvero desiderabile. Ho flirtato brevemente con l'idea di utilizzare un LinkedHashSet , ma non consente l'inserimento nel mezzo dell'elenco collegato, né sembra fondamentalmente corretto utilizzare un'implementazione impostata per qualcosa di simile.

Quindi ecco cosa mi è venuto in mente:

class Node {
    Node previous;
    Node next;
    Chain chain;
}

Un nodo mantiene solo un riferimento ai suoi nodi precedenti e successivi, così come la catena a cui appartiene (anche in questo caso quest'ultima parte sembra non convenzionale e forse addirittura dispendiosa per me, ma sono convinto che potrebbe essere necessario qui) .

class Chain {
    Node first;
    Node last;
}

La catena conosce solo il suo primo e ultimo nodo.

Ora, se un utente vuole inserire un nodo nel mezzo della catena? Seleziona il nodo, che aggiorna semplicemente il primo / ultimo riferimento di se stesso e dei suoi vicini. Se vuole aggiungere nodi alla fine di una catena? Seleziona semplicemente qualsiasi nodo sullo schermo (che è consapevole della catena a cui appartiene, e quindi di quale sia l'ultimo nodo di quella catena), e la catena inizia immediatamente ad aggiornare i riferimenti di collegamento per l'ultimo nodo e ogni nodo aggiunto dopo di essa, come oltre a mantenere aggiornato il proprio "ultimo" riferimento.

Volevo davvero usare una classe Collections, ma questo approccio mi sembra migliore. Ma mi piacerebbe qui pensieri / critiche da parte di programmatori più esperti. Grazie.

design java collections data-structures

posta The111 12.01.2013 - 02:33

fonte

2 risposte

2

Sicuramente vuoi sfruttare la funzionalità di "manutenzione degli elenchi" fornita da Java. Vai prima con facilità d'uso e preoccupati delle prestazioni in seguito. "pre-ottimizzazione" è un cane che insegue la coda.

Class Waypoint {
    string name;
    double lat;  // I'm not saying double is necessarily the ideal type here.
    double long;
    // other stuff as needed for GPX

   RouteCollection myRoutes; // all the routes containing this waypoint
}

Class Route {
    LinkedList<Waypoint> myRoute;
    string name;
    Waypoint start { return myRoute[0]; }
    Waypoint end { return myRoute[myRoute.Length-1] };
}

Class RouteCollection {
    ArrayList<Route> myRoutes;
    // maybe a dictionary/hash instead, the key being the Route.name perhaps
    // order is not important in this collection, I suspect.
}

Class WaypointJanitor {
    // keeps cross references in the various classes in sync
    // for example updates the Waypoint.myRoutes when a Route object is edited

    // I can see the main add/delete/insert functionality in this class,
    // passing routes & waypoint parameters. And all the complexity is contained, keeping your data structure classes clean and simple.
}

L'interfaccia utente fornisce il contesto per l'inserimento

If the node belongs to a linked list, it will need to maintain a reference to its encompassing list

"se il nodo appartiene .." Questo è confuso. Mi sembra che nell'interfaccia utente creo percorsi / catene / tracce esplicitamente, dando a ciascuno un nome probabilmente. Quindi non ci sono dubbi. Quando voglio inserire un waypoint, indico attraverso l'interfaccia utente quale percorso sto manipolando. Inoltre, qualsiasi waypoint (coordinata lat / long arbitraria) potrebbe essere parte di un numero qualsiasi di route; selezionando esplicitamente la rotta da modificare non c'è ambiguità.

risposta data 12.01.2013 - 06:30

fonte

Leggi altre domande sui tag design java collections data-structures

Come eseguire il debug di un'applicazione basata su swing in modo efficace Problema Comprensione della definizione IEEE di Ingegneria del software

score 1 · Accepted Answer

I riferimenti circolari mutevoli sono cattivi. Basta usare un ArrayList e non preoccuparti.

Puoi vedere tutti gli elementi sullo schermo : non sarà così lungo che il tempo lineare impiega qualsiasi momento.

È necessario chiedere una spiegazione perché i riferimenti circolari mutevoli sono sgradevoli: come nel codice errato. È un uso inefficiente di programmatore-pensiero-tempo, non inevitabilmente problematico.