PHPackages                             r34117y/sorted-linked-list - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. r34117y/sorted-linked-list

ActiveLibrary[Utility & Helpers](/categories/utility)

r34117y/sorted-linked-list
==========================

A PHP library providing sorted linked lists for typed values.

v2.1.0(1mo ago)03MITPHPPHP ^8.2CI passing

Since Jul 14Pushed 1w agoCompare

[ Source](https://github.com/r34117y/sorted-linked-list)[ Packagist](https://packagist.org/packages/r34117y/sorted-linked-list)[ RSS](/packages/r34117y-sorted-linked-list/feed)WikiDiscussions main Synced 1w ago

READMEChangelogDependencies (4)Versions (6)Used By (0)

Sorted Linked List
==================

[](#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
------------

[](#requirements)

- PHP 8.2 or newer
- PHP intl extension
- Composer

Installation
------------

[](#installation)

Install the library with Composer:

```
composer require r34117y/sorted-linked-list
```

Then import the factory class where you need it:

```
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;
```

Architecture
------------

[](#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
-----

[](#usage)

### Integer Lists

[](#integer-lists)

```
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forIntegers([3, 1, 2]);
$list->insert(2);

$list->toArray(); // [1, 2, 2, 3]
$list->first(); // 1
$list->last(); // 3
$list->contains(2); // true
```

Use `descending: true` for descending integer order:

```
$list = SortedLinkedListFactory::forIntegers([3, 1, 2], descending: true);

$list->toArray(); // [3, 2, 1]
$list->first(); // 3
$list->last(); // 1
```

### String Lists

[](#string-lists)

```
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forStrings(['banana', 'apple', 'cherry']);
$list->insert('apple');

$list->toArray(); // ['apple', 'apple', 'banana', 'cherry']
$list->first(); // 'apple'
$list->last(); // 'cherry'
$list->contains('banana'); // true
```

Use `descending: true` for descending string order:

```
$list = SortedLinkedListFactory::forStrings(['banana', 'apple', 'cherry'], descending: true);

$list->toArray(); // ['cherry', 'banana', 'apple']
$list->first(); // 'cherry'
$list->last(); // 'apple'
```

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

```
$list = SortedLinkedListFactory::forStrings(['ą', 'a', 'ź', 'z'], locale: 'pl_PL');

$list->toArray(); // ['a', 'ą', 'z', 'ź']
$list->first(); // 'a'
$list->last(); // 'ź'
```

If locale cannot be resolved, `LocaleNotInstalledException` is thrown.

### Custom Strategy Lists

[](#custom-strategy-lists)

```
use Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException;
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;
use Agrzelec\SortedLinkedList\Strategy\SortedListStrategy;

/**
 * @implements SortedListStrategy
 */
final class DateTimeImmutableStrategy implements SortedListStrategy
{
    public function normalize(mixed $value): DateTimeImmutable
    {
        if (!$value instanceof DateTimeImmutable) {
            throw new InvalidValueTypeException(sprintf(
                'Expected value of type %s, got %s.',
                DateTimeImmutable::class,
                get_debug_type($value),
            ));
        }

        return $value;
    }

    public function compare(mixed $left, mixed $right): int
    {
        $left = $this->normalize($left);
        $right = $this->normalize($right);

        return $left->getTimestamp()  $right->getTimestamp();
    }

    public static function getValueType(): string
    {
        return DateTimeImmutable::class;
    }
}

$list = SortedLinkedListFactory::usingStrategy(
    new DateTimeImmutableStrategy(),
    [
        new DateTimeImmutable('2024-12-01'),
        new DateTimeImmutable('2024-01-01'),
    ],
);

$list->insert(new DateTimeImmutable('2024-06-01'));

$list->toArray(); // 2024-01-01, 2024-06-01, 2024-12-01
```

Value Typing
------------

[](#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()`.

```
use Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException;
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forIntegers([1, 2, 3]);

try {
    $list->insert('4');
} catch (InvalidValueTypeException $exception) {
    // The list still contains [1, 2, 3].
}
```

Sorting
-------

[](#sorting)

Integer lists use numeric ascending order by default.

```
SortedLinkedListFactory::forIntegers([10, -1, 2])->toArray(); // [-1, 2, 10]
SortedLinkedListFactory::forIntegers([10, -1, 2], descending: true)->toArray(); // [10, 2, -1]
```

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

```
SortedLinkedListFactory::forStrings(['2', '10', '1'])->toArray(); // ['1', '10', '2']
SortedLinkedListFactory::forStrings(['2', '10', '1'], descending: true)->toArray(); // ['2', '10', '1']
```

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

```
$list = SortedLinkedListFactory::forStrings(['z', 'ą', 'a'], 'pl_PL');

$list->toArray(); // ['a', 'ą', 'z']
```

Descending locale-aware sorting is also supported:

```
$list = SortedLinkedListFactory::forStrings(['z', 'ą', 'a'], 'pl_PL', descending: true);

$list->toArray(); // ['z', 'ą', 'a']
```

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
----------

[](#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:

```
$list = SortedLinkedListFactory::forIntegers([1, 2, 2, 3]);

$list->remove(2); // true
$list->toArray(); // [1, 2, 3]
```

API Reference
-------------

[](#api-reference)

- `SortedLinkedListFactory::forIntegers(iterable $values = [], bool $descending = false): SortedLinkedList` creates an integer-only list.
- `SortedLinkedListFactory::forStrings(iterable $values = [], ?string $locale = null, bool $descending = false): SortedLinkedList` creates a string-only list, optionally using locale-aware sorting.
- `SortedLinkedListFactory::usingStrategy(SortedListStrategy $strategy, iterable $values = []): SortedLinkedList` 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` returns values as a sorted PHP list.
- `getIterator(): Traversable` supports `foreach` iteration in sorted order.
- `jsonSerialize(): list` serializes the list as a JSON array.

Operation Complexity
--------------------

[](#operation-complexity)

OperationComplexityNotes`insert()`O(n)Finds the sorted insertion point.`contains()`O(n)Stops early when the current value is greater than the searched value.`remove()`O(n)Removes the first matching value and stops early when possible.`first()`O(1)Reads the head node.`last()`O(1)Reads the tracked tail node.`count()` / `isEmpty()`O(1)Uses tracked list size.`clear()`O(1)Drops head and tail references.`toArray()` / iteration / JSON serializationO(n)Walks the list in sorted order.Benchmark
---------

[](#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.

LengthBuild shuffled list`contains()` last value`contains()` missing high value`toArray()`1001.432 ms0.176 ms0.003 ms0.043 ms1,00023.423 ms1.744 ms0.006 ms0.378 ms2,50074.699 ms5.078 ms0.008 ms1.035 ms5,000150.381 ms8.376 ms0.008 ms1.970 msShuffled 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
-----------

[](#development)

Install dependencies:

```
composer install
```

Common local commands:

CommandDescription`composer test`Run the PHPUnit test suite.`composer analyse`Run PHPStan static analysis.`composer cs`Check coding standards with PHP-CS-Fixer.`composer cs:fix`Automatically fix coding-standard issues.`composer check`Run coding standards, static analysis, and tests.Versioning
----------

[](#versioning)

This project follows [Semantic Versioning](https://semver.org/spec/v2.0.0.html). Release notes are maintained in [CHANGELOG.md](CHANGELOG.md).

###  Health Score

40

—

FairBetter than 86% of packages

Maintenance94

Actively maintained with recent releases

Popularity3

Limited adoption so far

Community6

Small or concentrated contributor base

Maturity50

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 100% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~0 days

Total

5

Last Release

46d ago

Major Versions

v1.0.2 → v2.0.02026-07-15

### Community

Maintainers

![](https://www.gravatar.com/avatar/1ba4d7326edc0abfc935b14af0b1716225f6bd9a0b39d96372d0cdecd91b2c60?d=identicon)[r34117y](/maintainers/r34117y)

---

Top Contributors

[![r34117y](https://avatars.githubusercontent.com/u/6651766?v=4)](https://github.com/r34117y "r34117y (6 commits)")

---

Tags

collectionlinked listdata structuresorted-list

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan

Code StylePHP CS Fixer

Type Coverage Yes

### Embed Badge

![Health badge](/badges/r34117y-sorted-linked-list/health.svg)

```
[![Health](https://phpackages.com/badges/r34117y-sorted-linked-list/health.svg)](https://phpackages.com/packages/r34117y-sorted-linked-list)
```

###  Alternatives

[phpcollection/phpcollection

General-Purpose Collection Library for PHP

99665.1M34](/packages/phpcollection-phpcollection)[league/period

Time range API for PHP

7336.1M27](/packages/league-period)[lorisleiva/lody

Load files and classes as lazy collections in Laravel.

958.9M21](/packages/lorisleiva-lody)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)