README

PHP中的链表实现。

安装

composer require obernard/linkedlist

使用final类LifoList

如LifoList之类的final类是抽象链表类的实现示例，但扩展AbstractSinglyLinkedList或AbstractDoublyLinkedList提供了更多的编码潜力。

创建一个空列表并添加节点。

$stack = new Obernard\LinkedList\Collection\LifoList;

$stack->push('hello');
$stack->push(1);
$stack->push(['test1', 'test2']);

foreach ($stack as $key, $value) {
    // do something 
}

$l = $stack->length() // 3

$node = $stack->pop(); // ['test1', 'test2']

$l = $stack->length() // 2

$node = $stack->pop(); // 1

$l = $stack->length() // 1

使用抽象类

抽象单链表支持使用抽象双链表节点，但作为良好实践，在单链表中使用单链表节点。

您的具体列表类链接您的具体节点类的实例。具体列表类可以创建节点对象，例如LifoList类所做的那样，也可以不创建。

在本例中，MyList类不自己创建节点

// MyList.php

class MyList extends AbstractSinglyLinkedList {
    
}

// MyNode.php
class MyNode extends AbstractSinglyLinkedNode {

    public $data;
    public function __construct($data) {
        $this->data = $data;
    }

    // IterableNodeInterface getValue method:
    public function getValue() {
        return $this->data;
    }

}

// program.php

$list= new MyList();

$list->pushToHead(new MyNode("test1"))->pushToHead(new MyNode("test2"));

foreach ($list as $key => $value) {
    // do something with $value string (returned by MyNode->getValue()) and $key (MyNode->getKey())
}

节点类通过AbstractNode实现IterableNodeInterface的getKey和getValue方法。您可能需要替换其中一个或两个。

• getValue方法确定迭代列表时返回的值。

在上面的示例中，我们决定foreach语句迭代$data节点属性。

如果您想迭代节点对象，不要替换getValue，因为AbstractNode->getValue()已经返回了$this。

• getKey方法确定迭代列表时返回的键。AbstractNode->getkey()参数$index与迭代器的位置索引绑定。但您可以替换该方法并使其返回适合您需求的任何内容。

@see AbstractCommonList的key()和current()方法，以了解魔法是如何工作的。

节点之间的对话

一个有趣的设计模式是通过列表使节点进行通信。

以AbstractNode的distanceToLastNode()方法作为节点间通信的示例

// AbstractNode.php

    /**
     *  Returns the node's rank beginning at tail node (ie at the end).
     *  !! Time complexity is O(n) !!
     *  @return int 
     */
    public function distanceToLastNode():int {
        if ($this->isLast()) // if you Node are the last node just say 0
            return 0;
        else {
            // just ask your next node for its rank and increment 
            $nextNodeRrank=$this->next->distanceToLastNode();    
            return ++$nextNodeRrank; 
        }
    }

这种设计模式基于递归。

此类递归方法的复杂度是0(n)，其中n是节点的数量。

如果您的配置已启用xdebug模块，当您的列表长度接近256时，使用此类递归函数调用可能会引发以下错误

Error: Maximum function nesting level of '256' reached, aborting!    

如果您不想通过增加xdebug.max_nesting_level设置来修改您的xdebug配置，就请不要为长列表使用这种设计模式。

请注意，在迭代节点时不要使用节点之间的递归通信方法，因为复杂度将是O(n2)，从而导致非常差的性能。

// very low 0(n) < perf < 0(n^2)
for ($i=0; $i<$list->length(); $i++) {
    $list->head($i);
}
// very very low perf ~ O(n^2)  ...
for ($i=0; $i<$list->length(); $i++) {
    $list->head($i)->distanceToLastNode();
}

测试

运行composer test。

贡献

欢迎改进！请随时提交pull请求。

许可协议

MIT

版权所有 (c) 2021 Olivier BERNARD