PHPackages                             uniacid/sortedlinkedlist - 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. [Utility & Helpers](/categories/utility)
4. /
5. uniacid/sortedlinkedlist

ActiveLibrary[Utility & Helpers](/categories/utility)

uniacid/sortedlinkedlist
========================

A type-safe, automatically-sorted linked list data structure for PHP

v1.0.0(8mo ago)00[1 PRs](https://github.com/uniacid/sortedlinkedlist/pulls)MITPHPPHP ^8.1

Since Sep 19Pushed 8mo agoCompare

[ Source](https://github.com/uniacid/sortedlinkedlist)[ Packagist](https://packagist.org/packages/uniacid/sortedlinkedlist)[ Docs](https://github.com/uniacid/sortedlinkedlist)[ RSS](/packages/uniacid-sortedlinkedlist/feed)WikiDiscussions main Synced 1mo ago

READMEChangelog (1)Dependencies (8)Versions (3)Used By (0)

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

[](#sortedlinkedlist)

A high-performance, type-safe, automatically-sorted linked list data structure for PHP with advanced features including binary search optimization, custom comparators, bulk operations, and immutable variants.

[![CI Status](https://github.com/uniacid/sortedlinkedlist/actions/workflows/ci.yml/badge.svg)](https://github.com/uniacid/sortedlinkedlist/actions)[![Coverage Status](https://camo.githubusercontent.com/7c1e9c554135a44d39074cd70d18e5b76f49dab43bd486387d66b00fe220685f/68747470733a2f2f636f766572616c6c732e696f2f7265706f732f6769746875622f756e69616369642f736f727465646c696e6b65646c6973742f62616467652e7376673f6272616e63683d6d6173746572)](https://coveralls.io/github/uniacid/sortedlinkedlist?branch=master)[![Latest Stable Version](https://camo.githubusercontent.com/29d4c63ef4e1f5418cd2280f1606fa1d6b19296b420457a551f86eb6af3f64fb/68747470733a2f2f706f7365722e707567782e6f72672f756e69616369642f736f727465646c696e6b65646c6973742f762f737461626c65)](https://packagist.org/packages/uniacid/sortedlinkedlist)[![Total Downloads](https://camo.githubusercontent.com/87cb466bb6b1c6510cfd557b16ff24e59dc334db61691f0fd5de2d89f6920b79/68747470733a2f2f706f7365722e707567782e6f72672f756e69616369642f736f727465646c696e6b65646c6973742f646f776e6c6f616473)](https://packagist.org/packages/uniacid/sortedlinkedlist)[![License](https://camo.githubusercontent.com/8392b7002f4033a561ad5d8ce96f0a3e6855ba8e033ae7eab53c8c7c17a17f48/68747470733a2f2f706f7365722e707567782e6f72672f756e69616369642f736f727465646c696e6b65646c6973742f6c6963656e7365)](https://packagist.org/packages/uniacid/sortedlinkedlist)[![PHP Version](https://camo.githubusercontent.com/d6aac44f81cb2e6f4e71f098a1cb4a71992f24f7bfb424f6670db8313c9a855c/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f5048502d253545382e312d626c7565)](https://www.php.net)[![PHPStan](https://camo.githubusercontent.com/83dd3d35cebed0eab9ee97ff1a5849c1344cda6a8ee9cac2cda20f5aa55b67bd/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f5048505374616e2d6c6576656c253230392d627269676874677265656e2e7376673f7374796c653d666c6174)](https://github.com/phpstan/phpstan)[![PSR-12](https://camo.githubusercontent.com/a33589f7572f0a744de0efda0d22b515dea415a40e4419c182c06ad1477171ce/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f5053522d31322d626c7565)](https://www.php-fig.org/psr/psr-12/)

Table of Contents
-----------------

[](#table-of-contents)

- [Features](#features)
- [Requirements](#requirements)
- [Installation](#installation)
- [Quick Start](#quick-start)
- [Documentation](#documentation)
- [Performance Characteristics](#performance-characteristics)
- [Advanced Usage](#advanced-usage)
- [Testing](#testing)
- [Contributing](#contributing)
- [License](#license)

Features
--------

[](#features)

- **Type-Safe Implementations**: Dedicated classes for Integer, String, and Float types
- **Automatic Sorting**: Elements are automatically maintained in sorted order
- **Binary Search Optimization**: O(log n) search complexity for large datasets
- **Custom Comparators**: Flexible sorting with built-in and custom comparators
- **Bulk Operations**: Efficient batch operations (addAll, removeAll, retainAll)
- **Immutable Variant**: Thread-safe implementation with structural sharing
- **Iterator Support**: Full PHP Iterator and ArrayAccess interface compliance
- **Collection Transformations**: Map, filter, and reduce operations
- **Performance Tracking**: Built-in statistics for performance analysis

Requirements
------------

[](#requirements)

- PHP 8.1 or higher
- Composer for dependency management
- No runtime dependencies (zero-dependency library)

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

[](#installation)

```
composer require uniacid/sortedlinkedlist
```

Quick Start
-----------

[](#quick-start)

```
use SortedLinkedList\IntegerSortedLinkedList;

$list = new IntegerSortedLinkedList();
$list->add(5);
$list->add(2);
$list->add(8);
$list->add(1);

// Elements are automatically sorted
foreach ($list as $value) {
    echo $value . " "; // Output: 1 2 5 8
}

// Binary search for efficient lookups
$index = $list->binarySearch(5); // Returns index of element

// Bulk operations
$list->addAll([3, 7, 4]);
$filtered = $list->filter(fn($v) => $v > 3);
$doubled = $list->map(fn($v) => $v * 2);
```

Usage Examples
--------------

[](#usage-examples)

### Basic Operations with Different Types

[](#basic-operations-with-different-types)

```
use SortedLinkedList\IntegerSortedLinkedList;
use SortedLinkedList\StringSortedLinkedList;
use SortedLinkedList\FloatSortedLinkedList;

// Integer list
$intList = new IntegerSortedLinkedList();
$intList->add(42);
$intList->add(17);
$intList->add(99);
echo $intList->first(); // 17
echo $intList->last();  // 99

// String list
$stringList = new StringSortedLinkedList();
$stringList->addAll(['banana', 'apple', 'cherry']);
foreach ($stringList as $fruit) {
    echo $fruit . ' '; // apple banana cherry
}

// Float list
$floatList = new FloatSortedLinkedList();
$floatList->addAll([3.14, 1.41, 2.71]);
echo $floatList->get(1); // 2.71 (second element after sorting)
```

### Binary Search and Contains

[](#binary-search-and-contains)

```
$list = new IntegerSortedLinkedList();
$list->addAll(range(1, 1000));

// Binary search (fast for large lists)
$index = $list->binarySearch(500);
if ($index >= 0) {
    echo "Found at index: " . $index;
}

// Contains check
if ($list->contains(750)) {
    echo "List contains 750";
}

// Find first occurrence of value >= 400
$index = $list->binarySearchInsertPosition(400);
echo "Insert position for 400: " . $index;
```

### Collection Operations

[](#collection-operations)

```
$list = new IntegerSortedLinkedList();
$list->addAll([5, 2, 8, 1, 9, 3, 7]);

// Filter elements
$filtered = $list->filter(fn($v) => $v > 5);
// Result: [7, 8, 9]

// Map transformation
$doubled = $list->map(fn($v) => $v * 2);
// Result: [2, 4, 6, 10, 14, 16, 18]

// Reduce to single value
$sum = $list->reduce(fn($carry, $item) => $carry + $item, 0);
echo "Sum: " . $sum; // 35

// Slice operations
$slice = $list->slice(2, 3); // Get 3 elements starting from index 2
// Result: [3, 5, 7]
```

### Bulk Operations

[](#bulk-operations)

```
$list1 = new StringSortedLinkedList();
$list1->addAll(['apple', 'banana', 'cherry']);

$list2 = new StringSortedLinkedList();
$list2->addAll(['banana', 'date', 'elderberry']);

// Remove all elements that exist in list2
$list1->removeAll($list2);
// list1 now contains: ['apple', 'cherry']

// Retain only elements that exist in both
$list3 = new StringSortedLinkedList();
$list3->addAll(['apple', 'banana', 'cherry']);
$list3->retainAll(['banana', 'cherry', 'date']);
// list3 now contains: ['banana', 'cherry']
```

### Array Access Interface

[](#array-access-interface)

```
$list = new IntegerSortedLinkedList();
$list->addAll([30, 10, 20]);

// Array-like access
echo $list[0];  // 10 (first sorted element)
echo $list[1];  // 20
echo $list[2];  // 30

// Check if index exists
if (isset($list[1])) {
    echo "Index 1 exists";
}

// Note: Setting values via array access maintains sort order
$list[3] = 15;  // Adds 15 to the list in sorted position
```

### Iterator and Foreach

[](#iterator-and-foreach)

```
$list = new StringSortedLinkedList();
$list->addAll(['zebra', 'alpha', 'beta']);

// Standard foreach
foreach ($list as $index => $value) {
    echo "$index: $value\n";
}
// Output:
// 0: alpha
// 1: beta
// 2: zebra

// Manual iteration
$list->rewind();
while ($list->valid()) {
    echo $list->current() . "\n";
    $list->next();
}
```

### Converting to Array

[](#converting-to-array)

```
$list = new FloatSortedLinkedList();
$list->addAll([3.14, 1.41, 2.71, 1.73]);

// Convert to array
$array = $list->toArray();
// Result: [1.41, 1.73, 2.71, 3.14]

// Get values only (same as toArray)
$values = $list->values();

// Check if empty
if (!$list->isEmpty()) {
    echo "List has " . $list->size() . " elements";
}

// Clear all elements
$list->clear();
echo $list->isEmpty() ? "Empty" : "Not empty"; // Empty
```

Documentation
-------------

[](#documentation)

- [API Documentation](https://uniacid.github.io/sortedlinkedlist/) - Complete class and method references
- [Usage Examples](#advanced-usage) - Detailed examples for all features
- [Performance Guide](#performance-characteristics) - Benchmarks and optimization tips
- [Contributing Guidelines](CONTRIBUTING.md) - How to contribute to the project

Performance Characteristics
---------------------------

[](#performance-characteristics)

### Time Complexity

[](#time-complexity)

OperationSortedLinkedListNative Array (sorted)NotesAdd (single)O(n)O(n)List maintains sort orderAdd (bulk)O(n\*m)O(n+m) + O(n log n)m = items to addSearch (binary)O(log n)O(log n)\*\*Requires manual implementationSearch (contains)O(n)O(n)Linear search fallbackRemoveO(n)O(n)Includes search timeIterationO(n)O(n)Similar performanceSizeO(1)O(1)Cached valueClearO(1)O(1)Reset references### Memory Usage

[](#memory-usage)

Data StructureMemory OverheadNotesSortedLinkedList~2.5xNode objects + referencesImmutableSortedLinkedList~1.5x per versionStructural sharing reduces overheadNative Array1x (baseline)Contiguous memory### Benchmark Results

[](#benchmark-results)

Performance benchmarks run on PHP 8.3 with 1000 elements:

#### Add Operations

[](#add-operations)

```
SortedLinkedList:     245.3 μs (±3.2%)
Native Array + sort:  112.7 μs (±2.1%)
Overhead:             2.18x

```

#### Search Operations (Binary vs Linear)

[](#search-operations-binary-vs-linear)

```
Binary Search (n=1000):  8.2 μs (±1.5%)
Linear Search (n=1000):  142.6 μs (±2.8%)
Speedup:                 17.4x for large datasets

```

#### Iterator Performance

[](#iterator-performance)

```
SortedLinkedList foreach:  89.3 μs (±1.9%)
Native array foreach:       31.2 μs (±1.2%)
Overhead:                   2.86x

```

#### Bulk Operations

[](#bulk-operations-1)

```
addAll (500 items):     312.5 μs (±2.5%)
removeAll (250 items):  198.7 μs (±2.1%)
filter (50%):           156.3 μs (±1.8%)
map transformation:     178.9 μs (±2.3%)

```

### When to Use SortedLinkedList

[](#when-to-use-sortedlinkedlist)

**Use SortedLinkedList when:**

- You need automatic sorting with every insertion
- Binary search optimization is important
- You need custom comparison logic
- Immutability and thread safety are required
- You frequently filter/map/reduce collections
- Type safety is important

**Use Native Arrays when:**

- Memory usage is critical
- Data is inserted in bulk then sorted once
- Simple numeric indices are sufficient
- Maximum iteration speed is required

Advanced Usage
--------------

[](#advanced-usage)

### Custom Comparators

[](#custom-comparators)

```
use SortedLinkedList\ImmutableSortedLinkedList;
use SortedLinkedList\Comparator\DateComparator;
use SortedLinkedList\Comparator\ObjectComparator;
use SortedLinkedList\Comparator\ReverseComparator;
use SortedLinkedList\Comparator\ChainComparator;

// Date sorting
$dateComparator = new DateComparator('Y-m-d');
$dateList = new ImmutableSortedLinkedList($dateComparator);
$dateList = $dateList->addAll(['2024-03-15', '2024-01-10', '2024-02-20']);

// Object property sorting
$users = [
    (object)['name' => 'Alice', 'age' => 30],
    (object)['name' => 'Bob', 'age' => 25],
];
$ageComparator = new ObjectComparator('age');
$userList = new ImmutableSortedLinkedList($ageComparator);
$userList = $userList->addAll($users);

// Reverse order
$reverseNumeric = new ReverseComparator(new NumericComparator());
$reverseList = new ImmutableSortedLinkedList($reverseNumeric);

// Multiple criteria (sort by age, then name)
$chainedComparator = new ChainComparator([
    new ObjectComparator('age'),
    new ObjectComparator('name')
]);
```

### Immutable Operations

[](#immutable-operations)

```
use SortedLinkedList\ImmutableSortedLinkedList;

$original = new ImmutableSortedLinkedList(new NumericComparator());
$original = $original->addAll([1, 2, 3, 4, 5]);

// Each operation returns a new instance
$version1 = $original->add(6);
$version2 = $original->remove(3);
$version3 = $version1->filter(fn($v) => $v % 2 === 0);

// All versions are independent
echo $original->size(); // 5
echo $version1->size(); // 6
echo $version2->size(); // 4
echo $version3->size(); // 3 (only even numbers from version1)
```

### Performance Monitoring

[](#performance-monitoring)

```
$list = new IntegerSortedLinkedList();
$list->resetStats();

// Perform operations
for ($i = 0; $i < 1000; $i++) {
    $list->add(random_int(1, 10000));
}

for ($i = 0; $i < 100; $i++) {
    $list->binarySearch(random_int(1, 10000));
}

// Get performance statistics
$stats = $list->getStats();
echo "Comparisons: " . $stats['comparisons'] . "\n";
echo "Node traversals: " . $stats['traversals'] . "\n";
```

Running Benchmarks
------------------

[](#running-benchmarks)

```
# Run all benchmarks
composer bench

# Run specific benchmark group
vendor/bin/phpbench run --group=search

# Compare with baseline
composer bench-compare

# Memory usage analysis
composer bench-memory

# Generate HTML report
vendor/bin/phpbench run --report=html --output=html
```

Testing
-------

[](#testing)

```
# Run all tests
composer test

# Run with coverage
composer test-coverage

# Run PHPStan analysis
composer analyse

# Run everything
composer check
```

Contributing
------------

[](#contributing)

Contributions are welcome! Please feel free to submit a Pull Request. Make sure to:

1. Add tests for new features
2. Update benchmarks if performance-related
3. Run `composer check` before submitting
4. Follow PSR-12 coding standards

License
-------

[](#license)

This project is licensed under the MIT License - see the LICENSE file for details.

Performance Optimization Tips
-----------------------------

[](#performance-optimization-tips)

1. **Use Binary Search**: For large datasets (&gt;100 elements), always prefer `binarySearch()` over `contains()`
2. **Bulk Operations**: Use `addAll()` instead of multiple `add()` calls for better performance
3. **Immutable Lists**: Use for concurrent access or when you need to maintain multiple versions
4. **Custom Comparators**: Implement efficient comparison logic to minimize operations
5. **Stats Monitoring**: Use `getStats()` in development to identify performance bottlenecks

Roadmap
-------

[](#roadmap)

- Persistent data structure variant
- Lazy evaluation for map/filter operations
- Parallel processing for bulk operations
- Memory-mapped file backend for huge datasets
- Redis/Memcached adapters
- Serialization support for data persistence

###  Health Score

30

—

LowBetter than 64% of packages

Maintenance62

Regular maintenance activity

Popularity0

Limited adoption so far

Community6

Small or concentrated contributor base

Maturity45

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

241d ago

### Community

Maintainers

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

---

Top Contributors

[![uniacid](https://avatars.githubusercontent.com/u/209640?v=4)](https://github.com/uniacid "uniacid (43 commits)")

---

Tags

iteratorcollectionsortinglinked listtype-safepsr-12data structurebinary searchsorted-list

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan

Code StylePHP\_CodeSniffer

Type Coverage Yes

### Embed Badge

![Health badge](/badges/uniacid-sortedlinkedlist/health.svg)

```
[![Health](https://phpackages.com/badges/uniacid-sortedlinkedlist/health.svg)](https://phpackages.com/packages/uniacid-sortedlinkedlist)
```

###  Alternatives

[loophp/collection

A (memory) friendly, easy, lazy and modular collection class.

745663.8k13](/packages/loophp-collection)[athari/yalinqo

YaLinqo, a LINQ-to-objects library for PHP

4561.2M5](/packages/athari-yalinqo)[chdemko/sorted-collections

Sorted Collections for PHP &gt;= 8.2

222.5M3](/packages/chdemko-sorted-collections)[gamez/typed-collection

Type-safe collections based on Laravel Collections

45317.8k](/packages/gamez-typed-collection)[graze/sort

A collection of array sorting transforms and functions

12289.6k2](/packages/graze-sort)[rotexsoft/versatile-collections

A collection package that can be extended to implement things such as a Dependency Injection Container, RecordSet objects for housing database records, a bag of http cookies, or technically any collection of items that can be looped over and whose items can each be accessed using array-access syntax or object property syntax.

186.0k1](/packages/rotexsoft-versatile-collections)

PHPackages © 2026

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