Download the PHP package vondrasoft/sorted-linked-list without Composer

SortedLinkedList

Type-safe, homogeneous sorted singly linked list for PHP 8.4+.

Installation

Note: The repository includes a Docker setup for development purposes only (running tests, static analysis, benchmarks). It is not needed when using the library as a dependency in your project.

Quick start (Docker)

The project uses a pre-built Docker image (ghcr.io/vondrasoft/php-xdebug:8.4) with PHP 8.4 + Xdebug + Composer, so you don't need to build anything locally. The Dockerfile is kept in the repository for reference.

API

Type safety

The list locks its type on first insertion. Mixing types throws InvalidTypeException:

The type lock resets when all elements are removed, allowing the list to be reused with a different type.

String sorting

Strings are sorted using PHP's native < operator, which performs byte-by-byte (lexicographic) comparison. This works correctly for ASCII/English strings. For locale-aware sorting (e.g. Czech, German), a Collator from the intl extension would be needed — this is intentionally out of scope for a generic data structure.

Project structure

Code coverage

Quality tools

Benchmarks

Note: The pre-built Docker image is built for arm64 (Apple Silicon / Mac). The benchmark results below reflect this architecture. Running the image on amd64 (e.g. Linux servers) may result in significantly slower performance due to QEMU userspace emulation — Docker transparently translates arm64 instructions to amd64 at runtime, which adds substantial overhead. For accurate benchmarks on amd64, rebuild the image natively (docker build --platform linux/amd64).

Run docker compose exec php composer benchmark to measure performance across different scenarios:

• Integer insertion (random order) — demonstrates O(n) per insert, O(n²) total:

• String insertion (random order):

• Sorted / reverse input — sorted input appends via tail pointer O(1), reverse always inserts at head O(1). Both avoid traversal:

• Removal (all elements from head):

• Iteration — toArray() (direct while loop) vs foreach (generator):

• contains(): while vs foreach vs in_array — compares direct node traversal (while), generator-based iteration (foreach), and PHP's native in_array() on a plain array for the middle element. Direct node traversal is ~4x faster than the generator, but in_array() on a plain array is significantly faster thanks to C-level optimization and cache-friendly contiguous memory:

Middle element (contains):

• Last element — last() tail O(1) vs while (direct node traversal, simulates old last() without tail) vs foreach (generator) vs array end(). The tail pointer matches array end() performance — both are O(1) regardless of list size:

Last element:

1,000 calls per scenario.

• Memory usage — linked list vs plain array. Each node object carries overhead (~3x more memory than a plain array slot):

SortedLinkedList (CZ)

Typově bezpečný, homogenní seřazený jednosměrný lineární seznam pro PHP 8.4+.

Instalace

Poznámka: Repozitář obsahuje Docker setup pouze pro vývojové účely (spouštění testů, statické analýzy, benchmarků). Pro použití knihovny jako závislosti ve vašem projektu není potřeba.

Spuštění (Docker)

Projekt používá předpřipravený Docker image (ghcr.io/vondrasoft/php-xdebug:8.4) s PHP 8.4 + Xdebug + Composer, takže není potřeba nic buildovat lokálně. Dockerfile je ponechán v repozitáři pro nahlédnutí.

API

Typová bezpečnost

Seznam zamkne svůj typ při prvním vložení prvku. Pokus o vložení jiného typu vyhodí InvalidTypeException:

Po odebrání všech prvků se zámek uvolní a seznam je možné použít s jiným typem.

Řazení řetězců

Řetězce jsou řazeny pomocí nativního PHP operátoru <, který provádí lexikografické (byte-by-byte) porovnání. To funguje správně pro ASCII/anglické řetězce. Pro locale-aware řazení (např. čeština, němčina) by bylo potřeba použít Collator z rozšíření intl — to je záměrně mimo rozsah této generické datové struktury.

Struktura projektu

Pokrytí kódu testy

Nástroje pro kvalitu

Benchmarky

Poznámka: Předbuilděný Docker image je postaven pro arm64 (Apple Silicon / Mac). Níže uvedené výsledky benchmarků odpovídají této architektuře. Při spuštění na amd64 (např. Linux servery) může být výkon výrazně nižší kvůli QEMU emulaci — Docker za běhu transparentně překládá arm64 instrukce na amd64, což přidává značný overhead. Pro přesné benchmarky na amd64 je potřeba image přebuildit nativně (docker build --platform linux/amd64).

Spuštění: docker compose exec php composer benchmark. Měří výkon v různých scénářích:

• Vkládání celých čísel (náhodné pořadí) — demonstruje O(n) na jedno vložení, O(n²) celkem:

• Vkládání řetězců (náhodné pořadí):

• Seřazený / obrácený vstup — seřazený vstup se připojuje přes tail pointer O(1), obrácený vkládá vždy na hlavu O(1). Oba se vyhnou průchodu:

• Odebírání (všechny prvky od hlavy):

• Iterace — toArray() (přímý while cyklus) vs foreach (generátor):

• contains(): while vs foreach vs in_array — porovnává přímý průchod uzly (while), iteraci přes generátor (foreach) a PHP nativní in_array() na poli pro prostřední prvek. Přímý průchod uzly je ~4x rychlejší než generátor, ale in_array() na poli je výrazně rychlejší díky C-level optimalizaci a cache-friendly souvislé paměti:

Prostřední prvek (contains):

• Poslední prvek — last() tail O(1) vs while (přímý průchod uzly, simuluje starý last() bez tailu) vs foreach (generátor) vs array end(). Tail pointer dosahuje stejného výkonu jako array end() — obojí je O(1) bez ohledu na velikost seznamu:

Poslední prvek:

1 000 volání na scénář.

• Paměťová náročnost — linked list vs pole. Každý objekt uzlu nese overhead (~3x více paměti než slot v poli):