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(); |
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();