PHP实现的一个链式列表
<?php class Node { public $id; public $name; public $next; public function __construct($id, $name) { $this->id = $id; $this->name = $name; $this->next = NULL; } } /** * 链表中有两个特别重要的方法,插入和删除 * * 插入需要找到插入的位置,把前一个元素的next指针指向被插入的节点,并将被插入极端点的next指针指向后一个节点 * * 而删除则把前一个节点的next指针指向后一个节点,并返回被删除元素的数据内容。 * * */ class SimpleLinkedList { private $header; public function __construct($node = NULL) { is_null($node) && $node = new Node(NULL, NULL, NULL); $this->header = $node; } /** * 获取链式列表中的数据的个数 * @return int */ public function getLinkLength() { $count = 0; $current = $this->header; while (!is_null($current->next)) { $count++; $current = $current->next; } return $count; } /** * 向链式列表中添加数据,里面有一个条件 * 检测了要插入的节点元素id的大小,最终将导致一个id从小到大的排序 * * @param $node */ public function addLink($node) { $current = $this->header; //如果$current->next 是null 就退退出while循环 while ($current->next != NULL) { if ($current->next->id > $node->id) break; $current = $current->next; } $node->next = $current->next; $current->next = $node; } /** * 删除一个id的链表, * 这里需要着重说一说,怎么删除 * * 删除时,需要知道 删除元素的上一个元素是谁 * * 删除元素的下一个元素是谁, * * 这两个元素需要做一个对接 * * 这样就能保证 链式列表不断链。 * @param $id */ public function delLink($id) { $current = $this->header; $flag = FALSE; while (!is_null($current->next)) { if ($current->next->id == $id) { $flag = TRUE; break; } $current = $current->next; } if ($flag) { $current->next = $current->next->next; } } /** * 判断链式列表是否为空 * @return bool */ public function is_empty() { return is_null($this->header->next) ? TRUE : FALSE; } /** * 获取指定id元素的名称或列表 * @param $id * @return null */ public function getLinkNameById($id) { $current = $this->header; while (!is_null($current->next)) { if ($current->id === $id) { return $current->name; } $current = $current->next; } return NULL; } /** * 更新指定id的对象 * @param $id * @param $name * @return mixed */ public function updateLink($id, $name) { $current = $this->header; while (!is_null($current->next)) { if ($current->id == $id) { break; } $current = $current->next; } return $current->name = $name; } /** * 获取链式列表中的数据 * @return array|void */ public function getLinkList() { $current = $this->header; if (is_null($current->next)) { echo("链表为空!"); return; } $data = []; while (!is_null($current->next)) { $data[] = $current->next; $current = $current->next; } return $data; } } $linkList = new SimpleLinkedList(); $linkList->addLink(new Node(1, 'james')); $linkList->addLink(new Node(2, 'shiree')); $linkList->addLink(new Node(5, 'jim')); $linkList->addLink(new Node(3, 'jon')); $linkList->updateLink(3, '123123'); /*echo $linkList->getLinkNameById(3); $data=$linkList->getLinkList(); print_r($data); var_dump($linkList->getLinkLength()); */ $linkList->delLink(3); var_dump($linkList->getLinkLength()); $data = $linkList->getLinkList(); print_r($data); // $data=$linkList->getLinkList(); //