Listmap

Listmap is a data structure that stores associations from keys to lists of values, combining a map with a collection of values per key. It enables one key to be related to multiple values and supports standard map operations while allowing accumulation of multiple entries for each key.

Typical operations include: add or append(key, value) to place a value into the key’s list; get(key) to retrieve the list of values for a key (often returning an empty list if the key is absent); remove(key, value) to delete a specific value from a key’s list; removeAll(key) to discard all values for a key; and contains(key, value) to test membership. Additional helpers such as keys(), values(key), and totalCount (the total number of stored key-value pairs) are common. In many implementations, lists per key are ordered by insertion, and duplicates may be allowed unless explicitly suppressed.

Implementation and complexity: a Listmap is usually built by wrapping a standard map from keys to lists. The per-key lists can be implemented with dynamic arrays or linked lists. Insertion and retrieval are typically O(1) on average for the map lookup, with the per-key list operations depending on the chosen list representation. Memory usage grows with the number of distinct key-value pairs.

Common use cases include representing one-to-many relationships, such as indexing terms to document positions, event listeners by event type, or grouping items by category. Related concepts include multimaps and inverted indexes.