Utility classes

class LinkedNode
{
    /**
     * The previous node
     *
     * @var LinkedNode|null
     */
    private $prev = null;

    /**
     * The next node
     *
     * @var LinkedNode|null
     */
    private $next = null;

    /**
     * The value of the node
     *
     * @var mixed
     */
    private $value = null;

    /**
     * The list this node belongs to
     *
     * @var LinkedList
     */
    private $list = null;

    /**
     * Crate a new node
     *
     * @param mixed $value
     */
    public function __construct($value, $list) {
        $this->value = $value;
        $this->list = $list;
    }

    /**
     * Get the previous node
     *
     * @return LinkedNode|null
     */
    public function getPrev() {
        return $this->prev;
    }

    /**
     * Get the next node
     *
    * @return LinkedNode|null
     */
    public function getNext() {
        return $this->next;
    }

    /**
     * Get the value of this node
     *
     * @return mixed
     */
    public function getValue() {
        return $this->value;
    }

    /**
     * Set the previous node
     *
     * @param LinkedNode
     * @return void
     */
    public function setPrev($prev) {
        $this->prev = $prev;
    }

    /**
     * Set the next node
     *
     * @param LinkedList $next
     * @return void
     */
    public function setNext($next) {
        $this->next = $next;
    }

    /**
     * Set the value of this node
     *
     * @param mixed $value
     * @return void
     */
    public function setValue($value) {
        $this->value = $value;
    }

    /**
     * Remove this node from the list
     *
     * @return void
     */
    public function remove()
    {
        $this->getPrev()->setNext($this->getNext());
        $this->getNext()->setPrev($this->getPrev());
    }

    /**
     * Insert a node before this one
     *
     * @param mixed $value
     * @return LinkedNode The created node
     */
    public function insertBefore($value)
    {
        $node = new LinkedNode($value, $this->list);
        $node->setPrev($this->getPrev());
        $node->setNext($this);
        $this->getPrev()->setNext($node);
        $this->setPrev($node);
        return $node;
    }

    /**
     * Insert a node after this one
     *
     * @param mixed $value
     * @return LinkedNode The created node
     */
    public function insertAfter($value)
    {
        $node = new LinkedNode($value, $this->list);
        $node->setPrev($this);
        $node->setNext($this->getNext());
        $this->getNext()->setPrev($node);
        $this->setNext($node);
        return $node;
    }
}

class LinkedList
{
    /**
     * The head node of the list
     *
     * @var LinkedNode
     */
    private $head = null;

    /**
     * The list is circular
     *
     * @var boolean
     */
    private $is_circular = false;

    /**
     * Initialize the list with a first value
     *
     * @param mixed $head_value
     * @param boolean $circular The list is circular
     */
    public function __construct($head_value = null, $is_circular = false) {
        if (!is_null($head_value)) {
            $this->head = new LinkedNode($head_value, $this);
            if ($this->is_circular = $is_circular) {
                $this->head->setNext($this->head);
                $this->head->setPrev($this->head);
            }
        }
    }

    /**
     * Get the head of the list
     *
     * @return LinkedNode
     */
    public function getHead() {
        return $this->head;
    }

    /**
     * Get the tail of the list
     *
     * @return LinkedNode
     */
    public function getTail() {
        if ($this->is_circular) {
            return $this->head->getPrev();
        }

        $node = $this->head;
        while ($node->getNext()) {
            $node = $node->getNext();
        }
        return $node;
    }

    /**
     * The a node with a given value
     *
     * @param mixed $value
     * @return LinkedNode|null
     */
    public function getNodeWithValue($value)
    {
        $node = $this->head;
        while ($node) {
            if ($node->getValue() == $value) {
                return $node;
            }
            $node = $node->getNext();
        }
        return null;
    }

    /**
     * Add a node as the head of the list
     *
     * @param mixed $value Value of the node to unshift
     * @return LinkedNode THe created node
     */
    public function unshift($value)
    {
        $node = new LinkedNode($value, $this);

        if ($this->head) {
            $node->setPrev($this->head->getPrev());
            $node->setNext($this->head);
            $this->head->setPrev($node);
        }

        $this->head = $node;
        return $node;
    }

    /**
     * Add a node as the tail of the list
     *
     * @param mixed $value Value of the node to append
     * @return LinkedNode THe created node
     */
    public function append($value)
    {
        $node = new LinkedNode($value, $this);

        $tail = $this->getTail();
        if ($tail) {
            $node->setPrev($tail);
            $node->setNext($tail->getNext());
            $tail->setNext($node);
        } else {
            $this->head = $node;
        }

        return $node;
    }
}