PHPackages                             vondrasoft/sorted-linked-list - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. vondrasoft/sorted-linked-list

ActiveLibrary

vondrasoft/sorted-linked-list
=============================

A homogeneous, type-safe sorted singly linked list for PHP 8.4+

1.0.0(1mo ago)03↑1900%MITPHPPHP >=8.4

Since Mar 21Pushed 1mo agoCompare

[ Source](https://github.com/vondrasoft/sorted-linked-list)[ Packagist](https://packagist.org/packages/vondrasoft/sorted-linked-list)[ RSS](/packages/vondrasoft-sorted-linked-list/feed)WikiDiscussions main Synced 1mo ago

READMEChangelog (1)Dependencies (7)Versions (2)Used By (0)

SortedLinkedList
================

[](#sortedlinkedlist)

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

Installation
------------

[](#installation)

```
composer require vondrasoft/sorted-linked-list
```

> **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)
--------------------

[](#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.

```
# First-time setup (starts container + installs dependencies)
./init.sh

# Install dependencies
docker compose exec php composer install

# Run tests
docker compose exec php composer test

# Run tests with code coverage (Xdebug included in Docker image)
docker compose exec php composer test-coverage

# Run static analysis (PHPStan level 9 + strict rules)
docker compose exec php composer analyze

# Run code style check (PHPCS + ShipMonk Coding Standard)
docker compose exec php composer cs

# Auto-fix code style violations
docker compose exec php composer cs-fix

# Run benchmarks
docker compose exec php composer benchmark
```

API
---

[](#api)

```
use Vondrasoft\DataStructures\SortedLinkedList;

$list = new SortedLinkedList();

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

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

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

$list->remove(3);    // true  (removes first occurrence)
$list->removeAll(1); // 1     (returns number of removed elements)
$list->toArray();    // [5]

$list->clear();      // removes all elements, resets type lock
$list->toArray();    // []
count($list);        // 0
```

### Type safety

[](#type-safety)

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

```
$list = new SortedLinkedList();
$list->add(1);
$list->add('hello'); // throws InvalidTypeException
```

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

### String sorting

[](#string-sorting)

Strings are sorted using PHP's native ` **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:

SizeTime100 elements2.64 ms500 elements2.12 ms1,000 elements7.10 ms5,000 elements162.02 ms10,000 elements640.19 ms- **String insertion (random order):**

SizeTime100 elements0.26 ms500 elements3.34 ms1,000 elements11.44 ms5,000 elements261.77 ms10,000 elements1,098.61 ms- **Sorted / reverse input** — sorted input appends via tail pointer O(1), reverse always inserts at head O(1). Both avoid traversal:

SizeAlready sortedReverse sorted100 elements0.10 ms0.11 ms500 elements0.47 ms0.45 ms1,000 elements0.86 ms0.82 ms5,000 elements4.07 ms4.03 ms10,000 elements8.23 ms7.90 ms- **Removal** (all elements from head):

SizeTime100 elements0.07 ms500 elements0.22 ms1,000 elements0.46 ms5,000 elements2.18 ms10,000 elements4.45 ms- **Iteration** — `toArray()` (direct while loop) vs `foreach` (generator):

SizetoArray()foreach100 elements0.01 ms0.03 ms500 elements0.03 ms0.10 ms1,000 elements0.05 ms0.20 ms5,000 elements0.24 ms0.81 ms10,000 elements0.48 ms1.63 ms- **`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):**

Sizewhileforeachin\_array100 elements2.35 ms7.75 ms0.31 ms500 elements9.67 ms38.10 ms0.48 ms1,000 elements18.99 ms76.67 ms0.71 ms5,000 elements92.94 ms372.95 ms2.29 ms10,000 elements186.13 ms756.94 ms4.38 ms- **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:**

Sizetail O(1)whileforeachend()100 elements0.25 ms2.29 ms16.09 ms0.23 ms500 elements0.26 ms9.44 ms78.43 ms0.23 ms1,000 elements0.25 ms18.38 ms156.64 ms0.24 ms5,000 elements0.25 ms86.98 ms766.63 ms0.25 ms10,000 elements0.26 ms174.49 ms1,523.88 ms0.23 ms*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):

SizeLinkedListarrayratio100 elements7.9 KB2.6 KB3.1x500 elements39.2 KB12.1 KB3.2x1,000 elements78.2 KB20.1 KB3.9x5,000 elements390.7 KB132.1 KB3.0x10,000 elements909.4 KB260.1 KB3.5x---

SortedLinkedList (CZ)
=====================

[](#sortedlinkedlist-cz)

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

Instalace
---------

[](#instalace)

```
composer require vondrasoft/sorted-linked-list
```

> **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)
-----------------

[](#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í.

```
# Prvotní spuštění (nastartuje kontejner + nainstaluje závislosti)
./init.sh

# Instalace závislostí
docker compose exec php composer install

# Spuštění testů
docker compose exec php composer test

# Testy s code coverage (Xdebug je součástí Docker image)
docker compose exec php composer test-coverage

# Statická analýza (PHPStan level 9 + strict rules)
docker compose exec php composer analyze

# Kontrola coding standardu (PHPCS + ShipMonk Coding Standard)
docker compose exec php composer cs

# Automatická oprava coding standardu
docker compose exec php composer cs-fix

# Benchmarky
docker compose exec php composer benchmark
```

API
---

[](#api-1)

```
use Vondrasoft\DataStructures\SortedLinkedList;

$list = new SortedLinkedList();

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

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

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

$list->remove(3);    // true  (odebere první výskyt)
$list->removeAll(1); // 1     (vrátí počet odebraných prvků)
$list->toArray();    // [5]

$list->clear();      // odebere všechny prvky, uvolní zámek typu
$list->toArray();    // []
count($list);        // 0
```

### Typová bezpečnost

[](#typová-bezpečnost)

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

```
$list = new SortedLinkedList();
$list->add(1);
$list->add('hello'); // 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ů

[](#řazení-řetězců)

Řetězce jsou řazeny pomocí nativního PHP operátoru ` **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:

VelikostČas100 prvků2,64 ms500 prvků2,12 ms1 000 prvků7,10 ms5 000 prvků162,02 ms10 000 prvků640,19 ms- **Vkládání řetězců (náhodné pořadí):**

VelikostČas100 prvků0,26 ms500 prvků3,34 ms1 000 prvků11,44 ms5 000 prvků261,77 ms10 000 prvků1 098,61 ms- **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:

VelikostSeřazenýObrácený100 prvků0,10 ms0,11 ms500 prvků0,47 ms0,45 ms1 000 prvků0,86 ms0,82 ms5 000 prvků4,07 ms4,03 ms10 000 prvků8,23 ms7,90 ms- **Odebírání** (všechny prvky od hlavy):

VelikostČas100 prvků0,07 ms500 prvků0,22 ms1 000 prvků0,46 ms5 000 prvků2,18 ms10 000 prvků4,45 ms- **Iterace** — `toArray()` (přímý while cyklus) vs `foreach` (generátor):

VelikosttoArray()foreach100 prvků0,01 ms0,03 ms500 prvků0,03 ms0,10 ms1 000 prvků0,05 ms0,20 ms5 000 prvků0,24 ms0,81 ms10 000 prvků0,48 ms1,63 ms- **`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):**

Velikostwhileforeachin\_array100 prvků2,35 ms7,75 ms0,31 ms500 prvků9,67 ms38,10 ms0,48 ms1 000 prvků18,99 ms76,67 ms0,71 ms5 000 prvků92,94 ms372,95 ms2,29 ms10 000 prvků186,13 ms756,94 ms4,38 ms- **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:**

Velikosttail O(1)whileforeachend()100 prvků0,25 ms2,29 ms16,09 ms0,23 ms500 prvků0,26 ms9,44 ms78,43 ms0,23 ms1 000 prvků0,25 ms18,38 ms156,64 ms0,24 ms5 000 prvků0,25 ms86,98 ms766,63 ms0,25 ms10 000 prvků0,26 ms174,49 ms1 523,88 ms0,23 ms*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):

VelikostLinkedListarraypoměr100 prvků7,9 KB2,6 KB3,1x500 prvků39,2 KB12,1 KB3,2x1 000 prvků78,2 KB20,1 KB3,9x5 000 prvků390,7 KB132,1 KB3,0x10 000 prvků909,4 KB260,1 KB3,5x

###  Health Score

42

—

FairBetter than 89% of packages

Maintenance97

Actively maintained with recent releases

Popularity4

Limited adoption so far

Community6

Small or concentrated contributor base

Maturity51

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 100% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Unknown

Total

1

Last Release

48d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/f6d9292318ef6483a05ddbeccc6ef5428a59e998a3485b01b447b7d3802a788f?d=identicon)[vondrasoft](/maintainers/vondrasoft)

---

Top Contributors

[![vondrasoft](https://avatars.githubusercontent.com/u/49568359?v=4)](https://github.com/vondrasoft "vondrasoft (1 commits)")

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan

Code StylePHP\_CodeSniffer

Type Coverage Yes

### Embed Badge

![Health badge](/badges/vondrasoft-sorted-linked-list/health.svg)

```
[![Health](https://phpackages.com/badges/vondrasoft-sorted-linked-list/health.svg)](https://phpackages.com/packages/vondrasoft-sorted-linked-list)
```

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)