链表的操作要比序列表（数组）复杂的多。因为PHP确实为我们解决了很多数组操作的问题，我们可以很方便的操作数组，不需要再为数组定义很多逻辑操作。比如在C中，数组是有长度限制的，但是在PHP中我们不考虑这个问题。如果你用的是C，这个长度限制是数组结构的一大缺点，而链表无论是C还是PHP，都不受长度限制的问题。唯一能限制链表的就是内存的大小。另外，链表的链式结构还可以给我们带来不同于数组操作的全新体验。对于一些函数式算法，链表也更有优势。话不多说，直接进入今天的内容吧！链式结构的定义首先，在第一篇关于线性表的文章中，我们已经提到了链表的定义。在这里，我们回顾一下之前关于链表的图表，以便更清楚地理解链表的概念。我们用类来表示图中的节点Node：/***链表结构*/classLinkedList{public$data;public$next;}一个链表类可以看作是链表中的一个节点，它包含两个内容，data表示数据，next表示下一个节点的指针。就像链子一样，一环就是一环。这就是传说中的链表结构。生成链表和初始化操作/***生成链表*/functioncreateLinkedList(){$list=newLinkedList();$列表->数据=空；$列表->下一个=空；return$list;}/***初始化链表*@paramarray$data链表中要保存的数据，这里以数组作为引用*@returnLinkedList链表数据*/functionInit(array$data){//初始化$list=createLinkedList();$r=$列表；foreach($dataas$key=>$value){$link=newLinkedList();$链接->数据=$值；$链接->下一个=空；$r->下一个=$链接；$r=$链接；}return$list;}$link=Init(range(1,10));print_r($link);//LinkedList对象//(//[data]=>//[next]=>LinkedList对象//(//[data]=>1//[next]=>LinkedList对象//(//[data]=>2//[next]=>LinkedList对象//(//[data]=>3//[下一步]=>链接dListObject//(//[data]=>4//[next]=>LinkedListObject//(//[data]=>5//[next]=>LinkedListObject//(//[data]=>6//[next]=>LinkedList对象//(//[data]=>7//[next]=>LinkedList对象//(//[data]=>8//[next]=>LinkedList对象//(//[data]=>9//[next]=>LinkedList对象//(//[data]=>10//[next]=>//)//)//)//)//)//)//)//)//)//)//)在使用链表时，我们通常让第一个节点不包含任何数据，就像一个空节点指向第一个有数据的节点即可称为头节点。如果需要判断链表是否为空，只需要判断第一个节点的next是否为空即可。在上面的代码中，创建链表的createLinkedList()函数其实就是生成了这样一个头节点。然后，我们通过Init()初始化函数构造这个链表。施工过程比较简单。这里固定传入一个数组，根据数组结构构造链表。当然，在实际应用中，我们可以使用任意数据来构造链表。构建过程并不复杂，只需将当前节点赋值给r变量，然后创建一个新节点，让r->next等于新创建的节点即可。构造链表直接打印出来的结构就是注释中的形式。遍历链表函数IteratorLinkedList(LinkedList$link){while(($link=$link->next)!=null){echo$link->data,',';}echoPHP_EOL;}链表的遍历很像某些数据库的Cursor操作，或者类似迭代器模式的操作。没错，游标和迭代器的结构其实就是链表的一种形式。一直寻找$next，直到没有下一个结点，这样就完成了一次链表的遍历。可以看出，这个过程的时间复杂度是O(n)。Insert,delete/***在链表指定位置插入元素*@paramLinkedList$list链表数据*@paramint$iposition*@parammixed$datadata*/functionInsert(LinkedList&$list,int$我,$数据){$j=0;$项目=$列表；//遍历链表，找到指定位置的上一个位置while($j<$i-1){$item=$item->next;$j++;}//如果item不存在或者$i>n+1or$i<0if($item==null||$j>$i-1){returnfalse;}//创建一个新节点$s=newLinkedList();$s->数据=$数据；//新建节点的下一个节点指向原i-1节点的下一跳节点，即当前i节点$s->next=$item->next;//将i-1节点的下一跳节点指向s，将s插入到指定的i位置，使原来的i位置元素变成i+1位置$item->next=$s;返回真；}/***删除链表指定位置的元素*@paramLinkedList$list链表数据*@paramint$iposition*/functionDelete(LinkedList&$list,int$i){$j=0;$item=$list;//遍历链表，找到指定位置的上一个位置while($j<$i-1){$item=$item->next;$j++;}//如果项目不存在或$i>n+1或$i<0if($item==null||$j>$i-1){返回假；}//使用临时节点保存当前节点信息，$item是第i-1个节点，所以$item->next就是我们要找的当前i节点$temp=$item->next;//使当前节点，也就是目标节点的前一个节点，i-1的这个节点的下一跳（原i位置节点）成为原i位置节点next节点的下一跳，让位置i的节点离开链$item->next=$temp->next;returntrue;}//InsertInsert($link,5,55);//遍历链表IteratorLinkedList($link);//1,2,3,4,55,5,6,7,8,9,10,//删除Delete($link,7);//遍历链表IteratorLinkedList($link);//1,2,3,4,55,5,7,8,9,10，链表的插入和删除其实很相似。它们都需要找到插入或删除位置的前一个元素，即第i-1个位置的元素，然后通过对该元素的next指针的操作，实现链表元素的插入和删除操作。它们在遍历和位置判断这两个函数中的代码其实是一样的。不同的是创建的时候会创建一个新节点，然后这个节点的next指向上一个i-1位置元素的next，然后i-1位置元素的next指向新创建的节点。删除操作是将这个位置i的待删除节点保存到一个临时变量中，然后将位置i-1的元素的下一个指向被删除的位置i的下一个。上面的解释需要结合代码一步步看。当然我们也可以结合下图进行学习。插入和删除操作是链表操作的核心，也是最复杂的部分，需要大量的理解和掌握。按位置搜索，按数据搜索/***按位置查找元素位置*@paramLinkedList$list链表数据*@paramint$iposition*/functionGetElem(LinkedList&$list,int$i){$item=$列表；$j=1;//从第一个开始查找，0为头节点while($item&&$j<=$i){$item=$item->next;$j++;}if(!$item||$j>$i+1){返回false;}return$item->data;}/***根据数据找到数据元素的位置*@paramLinkedList$list链表数据*@parammixed$dataData*/functionLocateElem(LinkedList&$list,$data){$item=$list;$j=1;//从第一个开始查找，0为头节点while(($item=$item->next)!=null){if($item->data==$data){return$j;}$j++;}returnfalse;}//获取指定位置的元素内容var_dump(GetElem($link,5));//int(55)//获取指定元素的位置var_dump(LocateElem($link,55));//查找int(5)链表有两种形式，一种是给一个位置，比如我要第5个位置的元素的内容，那么就是找元素的值根据指定的位置，就像数组的下标一样。但是需要注意的是，链表的下标是从1开始的，因为0的位置就是我们的头节点。当然，我们也可以修改代码忽略掉头节点，使其与数组保持一致，但是这种情况下，链表的特性并不明显，所以这里的测试代码还是从1开始.另一种搜索是给定一个数据内容，查找它在链表中的位置。其实这两种算法都是遍历整个链表，本质上没有区别。由于链表不像数组那样具有下标的能力，所以其查找操作的时间复杂度为O(n)。怎么总结，难度就上来了。链表的操作要复杂很多，不用担心，这只是开胃菜。后面学习的内容基本都会围绕序列表（数组）和链表这两种形式展开。而我们的链表学习还没有结束。在下一篇文章中，我们将对其他形式的链表有更深入的了解：双向链表、循环链表、双向循环链表。测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2。线性表/source/2.3%20链表相关逻辑运算.php参考资料：《数据结构》第二版，闫伟民《数据结构》第二版，陈越《数据结构高分笔记》2020年版，天琴考研各自媒体平台可以搜索[硬核心项目经理]
