README

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 ints or strings — 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

• 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

• PHP >= 8.2

Installation

composer require idlerus/sorted-linked-list

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

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

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

$list = new SortedLinkedList();
$list->insert(1);
$list->insert('one');  // throws TypeMismatchException
                       // ($e->expectedType === 'int', $e->actualType === 'string')

API overview

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 check   # cs + tests in one go

Dev dependencies & what they guard

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

• 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

MIT