SortedLinkedList (PHP 8.3)

A tiny, type-safe linked list that keeps values sorted at insertion time. Each list instance holds either integers or strings, never both.

---

Problem Statement

Implement a library providing SortedLinkedList that:

• Stores only one scalar type per instance: int or string
• Maintains sorted order when inserting
• Feels natural to use with count(), foreach, and json_encode()

---

What Was Used

• Language: PHP 8.3 with declare(strict_types=1)
• Design: Simple linked list that inserts in order
• Interfaces: IteratorAggregate, Countable, JsonSerializable
• Enum: ValueType to lock an instance to int or string
• Typing: Union types (int|string), readonly constructor args
• Generics: PHPDoc templates for static analysis (@template T of int|string)

---

Requirements

• PHP 8.3
• Composer 2.x

---

Installation and Running

# Clone
git clone https://github.com/YOUR_USERNAME/shipmonk-sorted-linked-list.git
cd shipmonk-sorted-linked-list

# Install dependencies
composer install

# Run unit tests
composer test

# Run static analysis
composer stan

# Check coding standards
composer cs

---

Example Usage

<?php

use ShipMonk\Collections\SortedLinkedList;

// Int list, ascending by default
$ints = SortedLinkedList::forInt();
$ints->insert(5);
$ints->insert(1);
$ints->insert(10);

echo $ints->first();        // 1
echo $ints->last();         // 10
print_r($ints->toArray());  // [1, 5, 10]
echo count($ints);          // 3

// String list, descending
$strings = SortedLinkedList::forString(ascending: false);
$strings->insert('alpha');
$strings->insert('charlie');
$strings->insert('bravo');

print_r($strings->toArray()); // ['charlie', 'bravo', 'alpha']

// Remove, contains, clear
$ints->remove(5);              // true
var_dump($ints->contains(5));  // false
$ints->clear();                // empties the list

---

API Overview

SortedLinkedList::forInt(bool $ascending = true): self
SortedLinkedList::forString(bool $ascending = true): self
SortedLinkedList::fromArray(array $values, ValueType $type, bool $ascending = true): self

insert(int|string $value): void
remove(int|string $value): bool
contains(int|string $value): bool
first(): int|string|null
last(): int|string|null
isEmpty(): bool
toArray(): array
clear(): void
count(): int
getIterator(): Traversable
jsonSerialize(): array

---

Expectations From the Library

• Sorted order is guaranteed after every insert
• Each instance is homogeneous: either all ints or all strings
• Natural to use with native PHP functions and patterns
• Clear errors for misuse

---

Algorithm

• Data structure: Singly linked list with sorted insertion
• On insert: Traverse from the head until the correct position is found
• Maintain tail pointer: To make last() constant time

---

Testing and Quality

• PHPUnit: Unit tests cover ints, strings, duplicates, remove, clear, factories, and type errors
• PHPStan: Max level with template annotations
• PHPCS: PSR-12 ruleset

Useful Commands

composer test     # run tests
composer stan     # static analysis (level max)
composer cs       # coding standards
composer cs:fix   # auto-fix common style issues

---

Project Structure

src/
  SortedLinkedList.php
  ValueType.php
  Node.php
tests/
  SortedLinkedListTest.php
.github/workflows/
  ci.yml
composer.json
phpunit.xml
phpstan.neon.dist
phpcs.xml
README.md