【php实现数据结构】单向链表

什么是单向链表链表是以链式存储数据的结构，其不需要连续的存储空间，链表中的数据以节点来表示，每个节点由元素和指针组成。单向链表（也叫单链表）是链表中最简单的一种形式，每个节点只包含一个元素和一个指针。它有一个表头，并且除了最后一个节点外，所有节点都有其后继节点。它的存储结构如下图所示代码实现定义节点class Node{ public $data; /** * @var null | Node / public $next; public function __construct($data) { $this->data = $data; $this->next = null; }}单链表实现/* * Class SingleLinkList * 单链接的实现示例，实现简单的填加，插入，删除, 查询，长度，遍历这几个简单操作 /class SingleLinkList{ /* * 链表头结点，头节点必须存在， * @var Node / public $header; private $size = 0; /* * 构造函数，默认填加一个哨兵节点，该节点元素为空 * SingleLinkList constructor. / public function __construct() { $this->header = new Node(null); } /* * 添加节点 * @param Node $node * @return int / public function addNode(Node $node) { $current = $this->header; while ($current->next != null) { $current = $current->next; } $current->next = $node; return ++$this->size; } /* * 在指定位置查入节点 * @param int $index 节点位置，从1开始计数 * @param Node $node * @return int * @throws Exception / public function insertNodeByIndex($index, Node $node) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(sprintf(‘你要插入的位置，超过了链表的长度 %d’, $this->size)); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $node->next = $current->next; $current->next = $node; break; } } while ($current->next != null && ($current = $current->next)); return ++$this->size; } /* * 删除节点 * @param int $index 节点位置，从1开始计数 * @return int * @throws Exception / public function deleteNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(‘你删除的节点不存在’); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $current->next = $current->next->next; break; } } while ($current->next != null && ($current = $current->next)); return –$this->size; } /* * 查询节点 * @param int $index 节点位置，从1开始计数 * @return Node|null * @throws Exception / public function searchNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(‘你查询的节点不存在’); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { return $current->next; } } while ($current->next != null && ($current = $current->next)); } /* * 获取节点长度 * @return int / public function getLength() { return $this->size; } /* * 遍历列表 */ public function showNode() { $current = $this->header; $index = 1; while ($current->next != null) { $current = $current->next; echo ‘index — ’ . $index++ . ’ — ‘; echo var_export($current->data); echo PHP_EOL; } }}示例$link = new SingleLinkList();$link->addNode(new Node(1));$link->addNode(new Node(2));$link->insertNodeByIndex(3, new Node(3));$link->addNode(new Node(4));$link->addNode(new Node(5));echo $link->getLength(), PHP_EOL;$link->showNode();echo ‘———–’, PHP_EOL;var_dump($link->searchNodeByIndex(3));echo ‘———–’, PHP_EOL;$link->deleteNodeByIndex(3);$link->showNode();