This is really a draft, but I somehow decided to post it. Here’s a simple linked list in PHP, where only the add() method is slightly different. When you have an item to add it’s placed on the “right” place – the result is a sorted list.
Few notes before the code! This list is designed for integers, but I plan to “extend” it somehow and it can be improved a lot. In my future posts I’ll post something more about the complexity of the algorithm and an analysis of it.
class Node { public $data; public $next; public $prev; public function __construct($data, $prev, $next) { $this->data = $data; $this->prev = $prev; $this->next = $next; } } class LinkedList { protected $front = null; public function add($data) { if (!$this->front) { $node = new Node($data, null, null); $this->front = &$node; } else { if ($data < $this->front->data) { $node = new Node($data, null, $this->front); $this->front = $node; return; } $current = $this->front; while ($current) { if ($current->data < $data && isset($current->next) && $current->next->data > $data) { $node = new Node($data, $current, $current->next); $current->next = $node; } if ($current->data < $data && !isset($current->next)) { $node = new Node($data, $current, $current->next); $current->next = $node; } $current = $current->next; } } } public function printl() { $current = &$this->front; while($current) { echo $current->data, '<br />'; $current = $current->next; } } } $list = new LinkedList(); $list->add(13); $list->add(14); $list->add(15); $list->add(11); $list->add(12); $list->add(17); $list->add(10); $list->add(16); $list->printl(); |