List (computing)¶

A finite ordered collection whose positions remain distinct even when values repeat, exposed through sequence operations independently of its concrete array or linked representation.

Version: v1 · 2026-09-28 · History
Domain-specific #: 10440
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Data Structures, Abstract Data Types → Computer Science & Software Engineering

Core Idea¶

A computing list is an abstract finite sequence. Its items occupy a particular order, repeated values remain separate occurrences, and the interface supports constructing, traversing, selecting, and transforming the sequence. Empty list plus a constructor such as cons gives an inductive definition in many functional settings.

The abstract data type is not identical to a linked list. Arrays, dynamic arrays, linked nodes, balanced trees, and specialized compressed layouts can all implement ordered sequence behavior with different costs. The abstraction barrier lets clients reason about order and operations while implementations choose storage and performance tradeoffs.

Operations reveal different aspects of the contract: head and tail expose recursive structure; indexing exposes position; append combines sequences; map preserves shape while transforming values; filter changes membership while preserving relative order; fold summarizes a traversal. Their cost depends on representation even when their extensional result agrees.

Structural Signature¶

Sig role-phrases:

finite ordered positions. Give every occurrence a place in a bounded sequence. Constitutive carrier. If altered: Removing order yields a bag or set rather than a list.
item occurrences. Occupy positions and retain distinct occurrence identity even when values compare equal. Constitutive contents. If altered: Collapsing duplicate values changes length and sequence behavior.
constructors. Create the empty list and extend or assemble lists through operations such as cons, append, or literals. Constitutive formation interface. If altered: Without a formation rule the datatype has no closed population of values.
observers and transformers. Expose head, tail, indexing, traversal, map, filter, fold, or concatenation according to the interface. Characteristic operational interface. If altered: An operation that ignores order may be valid but does not exhaust list semantics.
representation boundary. Allows arrays, linked nodes, trees, or compressed layouts to implement the same abstract sequence contract. Identity-preserving abstraction barrier. If altered: Leaking representation assumptions makes code fail when implementation changes.

What It Is Not¶

Not a set. Order and duplicate occurrences are load-bearing.
Not necessarily a linked list. Linked nodes are one concrete representation of the abstract sequence.
Not necessarily an array. Random access and contiguous storage are not required by list identity.
Not a stream. A list is finite, while a stream may be potentially infinite or incrementally produced.

Scope of Application¶

The abstraction applies wherever software needs a finite ordered, multiplicity-preserving collection behind a declared sequence interface.

Functional programming. Uses nil-and-cons recursion and folds.
Collections libraries. Exposes sequence operations behind implementations.
Parsing. Stores ordered tokens, nodes, or alternatives.
Application data. Maintains user-visible ordering and duplicates.
Algorithm analysis. Compares operation costs across representations.

Clarity¶

The list abstraction separates extensional sequence behavior from storage layout. It prevents ‘list’ in an API from silently implying linked nodes, constant-time indexing, uniqueness, sortedness, or infinite laziness—properties that must be specified separately.

Manages Complexity¶

Collections differ along order, multiplicity, finiteness, access, update, and representation. Naming the list contract fixes the first three and exposes the remaining choices, allowing correctness arguments to remain stable while performance analysis follows the concrete implementation.

Abstract Reasoning¶

Check finiteness, order preservation, and duplicate-occurrence identity first.
State the constructor and observer operations promised by the interface.
Reason extensionally about sequence results before choosing a representation.
Analyze time, space, persistence, and locality against the selected implementation.
Test boundary cases including empty lists, repeated values, and representation changes.

Knowledge Transfer¶

List laws transfer literally across programming languages and representations when finite order and occurrence multiplicity are preserved. Performance expectations do not: append, indexing, and insertion can change complexity between arrays and linked implementations. Outside computing, an everyday written list is analogous unless it instantiates the formal sequence operations.

Examples¶

Canonical¶

The value [a, b, a] has length three: the first and third occurrences are distinct positions despite equal values. Mapping a function produces three ordered results, and filtering preserves the relative order of survivors.

Mapped back: finite ordered positions → positions 0, 1, 2; item occurrences → two distinct occurrences of a; constructors → list literal; observers and transformers → length, map, and filter; representation boundary → no storage layout assumed.

Applied / In Practice¶

A library replaces a linked-list implementation with a dynamic array while retaining the same list interface. Client results remain ordered and duplicate-preserving, but indexing becomes cheaper and insertion costs change, demonstrating the split between semantics and representation.

Mapped back: finite ordered positions → unchanged sequence; item occurrences → same values and duplicates; constructors → same public creation API; observers and transformers → same extensional operations; representation boundary → linked nodes replaced by array.

Structural Tensions¶

T1: abstract contract vs. representation cost. One list interface supports several layouts whose operation complexities differ sharply. Diagnostic: Which guarantees are semantic and which are performance-specific?

T2: positional access vs. structural recursion. Index-oriented and head-tail views favor different algorithms and implementations. Diagnostic: Does the workload navigate by position or decompose from an end?

T3: immutability vs. update efficiency. Persistent lists share structure safely while mutable arrays can offer compact in-place updates. Diagnostic: Which ownership and history guarantees does the program require?

Structural–Framed Character¶

Computing list is structural-leaning. Finite sequence laws are formal, while syntax, libraries, and performance contracts are language artifacts. It is non-evaluative but strongly embedded in programming practice. Vocabulary transfers among languages when contracts align; everyday list usage is looser. Its character: a finite ordered collection contract decoupled from storage representation.

Structural Core vs. Domain Accent¶

Skeletal core. A finite index order maps positions to item occurrences while preserving multiplicity.

Domain-bound accent. Data types, constructors, iterators, recursion, arrays, linked nodes, and complexity guarantees define the computing object.

Why not prime. Ordered collection structure travels, but the list ADT is constituted by programming interfaces and representation choices.

This entry is a kind of Data Structure.

Sequence. A list is a finite, operation-bearing realization of ordered sequence structure.
Abstraction barrier. Clients depend on list behavior rather than linked or contiguous storage details.
No canonical parent edge is asserted in the current DAG.

Relationships to Other Abstractions¶

Current abstraction List (computing) Domain-specific

Parents (1) — more general patterns this builds on

List (computing) is a kind of Data Structure Prime

List (computing) is a strict kind of Data Structure: its frozen identity entails the parent's defining structure while adding domain-specific restrictions.

Children (1) — more specific cases that build on this

Self-Organizing List Domain-specific is a kind of List (computing)

An access-updated sequential list is a restricted kind of finite ordered computing list.

Hierarchy path (1) — routes to 1 parentless root

List (computing) → Data Structure → Trade-offs → Constraint

Neighborhood in Abstraction Space¶

List (computing) sits in a crowded region of the domain-specific corpus (33^rd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Abstract Algebra & Category Theory (24 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Linked list. Tell: Is the term naming the abstract sequence or one node-and-pointer representation?
Array. Tell: Are contiguous storage and random access required, or only ordered sequence behavior?
Set. Tell: Are order and duplicate occurrences preserved?
Stream. Tell: Must the collection be finite and already realized?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/List_(abstract_data_type) (revision 1369366903).
Preserved source candidate: http://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf
Preserved source candidate: http://www.lua.org/pil/11.3.html

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.