Sorted Linked List

Development

Setup

# Clone the repository
git clone https://github.com/guccilive/sorted-linked-list.git
cd sorted-linked-list

# Install dependencies
composer install
# or
make install

Running Tests

# Run tests
composer test
# or
make test

# Run tests with coverage (requires Xdebug or PCOV)
composer test:coverage
# or
make coverage

Code Quality

# Run all checks (tests + phpstan + cs)
composer check
# or
make check

# Run PHPStan
composer phpstan
# or
make phpstan

# Check coding standards
composer cs
# or
make cs

# Fix coding standards
composer cs:fix
# or
make cs-fix

Pre-Commit Hook

The repository includes an optional pre-commit hook that automatically runs quality checks before each commit:

# The hook is already set up and will:
# 1. Auto-fix coding standards (composer cs:fix)
# 2. Run all checks (composer check)
# 3. Block commit if checks fail

# To bypass the hook (emergency only):
git commit --no-verify -m "your message"

# To run checks manually:
./pre-commit.sh

The pre-commit hook ensures code quality by catching issues before they reach the repository.

Code Coverage

To generate code coverage reports, you need to install a coverage driver.

Installing Xdebug (macOS with Homebrew)

pecl install xdebug

Installing PCOV (Lightweight alternative)

pecl install pcov

Then add to your php.ini:

extension=pcov.so
pcov.enabled=1

Once installed, run:

composer test:coverage  # HTML report
composer test:coverage-text  # Terminal output

✅ Type Safety: Enforces consistent types (int or string) throughout the list
⚡ Auto-Sorting: Elements maintain sorted order automatically on insertion
🎯 Optimized Operations: Early-exit algorithms for efficient searching
💾 Memory Efficient: Single-linked structure with minimal overhead
🔄 Standard Interfaces: Implements Countable and IteratorAggregate
📊 O(1) Count: Cached counter for instant size retrieval
🛡️ Final Classes: Prevents inheritance issues and enables JIT optimization

Installation

composer require guccilive/sorted-linked-list

Requirements

PHP >= 8.3.0

Usage

Basic Operations

use Guccilive\SortedLinkedList\SortedLinkedList;

// Create a new sorted list
$list = new SortedLinkedList();

// Insert values (automatically sorted)
$list->insert(30);
$list->insert(10);
$list->insert(20);

// Get as array
print_r($list->toArray()); // [10, 20, 30]

// Check if value exists
$list->contains(20); // true
$list->contains(40); // false

// Get by index
$list->get(0); // 10
$list->get(1); // 20

// Count elements
count($list); // 3
$list->isEmpty(); // false

// Remove value
$list->remove(20);
print_r($list->toArray()); // [10, 30]

// Clear all elements
$list->clear();

Type Safety

The list enforces type consistency - once the first element is inserted, all subsequent elements must be of the same type:

$list = new SortedLinkedList();
$list->insert(10);
$list->insert(20);

// This will throw TypeMismatchException
$list->insert('string'); // ❌ Error: List contains int values, but received string

String Support

Works perfectly with strings too:

$list = new SortedLinkedList();
$list->insert('delta');
$list->insert('alpha');
$list->insert('charlie');

print_r($list->toArray()); // ['alpha', 'charlie', 'delta']

Iteration

The list implements IteratorAggregate, so you can use it in foreach loops:

$list = new SortedLinkedList();
$list->insert(30);
$list->insert(10);
$list->insert(20);

foreach ($list as $value) {
    echo $value . "\n";
}
// Output:
// 10
// 20
// 30

Duplicates

Duplicate values are allowed:

$list = new SortedLinkedList();
$list->insert(20);
$list->insert(10);
$list->insert(20);

print_r($list->toArray()); // [10, 20, 20]

// Remove only removes first occurrence
$list->remove(20);
print_r($list->toArray()); // [10, 20]

API Reference