什么是单向链表链表是一种链式存储数据的结构，不需要连续的存储空间。链表中的数据用节点表示，每个节点由元素（存储数据）和指针（指向后继节点）组成。单向链表（也叫单向链表）是最简单的链表形式，每个节点只包含一个元素和一个指针。它有一个头部，除了最后一个节点之外的所有节点都有它们的后继节点。其存储结构如下图代码实现定义nodeclassNode{public$data;/***@varnull|节点*/public$next;公共函数__construct($data){$this->data=$data;$this->next=null;}}单链表的实现/***ClassSingleLinkList*单链表的实现实例，实现简单的增、插入、删除、查询、长度、遍历这些简单的操作*/classSingleLinkList{/***的头节点链表，头节点必须存在，*@varNode*/public$header;私人$大小=0;/***构造函数，默认添加一个sentinel节点，节点元素为Empty*SingleLinkList构造函数。*/publicfunction__construct(){$this->header=newNode(null);}/***在链表末尾添加一个节点*@paramNode$node*@returnint*/publicfunctionaddNode(Node$node){$current=$this->header;while($current->next!=null){$current=$current->next;}$current->next=$node;返回++$这个->大小；}/***在指定位置插入一个节点*@paramint$index节点位置，从1开始计数*@paramNode$node*@returnint*@throwsException*/publicfunctioninsertNodeByIndex($index,Node$node){if($index<1||$index>($this->size+1)){抛出新异常(sprintf('你要插入的位置超过链表长度%d',$this->size));$current=$this->header;$tempIndex=1;做{if($index==$tempIndex++){$node->next=$current->next;$current->next=$node;休息;while($current->next!=null&&($current=$current->next));返回++$this->size；}/***删除节点*@paramint$index节点位置，从1开始计数*@returnint*@throwsException*/publicfunctiondeleteNodeByIndex($index){if($index<1||$index>($this->size+1)){thrownewException('你删除的节点不存在');$current=$this->header;$tempIndex=1;做{if($index==$tempIndex++){$current->next=$current->next->next;休息;}}while($current->next!=null&&($current=$current->next));返回--$this->大小；}/***查询节点*@paramint$index节点位置，从1开始计数*@returnNode|null*@throwsException*/publicfunctionsearchNodeByIndex($index){if($index<1||$index>($this->size+1)){thrownewException('你查询的节点不存在');$current=$this->header;$临时索引=1;做{if($index==$tempIndex++){return$current->next;while($current->next!=null&&($current=$current->next));}/***获取节点长度*@returnint*/publicfunctiongetLength(){return$this->size;}/***遍历列表*/publicfunctionshowNode(){$current=$this->header;$索引=1；while($current->next!=null){$current=$current->next;回声“索引---”。$索引++。'---';echovar_export($current->data);echoPHP_EOL;$link=newSingleLinkList();$link->addNode(newNode(1));$link->addNode(newNode(2));$link->insertNodeByIndex(3,newNode(3)));$link->addNode(新节点(4));$link->addNode(新节点(5));echo$link->getLength(),PHP_EOL;$link->showNode();echo'----------',PHP_EOL;var_dump($link->searchNodeByIndex(3));echo'----------',PHP_EOL;$link->deleteNodeByIndex(3);$link->showNode();
