PHPackages idlerus/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. idlerus/sorted-linked-list ActiveLibrary[Utility & Helpers](/categories/utility) idlerus/sorted-linked-list ========================== Linked list that keeps its values sorted (int or string). 00PHPCI passing Since Jun 12Pushed 1mo agoCompare [ Source](https://github.com/idlerus/sorted-linked-list)[ Packagist](https://packagist.org/packages/idlerus/sorted-linked-list)[ RSS](/packages/idlerus-sorted-linked-list/feed)WikiDiscussions main Synced 1w ago READMEChangelogDependenciesVersions (1)Used By (0) SortedLinkedList ================ [](#sortedlinkedlist) A doubly linked list for PHP that keeps its values **sorted at all times** — so you never have to call `sort()` again. You insert, it files the value exactly where it belongs. Like a well-trained librarian, just without the disapproving looks. Holds either `int`s or `string`s — never both. The type is locked by the first inserted value, because PHP has no generics and *somebody* has to keep order around here. Features -------- [](#features) - **Always sorted** — values are placed at their sorted position on insert; no explicit sorting, ever - **Both reading directions** — ascending or descending via `SortOrder::Asc` / `SortOrder::Desc`, powered by backward links (no copying, no reversing) - **Configurable duplicate handling** — `DuplicatePolicy::Allow` (default), `Ignore` (silently skipped), or `Reject` (throws) - **Configurable string comparison** — case-sensitive by default, case-insensitive via `StringComparison::CaseInsensitive`; one comparison drives ordering *and* duplicate detection, consistently - **Type safety at runtime** — mixing ints and strings throws a `TypeMismatchException` carrying both type names - **Fast paths where it counts** — inserting a new minimum/maximum and rejecting out-of-range lookups are O(1); feeding it already-sorted data (timestamps, IDs) is as fast as it gets - **GC friendly** — node links are broken on `clear()`/destruction, so memory is freed by plain refcounting without waiting for the cycle collector - **Plays nicely with PHP** — implements `IteratorAggregate` (just `foreach` it) and `Countable` (`count($list)` is O(1)) Requirements ------------ [](#requirements) - PHP >= 8.2 Installation ------------ [](#installation) ``` composer require idlerus/sorted-linked-list ``` Usage ----- [](#usage) ``` use Idlerus\SortedLinkedList\SortedLinkedList; use Idlerus\SortedLinkedList\SortOrder; use Idlerus\SortedLinkedList\DuplicatePolicy; $list = new SortedLinkedList(); $list->insert(5); $list->insert(1); $list->insert(3); $list->toArray(); // [1, 3, 5] $list->toArray(SortOrder::Desc); // [5, 3, 1] foreach ($list as $value) { // 1, 3, 5 — sorted, always } $list->contains(3); // true $list->min(); // 1 $list->max(); // 5 count($list); // 3 $list->remove(3); // true — removes one occurrence $list->clear(); // empty list, type lock released ``` ### Duplicates, your way [](#duplicates-your-way) ``` // Allow (default): duplicates sit next to each other $list = new SortedLinkedList(); // Ignore: duplicates are skipped, insert() tells you what happened $list = new SortedLinkedList(DuplicatePolicy::Ignore); $list->insert(5); // true $list->insert(5); // false — already there, nothing changed // Reject: duplicates are an error $list = new SortedLinkedList(DuplicatePolicy::Reject); $list->insert(5); $list->insert(5); // throws DuplicateValueException ($e->value === 5) ``` ### Case sensitivity [](#case-sensitivity) By default, string comparison is byte-wise — which means case-sensitive, and ASCII ordering applies (`'Cherry' < 'apple'`, since uppercase sorts first). If that surprises your users, flip the switch: ``` use Idlerus\SortedLinkedList\StringComparison; $list = new SortedLinkedList(comparison: StringComparison::CaseInsensitive); $list->insert('banana'); $list->insert('Cherry'); $list->insert('apple'); $list->toArray(); // ['apple', 'banana', 'Cherry'] — dictionary-like $list->contains('APPLE'); // true // Combines with duplicate policies — equality follows the same comparison: $list = new SortedLinkedList(DuplicatePolicy::Ignore, StringComparison::CaseInsensitive); $list->insert('Apple'); // true $list->insert('apple'); // false — same word, different costume ``` Note: locale-aware collation (accents, non-ASCII alphabets) is out of scope; for that, reach for the `intl` extension's `Collator`. ### One type per list [](#one-type-per-list) ``` $list = new SortedLinkedList(); $list->insert(1); $list->insert('one'); // throws TypeMismatchException // ($e->expectedType === 'int', $e->actualType === 'string') ``` API overview ------------ [](#api-overview) MethodDescriptionComplexity`insert(int|string $value): bool`Inserts at sorted positionO(n), O(1) for new min/max`remove(int|string $value): bool`Removes first occurrenceO(n), O(1) out of range`contains(int|string $value): bool`Membership checkO(n), O(1) out of range`min()` / `max()`Smallest / largest value or nullO(1)`count()` / `isEmpty()`Size queriesO(1)`toArray(SortOrder $order)`All values as arrayO(n)`iterate(SortOrder $order)`Lazy generator, either directionO(n)`clear()`Empties the list, unlocks the typeO(n)Development ----------- [](#development) Clone, then: ``` composer install composer test # run the test suite composer cs # check coding standard composer cs-fix # auto-fix what can be fixed composer stan # static analysis composer check # cs + stan + tests in one go ``` The same three checks run in CI (GitHub Actions) on every push and pull request, with the test suite spanning PHP 8.2–8.4. ### Dev dependencies & what they guard [](#dev-dependencies--what-they-guard) PackageRole[`phpunit/phpunit`](https://phpunit.de/)Test framework. Runs the suite — unit tests for every branch (head/middle/tail, all policies) plus randomized tests that replay thousands of mutations against a plain-array reference implementation.[`phpstan/phpstan`](https://phpstan.org/)Static analysis at `level: max` (configured in `phpstan.neon.dist`). Proves the type story holds without running a single line — null-safety of node links included.[`squizlabs/php_codesniffer`](https://github.com/PHPCSStandards/PHP_CodeSniffer)Coding-standard enforcement (`phpcs`) and auto-fixing (`phpcbf`). The ruleset lives in `phpcs.xml.dist`: PSR-12 as the base, plus required PHPDoc on every method.[`slevomat/coding-standard`](https://github.com/slevomat/coding-standard)Extra sniffs on top of PSR-12: strict types declarations, type-hint completeness, import hygiene (no fallback globals), dead-code detection, early-exit style. The picky friend every codebase needs.The `dealerdirect/phpcodesniffer-composer-installer` plugin (pulled in automatically) registers the Slevomat standard with PHP\_CodeSniffer, so `phpcs` finds it without any manual path configuration. Design notes ------------ [](#design-notes) - **Doubly linked** — each node holds `prev` and `next`. That is what makes descending iteration and O(1) `max()` possible; the price is one extra pointer per node. - **Values are stored ascending, direction is a read concern** — one list serves both directions at once, no per-instance ordering lock. - **Sorted order is exploited everywhere** — lookups stop as soon as values pass the target, and anything outside the min/max range is answered in O(1) without touching the list. - **Known limitation** — insertion into the middle is O(n); a linked list cannot binary-search. If you need O(log n) inserts, you are shopping for a skip list, not a linked list. License ------- [](#license) MIT ### Health Score 20 — LowBetter than 12% of packages Maintenance60 Regular maintenance activity Popularity0 Limited adoption so far Community8 Small or concentrated contributor base Maturity11 Early-stage or recently created project Bus Factor1 Top contributor holds 60% 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. ### Community Maintainers ![](https://avatars.githubusercontent.com/u/1357012?v=4)[Lukáš Voborský](/maintainers/idlerus)[@idlerus](https://github.com/idlerus) --- Top Contributors [![Vikingeus](https://avatars.githubusercontent.com/u/30017175?v=4)](https://github.com/Vikingeus "Vikingeus (3 commits)")[![idlerus](https://avatars.githubusercontent.com/u/1357012?v=4)](https://github.com/idlerus "idlerus (2 commits)") ### Embed Badge ![Health badge](/badges/idlerus-sorted-linked-list/health.svg) ``` [![Health](https://phpackages.com/badges/idlerus-sorted-linked-list/health.svg)](https://phpackages.com/packages/idlerus-sorted-linked-list) ``` ### Alternatives [wapmorgan/php-code-analyzer A program that finds usage of different non-built-in extensions in your php code. 96149.1k4](/packages/wapmorgan-php-code-analyzer)[zepgram/magento-dotenv Simple autoloader to integrate the Symfony Dotenv component into Magento2 1376.0k](/packages/zepgram-magento-dotenv)[fsc/batch Library with classes to help you do batch. 185.3k](/packages/fsc-batch) PHPackages © 2026 [Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)