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

Method	Description	Complexity
`insert($value): void`	Add a value, maintaining sorted order	O(n)
`remove($value): bool`	Remove the first occurrence	O(n)
`contains($value): bool`	Check if a value exists	O(n)
`first(): int\|string`	Get the smallest (first) element	O(1)
`last(): int\|string`	Get the largest (last) element	O(1)
`toArray(): array`	Get all values as a sorted array	O(n)
`isEmpty(): bool`	Check if the list is empty	O(1)
`clear(): void`	Remove all elements	O(1)
`count(): int`	Get the number of elements	O(1)
`filter(callable): static`	Create a new filtered list	O(n)
`merge(self): static`	Merge two lists into a new one	O(n+m)
`getValueType(): ?ValueType`	Get the detected/declared value type	O(1)

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

Exception	Parent	When
`TypeMismatchException`	`\InvalidArgumentException`	Inserting a value of the wrong type
`EmptyListException`	`\UnderflowException`	Calling `first()` or `last()` on an empty list
`\InvalidArgumentException`	--	Merging two lists of different types

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

adambenovic / shipmonk-sorted-linked-list

Maintainers

Package info

Statistics

Security