Download the PHP package uniacid/sortedlinkedlist without Composer

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.

Table of Contents

• Features
• Requirements
• Installation
• Quick Start
• Documentation
• Performance Characteristics
• Advanced Usage
• Testing
• Contributing
• License

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

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

Installation

Quick Start

Usage Examples

Basic Operations with Different Types

Binary Search and Contains

Collection Operations

Bulk Operations

Array Access Interface

Iterator and Foreach

Converting to Array

Documentation

• API Documentation - Complete class and method references
• Usage Examples - Detailed examples for all features
• Performance Guide - Benchmarks and optimization tips
• Contributing Guidelines - How to contribute to the project

Performance Characteristics

Time Complexity

Memory Usage

Benchmark Results

Performance benchmarks run on PHP 8.3 with 1000 elements:

Add Operations

Search Operations (Binary vs Linear)

Iterator Performance

Bulk Operations

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

Custom Comparators

Immutable Operations

Performance Monitoring

Running Benchmarks

Testing

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

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

Performance Optimization Tips

1. Use Binary Search: For large datasets (>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

• [ ] 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