Esiste una struttura dati per questo tipo di elenco / mappa?

Stai cercando un NavigableMap . Questo è un sottotipo di SortedMap che ha anche alcune funzioni disponibili oltre alla natura della mappa che viene ordinata. Si noti che la mappa navigabile "è destinata a sostituire l'interfaccia SortedMap." ( Miglioramenti del framework Raccolte Java SE 6 ). Tutto ciò che attualmente implementa SortedMap implementa NavigableMap e probabilmente rimarrà vero.

In particolare, il metodo floorKey(K key) che "restituisce la chiave più grande minore o uguale alla chiave data, o null se non esiste una chiave di questo tipo.

Questo è solo uno dei tanti metodi che ti permettono di ottenere chiavi o submap specifici della mappa.

• ceiling / floor (la voce che è superiore / inferiore al parametro)
• accesso delle chiavi o mappa in ordine decrescente
• head / tail (le voci in ordine minore / maggiore di una determinata chiave)
• superiore / inferiore (il prossimo tasto più alto o più basso del parametro)
• submap (date due chiavi, restituisce la mappa che si trova tra le due chiavi)

Java ha due implementazioni di NavigableMap - la TreeMap e ConcurrentSkipListMap .

Se guardi l'idea / l'implementazione di una skip list vedrai perché funzionerebbe davvero bene con una struttura e le sue query.

Quello che stai cercando è una tabella dei simboli che supporta le operazioni ordinate. E nel tuo caso è l'operazione del piano.

L'implementazione hash di una tabella di simboli è la più veloce, ma non offre quelle operazioni ordinate.

Ma l'implementazione dell'albero delle tabelle dei simboli lo fa. Un esempio di ciò in Java è la classe TreeMap