Download the PHP package r34117y/sorted-linked-list without Composer

Sorted Linked List

A PHP library providing a sorted linked list for typed values. It provides sorted linked lists for integers and strings, with a strategy-based extension point for custom value types.

Requirements

• PHP 8.2 or newer
• PHP intl extension
• Composer

Installation

Install the library with Composer:

Then import the factory class where you need it:

Architecture

Create lists with SortedLinkedListFactory. SortedLinkedList has a public constructor only for factory and extension internals, and that constructor is marked @internal.

Built-in factories configure the strategy for common value types:

• SortedLinkedListFactory::forIntegers() uses numeric ascending order by default, or descending order when requested.
• SortedLinkedListFactory::forStrings() uses lexicographic ascending order by default, or locale-aware collation when a locale is provided. It can also sort descending.
• SortedLinkedListFactory::usingStrategy() accepts a custom SortedListStrategy for any value type.

Strategies validate values through normalize() and compare normalized values through compare(). Invalid values should be rejected by throwing InvalidValueTypeException.

Usage

Integer Lists

Use descending: true for descending integer order:

String Lists

Use descending: true for descending string order:

Use a locale to sort strings in locale-aware order:

If locale cannot be resolved, LocaleNotInstalledException is thrown.

Custom Strategy Lists

Value Typing

Built-in lists can contain integers or strings, but never both.

Direct construction is marked internal and is not supported for consumers. Use SortedLinkedListFactory::forIntegers() for integer lists, SortedLinkedListFactory::forStrings() for string lists, or SortedLinkedListFactory::usingStrategy() for custom value types.

Lists created with SortedLinkedListFactory::forIntegers() or SortedLinkedListFactory::forStrings() are explicitly typed from the start. They keep that type even when empty or after clear().

valueType() returns the value type string defined by the configured strategy.

Invalid values are rejected with Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException. This applies to factory initialization, insertion, contains(), and remove().

Sorting

Integer lists use numeric ascending order by default.

String lists use lexicographic ascending order by default, using PHP's strcmp() semantics. The default order is case-sensitive, and numeric strings remain strings.

Pass a locale to forStrings() to use locale-aware collation through PHP intl's collator_sort():

Descending locale-aware sorting is also supported:

Locale-aware sorting depends on ICU locales provided by PHP's intl extension. If the configured locale cannot be resolved, LocaleNotInstalledException is thrown.

Custom strategy lists use the ordering returned by the strategy's compare() method.

Duplicates

Duplicate values are allowed. New duplicates are placed after existing equal values, so the insertion order is stable among equal values.

remove() removes one matching value at a time:

API Reference

• SortedLinkedListFactory::forIntegers(iterable $values = [], bool $descending = false): SortedLinkedList<int> creates an integer-only list.
• SortedLinkedListFactory::forStrings(iterable $values = [], ?string $locale = null, bool $descending = false): SortedLinkedList<string> creates a string-only list, optionally using locale-aware sorting.
• SortedLinkedListFactory::usingStrategy(SortedListStrategy<T> $strategy, iterable<T> $values = []): SortedLinkedList<T> creates a custom strategy list.
• valueType(): string returns the list value type, defined in the relevant strategy.
• isEmpty(): bool returns whether the list has no values.
• count(): int returns the number of values. The list also supports PHP's count($list).
• insert(T $value): void inserts a value while preserving sorted order.
• contains(T $value): bool checks whether a value is present.
• remove(T $value): bool removes one matching value and returns whether anything was removed.
• first(): T|null returns the first sorted value, or null when empty.
• last(): T|null returns the last sorted value, or null when empty.
• clear(): void removes all values.
• toArray(): list<T> returns values as a sorted PHP list.
• getIterator(): Traversable<int, T> supports foreach iteration in sorted order.
• jsonSerialize(): list<T> serializes the list as a JSON array.

Operation Complexity

Benchmark

These figures are illustrative, not guarantees. They were measured on a local run with PHP 8.4.6 using integer lists built from deterministic shuffled input. Each value is the median of 3 runs.

Shuffled construction was intentionally the expensive case because every inserted value could scan part of the list. Factory construction now sorts the initial values first, so building shuffled input scales much better. Existing insert() calls still use linked-list insertion and remain O(n).

Development

Install dependencies:

Common local commands:

Versioning

This project follows Semantic Versioning. Release notes are maintained in CHANGELOG.md.