Implicit data structure
data structure that stores very little information other than the main or required data
In computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low overhead. They are called "implicit" because the position of the elements carries meaning and relationship between elements; this is contrasted with the use of pointers to give an explicit relationship between elements. Definitions of "low overhead" vary, but generally means constant overhead; in big O notation, O(1) overhead. A less restrictive definition is a succinct data structure, which allows greater overhead.
Definition
An implicit data structure is one with constant O(1) space overhead (above the information-theoretic lower bound).
Historically, Munro & Suwanda (1980) defined an implicit data structure (and algorithms acting on one) as one "in which structural information is implicit in the way data are stored, rather than explicit in pointers." They are somewhat vague in the definition, defining it most strictly as a single array, with only the size retained (a single number of overhead), or more loosely as a data structure with constant overhead (O(1)). This latter definition is today more standard, and the still-looser notion of a data structure with non-constant but small o(n) overhead is today known as a succinct data structure, as defined by Jacobson (1988); it was referred to as semi-implicit by Munro & Suwanda (1980).
A fundamental distinction is between static data structures (read-only) and dynamic data structures (which can be modified). Simple implicit data structures, such as representing a sorted list as an array, may be very efficient as a static data structure, but inefficient as a dynamic data structure, due to modification operations (such as insertion in the case of a sorted list) being inefficient.
Examples
A trivial example of an implicit data structure is an array data structure, which is an implicit data structure for a list, and requires only the constant overhead of the length; unlike a linked list, which has a pointer associated with each data element, which explicitly gives the relationship from one element to the next.
This brief starts where responsible research should: with the source description of “Implicit data structure” as data structure that stores very little information other than the main or required data. Everything that follows is an evidence route, not borrowed authority.
Why this record matters
The subject matters to the general reference register because the source frames it as data structure that stores very little information other than the main or required data. Its deeper value depends on whether names, dates, institutions and citations support that framing.
The citation trail is more important than the brevity of the summary: it shows where individual claims can be examined in context. The source revision retrieved here is dated Aug 4, 2026. The linked authority identifier is Q16707838. None of the 0 selected statements returned an explicit reference. The first chronological checks are 1980 and 1988.
Overview language is designed for orientation and should not be treated as a substitute for the evidence cited beneath it. The source lead contains qualifying language; that uncertainty should survive quotation, summary and reuse. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Implicit data structure”, its source revision and the description used here.
- Expand the search: follow Implicit data structure primary sources, Implicit data structure archive and Implicit research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Implicit data structure”?
- What terminology or title could unlock a more precise catalogue search?
- Which cited source is closest to the event, object or claim?
Search terms from this dossier
This entry incorporates text from “Implicit data structure” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.