PHPackages obernard/linkedlist - PHPackages - PHPackages [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register) 1. [Directory](/) 2. / 3. [Utility & Helpers](/categories/utility) 4. / 5. obernard/linkedlist ActiveLibrary[Utility & Helpers](/categories/utility) obernard/linkedlist =================== Data Storage based on linkedlist v4.1.1(3y ago)013.3k↓50%MITPHPPHP >=8.0 Since Nov 26Pushed 3y ago1 watchersCompare [ Source](https://github.com/pytoccaz/php-linkedlist)[ Packagist](https://packagist.org/packages/obernard/linkedlist)[ RSS](/packages/obernard-linkedlist/feed)WikiDiscussions main Synced 1mo ago READMEChangelogDependencies (2)Versions (26)Used By (0) 🖇 LinkedList ============ [](#-linkedlist) Linked List implementation in PHP. Installation ------------ [](#installation) ``` composer require obernard/linkedlist ``` Usage of final class LifoList ----------------------------- [](#usage-of-final-class-lifolist) Final classes like `LifoList` are given as examples of implementation of abstract linked-list classes but extending `AbstractSinglyLinkedList` or `AbstractDoublyLinkedList` offers much more coding potentials. Create an empty list and add nodes. ``` $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 ``` Usage of Abstract classes ------------------------- [](#usage-of-abstract-classes) Abstract singly-linked list supports the use of abstract doubly-linked nodes but as a good practice use singly linked nodes inside singly-linked lists. Your concrete list class links instances of your concrete node classe. Concrete list classes may create node objects - like `LifoList` class does - or may not. In this example, `MyList` class does not create nodes by itself: ``` // 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()) } ``` A Node classe implements `IterableNodeInterface` `getKey` and `getValue` methods through `AbstractNode`. You may need to replace one or the other. - `getValue` method determines what is returned as value when iterating the list. In above example, we decide that `foreach` statement iterate over `$data` node property. If you want to iterate over Node objects, do not replace `getValue` because `AbstractNode->getValue()` already returns `$this`. - `getKey` method determines what is returned as key when iterating the list. `AbstractNode->getkey()` argument `$index` is binded with the iterator position index. But you can replace the method and make it return whatever suites your needs. @see `AbstractCommonList` `key()` and `current()` methods to see how the magic works. Dialogue between nodes ---------------------- [](#dialogue-between-nodes) An interesting design pattern is to make nodes communicate through the list. See `AbstractNode` `distanceToLastNode()` method as an example of inter-nodes communication: ``` // 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; } } ``` This design pattern is based on recursivity. The time complexity of such recursive methods is `0(n)` where `n` is the number of nodes. **If your configuration has `xdebug` module enabled, the use of such recursive function calls may raise the following error if your list length get close to 256:** ``` Error: Maximum function nesting level of '256' reached, aborting! ``` If you don't want to modify your `xdebug` config by increasing the `xdebug.max_nesting_level` setting, just don't use that pattern design for long lists. **Be carefull not to use recursive communication methods between nodes when iterating over nodes because the time complexity would be O(n2) leading to very poor performance.** ``` // very low 0(n) < perf < 0(n^2) for ($i=0; $ilength(); $i++) { $list->head($i); } // very very low perf ~ O(n^2) ... for ($i=0; $ilength(); $i++) { $list->head($i)->distanceToLastNode(); } ``` Tests ----- [](#tests) Run `composer test`. Contributing ------------ [](#contributing) Improvements are welcome! Feel free to submit pull requests. Licence ------- [](#licence) MIT Copyright (c) 2021 Olivier BERNARD ### Health Score 32 — LowBetter than 72% of packages Maintenance20 Infrequent updates — may be unmaintained Popularity23 Limited adoption so far Community7 Small or concentrated contributor base Maturity65 Established project with proven stability Bus Factor1 Top contributor holds 100% of commits — single point of failure How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window. **Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores. **Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement. **Maturity (30%)** — Project age, version count, PHP version support, and release stability. ### Release Activity Cadence Every ~21 days Recently: every ~52 days Total 24 Last Release 1144d ago Major Versions v0.x-dev → v1.02021-11-29 v1.3.1 → v2.02021-12-31 v1.3.3 → v2.0.32022-01-11 v2.0.4 → v3.02022-09-02 v3.x-dev → v4.02022-09-07 PHP version history (2 changes)v0.1PHP >=7.4.0 v2.0PHP >=8.0 ### Community Maintainers ![](https://avatars.githubusercontent.com/u/352725?v=4)[obernard](/maintainers/obernard)[@obernard](https://github.com/obernard) --- Top Contributors [![pytoccaz](https://avatars.githubusercontent.com/u/41835171?v=4)](https://github.com/pytoccaz "pytoccaz (2 commits)") --- Tags linked-listphpiteratorcollectionLinkedListSinglyLinkedListDoublyLinkedList ### Code Quality TestsPHPUnit ### Embed Badge ![Health badge](/badges/obernard-linkedlist/health.svg) ``` [![Health](https://phpackages.com/badges/obernard-linkedlist/health.svg)](https://phpackages.com/packages/obernard-linkedlist) ``` ### Alternatives [loophp/collection A (memory) friendly, easy, lazy and modular collection class. 745663.8k13](/packages/loophp-collection)[athari/yalinqo YaLinqo, a LINQ-to-objects library for PHP 4561.2M5](/packages/athari-yalinqo)[chdemko/sorted-collections Sorted Collections for PHP >= 8.2 222.5M3](/packages/chdemko-sorted-collections)[rotexsoft/versatile-collections A collection package that can be extended to implement things such as a Dependency Injection Container, RecordSet objects for housing database records, a bag of http cookies, or technically any collection of items that can be looped over and whose items can each be accessed using array-access syntax or object property syntax. 186.0k1](/packages/rotexsoft-versatile-collections) PHPackages © 2026 [Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)