Внедрить связанный список в php

Существует SplDoublyLinkedList . Это тоже хорошо?

Ниже приведен пример реализации связанного списка в PHP: http://www.codediesel.com/php/linked-list-in-php/, который может добавлять, удалять, реверсировать и удалять связанный список в PHP.

 <?php class ListNode { public $data; public $next; function __construct($data) { $this->data = $data; $this->next = NULL; } function readNode() { return $this->data; } } class LinkList { private $firstNode; private $lastNode; private $count; function __construct() { $this->firstNode = NULL; $this->lastNode = NULL; $this->count = 0; } //insertion at the start of linklist public function insertFirst($data) { $link = new ListNode($data); $link->next = $this->firstNode; $this->firstNode = &$link; /* If this is the first node inserted in the list then set the lastNode pointer to it. */ if($this->lastNode == NULL) $this->lastNode = &$link; $this->count++; } //displaying all nodes of linklist public function readList() { $listData = array(); $current = $this->firstNode; while($current != NULL) { array_push($listData, $current->readNode()); $current = $current->next; } foreach($listData as $v){ echo $v." "; } } //reversing all nodes of linklist public function reverseList() { if($this->firstNode != NULL) { if($this->firstNode->next != NULL) { $current = $this->firstNode; $new = NULL; while ($current != NULL) { $temp = $current->next; $current->next = $new; $new = $current; $current = $temp; } $this->firstNode = $new; } } } //deleting a node from linklist $key is the value you want to delete public function deleteNode($key) { $current = $this->firstNode; $previous = $this->firstNode; while($current->data != $key) { if($current->next == NULL) return NULL; else { $previous = $current; $current = $current->next; } } if($current == $this->firstNode) { if($this->count == 1) { $this->lastNode = $this->firstNode; } $this->firstNode = $this->firstNode->next; } else { if($this->lastNode == $current) { $this->lastNode = $previous; } $previous->next = $current->next; } $this->count--; } //empty linklist public function emptyList() { $this->firstNode == NULL; } //insertion at index public function insert($NewItem,$key){ if($key == 0){ $this->insertFirst($NewItem); } else{ $link = new ListNode($NewItem); $current = $this->firstNode; $previous = $this->firstNode; for($i=0;$i<$key;$i++) { $previous = $current; $current = $current->next; } $previous->next = $link; $link->next = $current; $this->count++; } } } $obj = new LinkList(); $obj->insertFirst($value); $obj->insert($value,$key); // at any index $obj->deleteNode($value); $obj->readList(); 

Вот код в php, который реализует Linked List, только с ссылкой на главный узел, то есть на первый узел, а затем вы добавляете сначала, последний и удаляете ключ, а также сохраняете код ключей в списке.

 <?php /** * Class Node */ class Node { public $data; public $next; public function __construct($item) { $this->data = $item; $this->next = null; } } /** * Class LinkList */ class LinkList { public $head = null; private static $count = 0; /** * @return int */ public function GetCount() { return self::$count; } /** * @param mixed $item */ public function InsertAtFist($item) { if ($this->head == null) { $this->head = new Node($item); } else { $temp = new Node($item); $temp->next = $this->head; $this->head = $temp; } self::$count++; } /** * @param mixed $item */ public function InsertAtLast($item) { if ($this->head == null) { $this->head = new Node($item); } else { /** @var Node $current */ $current = $this->head; while ($current->next != null) { $current = $current->next; } $current->next = new Node($item); } self::$count++; } /** * Delete the node which value matched with provided key * @param $key */ public function Delete($key) { /** @var Node $current */ $current = $previous = $this->head; while($current->data != $key) { $previous = $current; $current = $current->next; } // For the first node if ($current == $previous) { $this->head = $current->next; } $previous->next = $current->next; self::$count--; } /** * Print the link list as string like 1->3-> ... */ public function PrintAsList() { $items = []; /** @var Node $current */ $current = $this->head; while($current != null) { array_push($items, $current->data); $current = $current->next; } $str = ''; foreach($items as $item) { $str .= $item . '->'; } echo $str; echo PHP_EOL; } } $ll = new LinkList(); $ll->InsertAtLast('KP'); $ll->InsertAtLast(45); $ll->InsertAtFist(11); $ll->InsertAtLast('FE'); $ll->InsertAtFist('LE'); $ll->InsertAtFist(100); $ll->InsertAtFist(199); $ll->InsertAtLast(500); $ll->PrintAsList(); echo 'Total elements ' . $ll->GetCount(); echo PHP_EOL; $ll->Delete(45); $ll->PrintAsList(); echo 'Total elements ' . $ll->GetCount(); echo PHP_EOL; $ll->Delete(500); $ll->PrintAsList(); echo 'Total elements ' . $ll->GetCount(); echo PHP_EOL; $ll->Delete(100); $ll->PrintAsList(); echo 'Total elements ' . $ll->GetCount(); echo PHP_EOL; 

Код:

 $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 - $ php LinkList.php 199->100->LE->11->KP->45->FE->500-> Total elements 8 199->100->LE->11->KP->FE->500-> Total elements 7 199->100->LE->11->KP->FE-> Total elements 6 199->LE->11->KP->FE-> Total elements 5 

Я также пытался написать программу для создания связанного списка в PHP. Вот что я написал, и это сработало для меня. Надеюсь, это поможет ответить на вопрос.

 Created a php file. Name: LinkedList.php {code} <?php require_once (__DIR__ . "/LinkedListNodeClass.php"); $node_1 = new Node(); Node::createNode($node_1, 5); echo "\n Node 1 is created."; $head = &$node_1; echo "\n Head is intialized with Node 1."; $node_2 = new Node(); Node::createNode($node_2, 1); echo "\n Node 2 is created."; Node::insertNodeInLinkedList($head, $node_2); $node_3 = new Node(); Node::createNode($node_3, 11); echo "\n Node 3 is created."; Node::insertNodeInLinkedList($head, $node_3); $node_4 = new Node(); Node::createNode($node_4, 51); echo "\n Node 4 is created."; Node::insertNodeInLinkedList($head, $node_4); $node_5 = new Node(); Node::createNode($node_5, 78); echo "\n Node 5 is created."; Node::insertNodeInLinkedList($head, $node_5); $node_6 = new Node(); Node::createNode($node_6, 34); echo "\n Node 6 is created."; Node::insertNodeInLinkedList($head, $node_6); $node_7 = new Node(); Node::createNode($node_7, 99); echo "\n Node 7 is created."; Node::insertNodeInHeadOfLinkedList($head, $node_7); $node_8 = new Node(); Node::createNode($node_8, 67); echo "\n Node 8 is created."; Node::insertNodeInHeadOfLinkedList($head, $node_8); $node_9 = new Node(); Node::createNode($node_9, 101); echo "\n Node 9 is created."; Node::insertNodeAfterAPositionInLinkedList($head, 5, $node_9); $node_10 = new Node(); Node::createNode($node_10, 25); echo "\n Node 10 is created."; Node::insertNodeAfterAPositionInLinkedList($head, 2, $node_10); echo "\n Displaying the linked list: \n"; Node::displayLinkedList($head); ?> {code} This file is calling a class to create, insert and display nodes in linked list. Name: LinkedListNodeClass.php {code} <?php class Node { private $data; private $next; public function __construct() { //does nothing... } //Creates a node public function createNode($obj, $value) { $obj->data = $value; $obj->next = NULL; } //Inserts a created node in the end of a linked list public function insertNodeInLinkedList($head, &$newNode) { $node = $head; while($node->next != NULL){ $node = $node->next; } $node->next = $newNode; } //Inserts a created node in the start of a linked list public function insertNodeInHeadOfLinkedList(&$head, &$newNode) { $top = $head; $newNode->next = $top; $head = $newNode; } //Inserts a created node after a position of a linked list public function insertNodeAfterAPositionInLinkedList($head, $position, &$newNode) { $node = $head; $counter = 1; while ($counter < $position){ $node = $node->next; $counter++; } $newNode->next = $node->next; $node->next = $newNode; } //Displays the Linked List public function displayLinkedList($head) { $node = $head; print($node->data); echo "\t"; while($node->next != NULL){ $node = $node->next; print($node->data); echo "\t"; } } } ?> {code} 

Вот еще одна реализация Linked list, использующая массив элементов. Функция add сохраняет элементы отсортированными.

 <?php class LinkedList{ private $_head = null; private $_list = array(); public function addNode($val) { // add the first element if(empty($this->_list)) { $this->_head = $val; $this->_list[$val] = null; return; } $curr = $this->_head; while ($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { $this->_list[$curr] = $val; $this->_list[$val] = null; return; } if($this->_list[$curr] < $val) { $curr = $this->_list[$curr]; continue; } $this->_list[$val] = $this->_list[$curr]; $this->_list[$curr] = $val; return; } } public function deleteNode($val) { if(empty($this->_list)) { return; } $curr = $this->_head; if($curr == $val) { $this->_head = $this->_list[$curr]; unset($this->_list[$curr]); return; } while($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { return; } if($this->_list[$curr] == $val) { $this->_list[$curr] = $this->_list[$val]; unset($this->_list[$val]); return; } $curr = $this->_list[$curr]; } } function showList(){ $curr = $this->_head; while ($curr != null || $curr === 0) { echo "-" . $curr; $curr = $this->_list[$curr]; } } } $list = new LinkedList(); $list->addNode(0); $list->addNode(3); $list->addNode(7); $list->addNode(5); $list->addNode(2); $list->addNode(4); $list->addNode(10); $list->showList(); echo PHP_EOL; $list->deleteNode(3); $list->showList(); echo PHP_EOL; $list->deleteNode(0); $list->showList(); echo PHP_EOL; с <?php class LinkedList{ private $_head = null; private $_list = array(); public function addNode($val) { // add the first element if(empty($this->_list)) { $this->_head = $val; $this->_list[$val] = null; return; } $curr = $this->_head; while ($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { $this->_list[$curr] = $val; $this->_list[$val] = null; return; } if($this->_list[$curr] < $val) { $curr = $this->_list[$curr]; continue; } $this->_list[$val] = $this->_list[$curr]; $this->_list[$curr] = $val; return; } } public function deleteNode($val) { if(empty($this->_list)) { return; } $curr = $this->_head; if($curr == $val) { $this->_head = $this->_list[$curr]; unset($this->_list[$curr]); return; } while($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { return; } if($this->_list[$curr] == $val) { $this->_list[$curr] = $this->_list[$val]; unset($this->_list[$val]); return; } $curr = $this->_list[$curr]; } } function showList(){ $curr = $this->_head; while ($curr != null || $curr === 0) { echo "-" . $curr; $curr = $this->_list[$curr]; } } } $list = new LinkedList(); $list->addNode(0); $list->addNode(3); $list->addNode(7); $list->addNode(5); $list->addNode(2); $list->addNode(4); $list->addNode(10); $list->showList(); echo PHP_EOL; $list->deleteNode(3); $list->showList(); echo PHP_EOL; $list->deleteNode(0); $list->showList(); echo PHP_EOL; с <?php class LinkedList{ private $_head = null; private $_list = array(); public function addNode($val) { // add the first element if(empty($this->_list)) { $this->_head = $val; $this->_list[$val] = null; return; } $curr = $this->_head; while ($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { $this->_list[$curr] = $val; $this->_list[$val] = null; return; } if($this->_list[$curr] < $val) { $curr = $this->_list[$curr]; continue; } $this->_list[$val] = $this->_list[$curr]; $this->_list[$curr] = $val; return; } } public function deleteNode($val) { if(empty($this->_list)) { return; } $curr = $this->_head; if($curr == $val) { $this->_head = $this->_list[$curr]; unset($this->_list[$curr]); return; } while($curr != null || $curr === 0) { // end of the list if($this->_list[$curr] == null) { return; } if($this->_list[$curr] == $val) { $this->_list[$curr] = $this->_list[$val]; unset($this->_list[$val]); return; } $curr = $this->_list[$curr]; } } function showList(){ $curr = $this->_head; while ($curr != null || $curr === 0) { echo "-" . $curr; $curr = $this->_list[$curr]; } } } $list = new LinkedList(); $list->addNode(0); $list->addNode(3); $list->addNode(7); $list->addNode(5); $list->addNode(2); $list->addNode(4); $list->addNode(10); $list->showList(); echo PHP_EOL; $list->deleteNode(3); $list->showList(); echo PHP_EOL; $list->deleteNode(0); $list->showList(); echo PHP_EOL; 

Выход:

-0-2-3-4-5-7-10

-0-2-4-5-7-10

-2-4-5-7-10

Если вы не думаете, что большинство людей понимают, что такое связанные списки. Основная идея заключается в том, что вы хотите сохранить организованные данные таким образом, чтобы вы могли получить доступ к предыдущему и следующему узлу с использованием текущего узла. Другие функции, такие как добавление, удаление, вставка, голова и т. Д., Являются сахаром, хотя это необходимо. Я думаю, пакет SPL действительно покрывает много. Проблема в том, что мне нужен класс PHP 5.2.9. Думаю, я должен сам это реализовать.