1。链表链表是物理存储单元上的一种非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中指针的链接顺序来实现的。链表由一系列节点组成（链表中的每个元素称为一个节点），节点可以在运行时动态生成。每个节点由两部分组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。与线性列表顺序结构相比，操作更加复杂。由于不必按顺序存储，所以链表在插入时可以达到O(1)的复杂度，比另一种线性列表序列表快很多，但查找节点或访问需要O(n)一个特定编号的节点时间，对应的线性表和顺序表的时间复杂度分别为O(logn)和O(1)。使用链表结构可以克服数组链表需要事先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了随机读取数组的优势，同时链表由于增加了节点的指针字段，空间开销也比较大。链表最明显的优点是常规数组排列关联项的方式可能与这些数据项在内存或磁盘中的顺序不同，数据的访问往往需要以不同的排列顺序进行转换.链表允许在列表的任意位置插入和删除节点，但不允许随机访问。有许多不同类型的链表：单链表、双向链表和循环链表。2.链表存储方式以链表方式存储的线性表简称链表。链表的具体存储表示为：①用一组任意的存储单元存储线性表的节点（这组存储单元可以是连续的，也可以是不连续的）②节点的逻辑顺序和物理顺序链表的顺序不一定相同。为了正确表示节点之间的逻辑关系，在存储每个节点的值的同时，还需要存储指示其后继节点（称为指针（pointer）或链（link））的地址（或位置）信息chain格式存储是最常用的存储方法之一。它不仅可以用来表示线性表，还可以用来表示各种非线性数据结构。3.链表结构/***构建链表节点*/ClassNode{public$e;公共$下一个；公共函数__construct($e=null,$next=null){$this->e=$e;$this->next=$next;}}单向链表中每个节点的存储地址都存储在其前驱节点的next字段中，起始节点没有前驱，所以要设置头指针head指向起始节点。链表由头指针唯一确定，单向链表可以通过头指针的名字来命名。终端节点没有后继，所以终端节点的指针字段为空，即NULL。4.链表添加操作/***在链表头部添加一个新元素e*@param$e*/publicfunctionaddFirst($e){$this->head=newNode($e,$这个->头）；$this->大小++；}/***在链表的索引（从0开始）位置添加一个新元素e*不是链表中的常用操作，用于练习：*@param$index*@param$e*@throwsException*/publicfunctionadd($index,$e){if($index<0||$index>$this->size)thrownewException("添加失败。非法索引。");如果($index==0){$this->addFirst($e);}else{$prev=$this->head;for($i=0;$i<$index-1;$i++){$prev=$prev->next;}//$node=newNode($e);//$node->next=$prev->next;//$prev->next=$node;$prev->next=newNode($e,$prev->next);$this->大小++；这里我们可以看到，在添加的时候，insertatthelinkedlistheadandinsertatthespecifiedindexpositionofthelinkedlist,我们采取了不同的插入way，为了采用通用的方法，下面引入虚拟头节点$dummyHead，我们将$dummyHead定义为head之前存在的节点，这样head节点也可以当作一个普通节点，并且有不需要单独处理4、php实现链表的常用操作定义文件名为dummyLink.php/***构建链表节点*/ClassNode{public$e;公共$下一个；公共函数__construct($e=null,$next=null){$this->e=$e;$this->next=$next;}}类LinkedList{public$dummyHead;私人$大小；公共函数__construct(){$this->dummyHead=newNode();$这个->大小=0;}/***获取链表中的元素个数*@returnint*/publicfunctiongetSize(){return$this->size;}/***返回链表是否为空*@returnbool*/publicfunctionisEmpty(){return$this->size==0;}/***在链表的index（从0开始）位置添加一个新元素e*不是链表中常用的操作，练习用：*@param$index*@param$e*@抛出异常*/publicfunctionadd($index,$e){if($index<0||$index>$this->size)thrownew\Exception("添加失败。非法索引。");$prev=$this->dummyHead;对于($i=0;$i<$index;$i++){$prev=$prev->next;}$prev->next=newNode($e,$prev->next);$this->大小++；}/***在链表头部添加一个新元素e*@param$e*/publicfunctionaddFirst($e){$this->add(0,$e);}/***在链表的末尾添加一个新元素e*@param$e*@throwsException*/publicfunctionaddLast($e){$this->add($this->size,$e);}/***获取链表（从0开始）元素在位置的索引*@param$index*@returnmixed*@throwsException*/publicfunctionget($index){if($index<0||$index>=$this->size)thrownew\Exception("获取失败。非法索引。");$cur=$this->dummyHead->next;对于($i=0;$i<$index;$i++)$cur=$cur->next;返回$cur->e;}/***获取链表的第一个元素*@returnmixed*@throwsException*/publicfunctiongetFirst(){return$this->get(0);}/***获取链表的最后一个元素*@returnmixed*@throwsException*/publicfunctiongetLast(){return$this->get($this->size-1);}/***修改列表中某个索引位置的值*@param$index*@param$e*@throwsException*/publicfunctionset($index,$e){if($index<0||$index>=$this->size)thrownew\Exception("设置失败。非法索引。");$cur=$this->dummyHead->下一步；对于($i=0;$i<$index;$i++)$cur=$cur->next;$cur->e=$e;}/***查找链表中是否有元素e*@param$e*@returnbool*/publicfunctioncontains($e){$cur=$this->dummyHead->next;while($cur!=null){if($cur->e==$e){返回真；}$cur=$cur->下一个；}返回假；}/***从链表中删除index(0-based)处的元素，返回删除的元素*@param$index*@returnmixed*/publicfunctionremove($index){if($index<0||$index>=$this->size)thrownew\Exception("删除失败。索引是非法的。");$prev=$this->dummyHead;对于($i=0;$i<$index;$i++)$prev=$prev->next;$retNode=$prev->下一步;$prev->next=$retNode->next;$retNode->next=null;$this->大小--;返回$retNode->e;}/***删除链表第一个元素，返回删除的元素*@returnmixed*/publicfunctionremoveFirst(){return$this->remove(0);}/***从链表中删除最后一个元素，返回删除的元素*@returnmixed*/publicfunctionremoveLast(){return$this->remove($this->size-1);}/***从链表中移除元素e*@param$e*/publicfunctionremoveElement($e){$prev=$this->dummyHead;while($prev->next!=null){if($prev->next->e==$e)中断；$prev=$prev->下一个；}if($prev->next!=null){$delNode=$prev->next;$prev->next=$delNode->next;$delNode->next=null;}}公共函数__toString(){$res='';for($cur=$this->dummyHead->next;$cur!=null;$cur=$cur->next)$res.=$cur->e."->";$res.="NULL".PHP_EOL;返回$res;}}5。测试$list=newLinkedList();$arr=[3,6,4,9,8];foreach($arras$v){$list->addLast($v);}$列表->添加（2,15）；//插入var_dump($list->dummyHead);//以对象形式查看链表结构echo$list.PHP_EOL;var_dump($list->get(2));//获取索引2位置的结果$list->removeLast();//移除最后一个An元素echo$list;//查看最终结果测试结果：6.链表的应用我专门在知乎上查询了链表的应用，发现两种比较好的安排如下当数据量不大时（比如只有10000条数据），时序表在各个方面都优于链表，甚至包括插入和删除。因为链表插入一个新节点构造一个对象，非常耗时；而在删除的时候，用现代计算机进行复制操作效率极高，因为性能不比链表差。删除链表的时候，还要进行destruct操作，所以会慢很多。当顺序表的长度大于某个值时，插入和删除操作的速度会变得比链表慢。链表的主要缺点是按元素编号随机访问效率低下。其他一些数据结构，例如图和树，在形式上也类似于链表。（当然也有基于顺序表的实现）LinkedList相比ArrayList插入速度更快。因为LinkedList不像ArrayList，它不需要在数组满的时候重新加载所有的数据到一个新的数组中。这是ArrayList最坏的情况，时间复杂度为O(n)，而LinkedList插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据的时候也需要更新索引（除了插入数组的尾部）。我认为LinkedList在以下场景中优于ArrayList：1）您的应用程序不会随机访问数据。因为如果需要LinkedList中的第n个元素，需要从第一个元素开始依次统计到第n个数据，然后读取数据。2）你的应用插入删除元素多，按索引读取数据少（如果只是遍历，区别不大）。因为插入和删除元素不涉及重新排列数据，所以比ArrayList更快。参考：百度百科-链表百度百科-SingleLinkedList（链表）这种数据结构的实际应用有哪些？
