<?php
class ListNode
{
public $data = NULL;
public $next = NULL;
function __construct(string $data = NULL)
{
$this->data = $data;
}
}
class LinkedList
{
private $_firstNode = NULL;
private $_lastNode = NULL;
private $_totalNodes = 0;
function insert(string $data = NULL)
{
$newNode = new ListNode($data);
if($this->_firstNode === NULL){
$this->_firstNode = &$newNode;
$this->_lastNode = $this->_firstNode;
$this->_totalNodes++;
return true;
}
$curentNode = $this->_firstNode;
while($curentNode->next !== NULL){
$curentNode = $curentNode->next;
}
$curentNode->next = $newNode;
$this->_lastNode = $newNode;
$this->_totalNodes++;
return true;
}
function printData(){
$pointer = $this->_firstNode;
if(!$pointer) return;
while($pointer != NULL){
echo $pointer->data . PHP_EOL;
$pointer = $pointer->next;
}
}
function returnListSize(){
return $this->_totalNodes;
}
function search($data = NULL){
if($this->_totalNodes){
$currentNode = $this->_firstNode;
while($currentNode !== NULL){
if($data == $currentNode->data){
return $currentNode;
}
$currentNode = $currentNode->next;
}
}
return FALSE;
}
function insertBefore($data = NULL, $search = NULL){
$newNode = new ListNode($data);
if($this->_firstNode){
$currentNode = $this->_firstNode;
$prevNode = NULL;
while($currentNode !== NULL){
// insert before first node
if($this->_firstNode->data == $search){
$newNode->next = $currentNode;
$this->_firstNode = $newNode;
$this->_totalNodes++;
return true;
}
// insert between nodes
if($currentNode->data == $search){
$prevNode->next = $newNode;
$newNode->next = $currentNode;
$this->_totalNodes++;
return true;
}
$prevNode = $currentNode;
$currentNode = $currentNode->next;
}
}
return false;
}
function insertAfter($data = NULL, $search = NULL){
$newNode = new ListNode($data);
if($this->_firstNode){
$nextNode = NULL;
$currentNode = $this->_firstNode;
while($currentNode !== NULL){
// insert as last position
if($currentNode->next == NULL){
$currentNode->next = $newNode;
$this->_lastNode = $currentNode->next;
$this->_totalNodes++;
return true;
}
// insert after (between nodes)
if($currentNode->data == $search){
$nextNode = $currentNode->next;
$newNode->next = $nextNode;
$currentNode->next = $newNode;
$this->_totalNodes++;
return true;
}
// NOTE! The order do mater
$currentNode = $currentNode->next;
$nextNode = $currentNode->next;
}
}
return false;
}
public function removeFirst(){
if($this->_firstNode !== NULL){
$this->_firstNode = $this->_firstNode->next;
$this->_totalNodes--;
return true;
}else{
return false;
}
}
public function removeLast(){
if($this->_lastNode !== NULL){
$currentNode = $this->_firstNode;
$prevNode = NULL;
if($this->_firstNode === $this->_lastNode){
$this->_firstNode = $this->_lastNode = NULL;
$this->_totalNodes--;
return true;
}
while($currentNode !== NULL){
if($currentNode->next === $this->_lastNode){
$currentNode->next = NULL;
$this->_lastNode = $currentNode;
$this->_totalNodes--;
return true;
}
$prevNode = $currentNode;
$currentNode = $currentNode->next;
}
}else{
return false;
}
}
}
Testing PHP linked list
$l = new LinkedList();
$l->insert("Wiktor");
$l->insert("Wojtuś");
$l->insert("Kubuś");
$l->insertBefore("Justyna", "Wiktor");
$l->insertBefore("Kotek", "Justyna");
$l->insertAfter("Konrad", "Kubuś");
var_dump($l->removeFirst());
var_dump($l->removeLast());
$l->printData();
echo $l->returnListSize(). PHP_EOL;
echo ($l->search("Wiktor"))->data. PHP_EOL;
var_dump($l);