rulinski/sorted-linked-list

A type-safe sorted linked list supporting int or string values (not both).

v1.0.0 2026-07-15 06:11 UTC

Requires

• php: ^8.4

Requires (Dev)

• phpstan/phpstan: ^2.2
• phpunit/phpunit: ^13.2

MIT

• Vitali Rulinski

Published on Packagist.org on 2026-07-15 06:17 UTC

README

A small, type-safe PHP library implementing a linked list that keeps its elements sorted at all times. A single list instance holds either int or string values — never both — with the type declared explicitly when the list is created.

Requirements

• PHP >= 8.4

Installation

composer require rulinski/sorted-linked-list

Usage

use Rulinski\SortedLinkedList\SortedLinkedList;

$list = new SortedLinkedList(SortedLinkedList::TYPE_INT);

$list->add(5);
$list->add(1);
$list->add(3);

$list->toArray();     // [1, 3, 5]
(string) $list;        // "[1, 3, 5]"
$list->contains(3);    // true
$list->first();        // 1
$list->last();         // 5
count($list);          // 3

foreach ($list as $value) {
    // 1, 3, 5
}

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

$strings = new SortedLinkedList(SortedLinkedList::TYPE_STRING);
$strings->add('banana');
$strings->add('apple');

$strings->toArray();   // ['apple', 'banana']

$strings->add(42);     // throws InvalidValueTypeException

Design notes

• Type is fixed at construction, not inferred from the first inserted value. This makes the contract explicit at the call site and fails fast on misuse, rather than silently locking in a type based on insertion order.
• Duplicates are allowed. This is a sorted list, not a sorted set. remove() removes only the first matching occurrence and returns whether anything was removed; call it repeatedly (or in a loop) to remove all matches.
• first()/last() throw EmptyListException on an empty list rather than returning null, so callers can't silently mistake "empty" for a valid 0/'' value.
• Ordering is ascending: numeric comparison for int, strcmp for string. Custom comparators are intentionally out of scope.
• Complexity: add(), remove(), contains() are O(n) (list traversal to find the sorted position / matching node). first() / isEmpty() / count() are O(1). last() is O(n) (singly linked, no tail pointer).
• Implements Countable, IteratorAggregate, and Stringable so it behaves like a native PHP collection (count(), foreach, string casting all work as expected).

Testing

composer test    # PHPUnit
composer stan    # PHPStan (max level)

Author

Vitali Rulinski