README

A type-safe sorted linked list library for PHP 8.4+. Holds either int or string values (never both in the same instance) and maintains ascending order on every insertion.

Requirements

• PHP 8.4 or higher

Installation

composer require adambenovic/shipmonk-sorted-linked-list

Quick Start

use AdamBenovic\SortedLinkedList\SortedLinkedList;

// Just insert values -- the type is detected automatically
$list = new SortedLinkedList();
$list->insert(42);
$list->insert(7);
$list->insert(15);

$list->toArray(); // [7, 15, 42]
$list->first();   // 7
$list->last();    // 42

Once the first value is inserted, the type is locked:

$list = new SortedLinkedList();
$list->insert(1);       // OK -- type locked to "integer"
$list->insert(2);       // OK
$list->insert('hello'); // throws TypeMismatchException

Creating Lists

use AdamBenovic\SortedLinkedList\SortedLinkedList;
use AdamBenovic\SortedLinkedList\ValueType;

// Auto-detect type from first insert
$list = new SortedLinkedList();

// Pre-declare the type (rejects wrong-type values even before first insert)
$ints = new SortedLinkedList(ValueType::Integer);
$strings = new SortedLinkedList(ValueType::String);

// Factory method -- creates a pre-populated sorted list
$list = SortedLinkedList::of(3, 1, 4, 1, 5);       // [1, 1, 3, 4, 5]
$list = SortedLinkedList::of('cherry', 'apple');     // ['apple', 'cherry']

Typed Convenience Classes

For stricter static analysis, use the type-specific classes directly:

use AdamBenovic\SortedLinkedList\IntSortedLinkedList;
use AdamBenovic\SortedLinkedList\StringSortedLinkedList;

$ints = new IntSortedLinkedList();       // first() returns int
$strings = new StringSortedLinkedList(); // first() returns string

API

Counting and Iteration

All list classes implement Countable, IteratorAggregate, JsonSerializable, and Stringable:

$list = SortedLinkedList::of(3, 1, 2);

count($list);             // 3
$list->size;              // 3 (read-only from outside)

foreach ($list as $value) {
    echo $value;          // 1, 2, 3
}

json_encode($list);       // [1,2,3]
echo $list;               // SortedLinkedList<integer>[1, 2, 3]

Filtering

$list = SortedLinkedList::of(1, 2, 3, 4, 5);

$even = $list->filter(fn(int|string $v) => $v % 2 === 0);
$even->toArray(); // [2, 4]

Merging

Merges two sorted lists of the same type in O(n+m) time:

$a = SortedLinkedList::of('apple', 'cherry');
$b = SortedLinkedList::of('banana', 'date');

$merged = $a->merge($b);
$merged->toArray(); // ['apple', 'banana', 'cherry', 'date']

Duplicates

Duplicate values are allowed. remove() removes only the first occurrence:

$list = SortedLinkedList::of(5, 5, 5);

$list->remove(5);
$list->toArray(); // [5, 5]

String Sorting

StringSortedLinkedList and SortedLinkedList (when holding strings) use byte-level comparison (strcmp), which follows UTF-8 byte order rather than locale-aware collation. This means:

• Uppercase letters sort before lowercase (e.g., "Banana" before "apple")
• Multi-byte characters (e.g., "ä", "ñ") sort after all ASCII characters

If you need locale-sensitive ordering, consider using PHP's intl extension (Collator class).

Exceptions

Architecture

The library uses the Template Method pattern:

• SortedLinkedListInterface -- defines the public contract with @template generics
• AbstractSortedLinkedList -- implements the sorted insertion algorithm, delegates type validation and comparison to subclasses
• SortedLinkedList -- the primary entry point with auto-detection of value type
• IntSortedLinkedList / StringSortedLinkedList -- convenience classes with narrowed return types for first() and last()

Development

# Install dependencies
composer install

# Run tests
vendor/bin/phpunit

# Run static analysis
vendor/bin/phpstan analyse

# Fix code style (PSR-12)
vendor/bin/php-cs-fixer fix

License

MIT