测试代码:
<?php $list = new SplDoublyLinkedList(); for ($i = 0; $i < 2000001; $i++) { $list->push($i); } $s = microtime(true); //$res = $list->offsetGet(2000000); // 7 ms $res = $list->offsetGet(0); // 0.07 ms var_dump($res); $e = microtime(true); echo ($e - $s) * 1000; //计算差值 毫秒
可以看到获取头部节点耗时远远低于尾部节点,可以推测SplDoublyLinkedList的offsetGet时间复杂度是O(n)
来自anson博客