下载文档原格式
数据结构与算法之PHP实现链表类（单链表双链表循环链表）链表是由⼀组节点组成的集合。
每个节点都使⽤⼀个对象的引⽤指向它的后继。
指向另⼀个节点的引⽤叫做链。
链表分为单链表、双链表、循环链表。
⼀、单链表插⼊：链表中插⼊⼀个节点的效率很⾼。
向链表中插⼊⼀个节点，需要修改它前⾯的节点(前驱)，使其指向新加⼊的节点，⽽新加⼊的节点则指向原来前驱指向的节点（见下图）。
由上图可知，B、C之间插⼊D，三者之间的关系为current为插⼊节点的前驱节点new->next = current->next // 新节点D指向B的后继节点Ccurrent->next = new // B节点指向新节点D删除：从链表中删除⼀个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）。
由上图可知，A、C之间删除B，三者之间的关系为current为要删除节点的前驱节点current->next = current->next->next // A节点指向C节点具体代码如下：<?php// 节点类class Node {public $data; // 节点数据public $next; // 下⼀节点public function __construct($data) {$this->data = $data;$this->next = NULL;}}// 单链表类class SingleLinkedList {private $header; // 头节点function __construct($data) {$this->header = new Node($data);}// 查找节点public function find($item) {$current = $this->header;while ($current->data != $item) {$current = $current->next;}return $current;}// （在节点后）插⼊新节点public function insert($item, $new) {$newNode = new Node($new);$current = $this->find($item);$newNode->next = $current->next;$current->next = $newNode;return true;}// 更新节点public function update($old, $new) {$current = $this->header;if ($current->next == null) {echo "链表为空！";}while ($current->next != null) {if ($current->data == $old) {break;}$current = $current->next;}return $current->data = $new;}// 查找待删除节点的前⼀个节点public function findPrevious($item) {$current = $this->header;while ($current->next != null && $current->next->data != $item) { $current = $current->next;}return $current;}// 从链表中删除⼀个节点public function delete($item) {$previous = $this->findPrevious($item);if ($previous->next != null) {$previous->next = $previous->next->next;}}// findPrevious和delete的整合public function remove($item) {$current = $this->header;while ($current->next != null && $current->next->data != $item) { $current = $current->next;}if ($current->next != null) {$current->next = $current->next->next;}}// 清空链表public function clear() {$this->header = null;}// 显⽰链表中的元素public function display() {$current = $this->header;if ($current->next == null) {echo "链表为空！";return;}while ($current->next != null) {echo $current->next->data . "  ";$current = $current->next;}}}$linkedList = new SingleLinkedList('header');$linkedList->insert('header', 'China');$linkedList->insert('China', 'USA');$linkedList->insert('USA','England');$linkedList->insert('England','Australia');echo '链表为：';$linkedList->display();echo "</br>";echo '-----删除节点USA-----';echo "</br>";$linkedList->delete('USA');echo '链表为：';$linkedList->display();echo '-----更新节点England为Japan-----';echo "</br>";$linkedList->update('England', 'Japan');echo '链表为：';$linkedList->display();//echo "</br>";//echo "-----清空链表-----";//echo "</br>";//$linkedList->clear();//$linkedList->display();// 输出：链表为：China USA England Australia-----删除节点USA-----链表为：China England Australia-----更新节点England为Japan-----链表为：China Japan Australia⼆、双链表单链表从链表的头节点遍历到尾节点很简单，但从后向前遍历就没那么简单了。
第8讲 双向链表● 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前趋结点，但时间耗费是O (n) 。
● 如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域prior 。
这样形成的链表中就有两条方向不同的链，我们称之为双向链表。
● 双向链表的结构定义如下：typedef struct DNode{ ElemType data ；struct DNode *prior ，*next ；}DNode, * DoubleList ；● 双向链表的结点结构如图所示。
图：双链表的结点结构注：● 双向链表也是由头指针唯一确定的，● 增加头结点能使双链表的某些运算变得方便● 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。
● 设指针p 指向双链表中某一结点，则有下式成立：p->prior->next = p = p->next->prior●在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，● 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。
1、 双向链表的前插操作【算法思想】欲在双向链表第i 个结点之前插入一个的新的结点，则指针的变化情况如图所示：… p …s->prior=p->prior; ①p->prior->next=s;②s->next=p; ③p->prior=s;④【算法描述】int DlinkIns(DoubleList L,int i,ElemType e){DNode *s,*p;… /*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/… /*若位置i合法，则找到第i个结点并让指针p指向它*/s=(DNode*)malloc(sizeof(DNode));if (s){ s->data=e;s->prior=p->prior; ①p->prior->next=s; ②s->next=p; ③p->prior=s; ④r eturn TRUE;}else return FALSE;}2、双向链表的删除操作【算法思想】欲删除双向链表中的第i个结点，则指针的变化情况如图所示：p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);【算法描述】int DlinkDel(DoubleList L,int i,ElemType *e){DNode *p;… /*先检查待插入的位置i 是否合法（实现方法同单链表的删除操作）*/… /*若位置i 合法，则找到第i 个结点并让指针p 指向它*/*e=p->data;p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);return TRUE;}3、 双向循环链表双向链表可以有循环表,称为双向循环链表。
循环链表是另一种形式的链式存储结构形式。
循环单链表：将表中尾节点的指针域改为指向表头节点，整个链表形成一个环。
由此从表中任一节点出发均可找到链表中其他节点。
循环双链表：形成两个环。
节点类型与非循环单链表的相同节点类型与非循环双链表的相同线性表(a 1, a 2, …, a i , … a n )映射逻辑结构存储结构a 1a 2a n…L带头节点循环单链表示意图1、循环单链表与非循环单链表相比，循环单链表：链表中没有空指针域p所指节点为尾节点的条件：p->next==LL pa1a2a n…【例2-8】某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素，故采用存储方式最节省运算时间。
A.单链表B.仅有头结点指针的循环单链表C.双链表D.仅有尾结点指针的循环单链表D.仅有尾结点指针的循环单链表a 1a2a n…L在尾元素之后插入一个元素删除第一个元素时间复杂度均为O(1)选择D线性表(a 1, a 2, … , a i , … a n )映射逻辑结构存储结构a 1a 2a n…L带头节点循环双链表示意图2、循环双链表与非循环双链表相比，循环双链表：链表中没有空指针域p所指节点为尾节点的条件：p->next==L一步操作即L->prior可以找到尾节点p La1a2a n…【例2-9】如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用。
A.只有尾结点指针没有头结点的循环单链表B.只有尾结点指针没有头结点的非循环双链表C.只有首结点指针没有尾结点指针的循环双链表D.既有头指针也有尾指针的循环单链表a 1a 2a n…LC.只有首结点指针没有尾结点指针的循环双链表删除第一个元素删除尾元素在第一个元素前面插入新元素在尾元素的后面插入新元素时间复杂度均为O(1)选择C【例2-10】设计判断带头节点的循环双链表L（含两个以上的节点）是否对称相等的算法。
双循环链表传统实现在传统的双循环链表实现中，如果创建某种数据结构的双循环链表，通常采用的办法是在这个数据结构的类型定义中加入两个（指向该类型对象的）指针next和prev。
例如：typedef struct foo {…struct foo *prev;struct foo *next;…} foo_t;这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。
Linux内核中双循环链表实现在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。
若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等操作函数。
（由于用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。
）在Linux源代码树的include/linux/list.h文件中，采用了一种（数据结构）类型无关的双循环链表实现方式。
其思想是将指针prev和next从具体的数据结构中提取处理构成一种通用的"双链表"数据结构list_head，而list_head被作为一个成员嵌入到要拉链的数据结构（被称为宿主数据结构）中。
这样，只需要一套通用的链表操作函数就可以将list_head成员作为"连接件"，把宿主数据结构链接起来。
如下图所示：在Linux内核中的双循环链表实现方式下：1. 链表结构作为一个成员嵌入到宿主数据结构内；2. 可以将链表结构放在宿主结构内的任何地方；3. 可以为链表结构取任何名字；4. 宿主结构可以有多个链表结构。
下面我们将基于Linux 2.4.21分析Linux内核双循环链表的实现及应用。
声明和初始化链表结构定义如下：struct list_head {struct list_head *next, *prev;};我们可以用struct list_head声明一个链表节点。
C++中链表例子(有详细的注释)学c++的时候大家一定会对链表很难弄明白所以就给大家一个例子重点的说明了链表的用法还加了很详细的注释例子:#include <iostream>using namespace std;struct Node //很多同学对这个名字很模糊，节点的英文就是Node{ //不一定非要用Node的。
int data; //节点中的数据结构体Node的成员变量Node* next; //指向下一节点的指针，习惯用next命名结构体Node的成员变量Node( const int& d=int() ) //结构体也可以有构造函数,d=T()来指定默认值:data(d),next(NULL) //用构造函数来初始化成员变量data和指针{} //所有数据类型，默认初始化都为0，这里data默认初始化为0};//老师是把Node作为封装类的内包结构体，这里我给分开写一下class Chain //封装链表{private: //数据成员通常都是private的Node* head; //首先，我们要一个Node型的指针来保存链表的第一个节点；int length; //再用一个整型变量来记录当前链表内的节点数public:Chain() //在构造函数里建立一个空链表，即head指向NULL:head(NULL),length(0){} //节点数为0;//这里小小插句嘴：当我们在类中定义函数时（不是声明），相当于在前面加上一个inline 修饰void delall() //见名知意，这个函数用来删除链表中的所有节点{Node* pdel; //定义一个Node型指针用来保存要删除的节点while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点{pdel = head; //这里备份head的当前指向节点head = head->next; //把head的指向改变为下一节点delete pdel; //把head的原指向给删除掉} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候//head就被赋值为NULL，不满足循环条件，退出循环length = 0; //把节点数归零}~Chain(){ delall(); } //在析构函数中调用delall函数，来完成对象销毁时清理工作//这样一个链表必须具备的功能就实现了。
数据结构中的双向链表实现和应用场景双向链表是一种常用的数据结构，它在许多实际应用中都发挥着重要的作用。
本文将介绍双向链表的实现原理以及一些常见的应用场景。
一、双向链表的实现原理双向链表由一系列节点组成，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。
相比于单向链表，双向链表可以实现双向遍历，提高了一些操作的效率。
1.1 节点定义双向链表的节点通常由数据域和两个指针域组成，例如：```struct Node {int data; // 节点数据Node* prev; // 前一个节点指针Node* next; // 后一个节点指针};```1.2 插入操作在双向链表中插入一个节点可以分为两种情况：在表头插入和在表尾插入。
在表头插入时，只需修改原来头节点的prev指针为新节点的地址，并将新节点的next指针指向原头节点即可。
在表尾插入时，需要先找到原来的尾节点，然后将尾节点的next指针指向新节点的地址，并将新节点的prev指针指向尾节点的地址。
1.3 删除操作删除操作与插入操作类似，同样分为在表头和表尾删除节点。
在表头删除时，只需将头节点的next指针指向新的头节点，同时将新头节点的prev指针置为空。
在表尾删除时，需要先找到尾节点的前一个节点，然后将该节点的next指针置为空。
1.4 查找操作双向链表支持从前向后和从后向前两种遍历方式。
从前向后遍历时，我们可以利用节点的next指针不断向后遍历得到所有节点。
同样，从后向前遍历时，可以利用节点的prev指针不断向前遍历得到所有节点。
二、双向链表的应用场景双向链表广泛应用于各种软件和系统中，下面列举了一些常见的应用场景。
2.1 浏览器的历史记录在浏览器中，经常需要记录用户浏览过的网页历史记录。
这时可以使用双向链表来实现。
每当用户访问一个新的网页，就在双向链表中插入一个新节点，同时将新节点的next指针指向前一个节点，prev指针指向后一个节点。
PHP SPL标准库里实现了几种简单的线性表和树型结构，其中包括了双链表和双链表实现的队列和栈、最大堆、最小堆和优先队列。
双链表是一种重要的线性存储结构，对于双链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。
双链表对PHP开发程序来讲是很重要的一种数据结构，可以把PHP数组中想想成一个双链表，而PHP内置的SplDoublyLinkedList类通过实现迭代器、数组访问和获取数量的接口使程序访问对象变得访问数组一样方便。
SplDoublyLinkedList类代码如下：<?php/*** PS：关于预定义接口Iterator, ArrayAccess, Countable的文章已经介绍过了，不认识的可以往前翻翻* @link /wuxing26jiayou/article/details/51862707*/class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable{/*** @var _llist 定义一个数组用于存放数据*/protected $_llist = array();/*** @var _it_mode 链表的迭代模式*/protected $_it_mode = 0;/*** @var _it_pos 链表指针*/protected $_it_pos = 0;/*** 迭代模式* @see setIteratorMode*/const IT_MODE_LIFO = 0x00000002;const IT_MODE_FIFO = 0x00000000;const IT_MODE_KEEP = 0x00000000;const IT_MODE_DELETE = 0x00000001;/*** @return 返回被移出尾部节点元素* @throw RuntimeException 如果链表为空则抛出异常*/public function pop(){if (count($this->_llist) == 0) {throw new RuntimeException("Can't pop from an empty datastructure");}return array_pop($this->_llist);}/*** @return 返回被移出头部节点元素* @throw RuntimeException 如果链表为空则抛出异常*/public function shift(){if (count($this->_llist) == 0) {throw new RuntimeException("Can't shift from an empty datastructure");}return array_shift($this->_llist);}/*** 往链表尾部添加一个节点元素* @param $data 要添加的节点元素*/public function push($data){array_push($this->_llist, $data);return true;}/*** 往链表头部添加一个节点元素* @param $data 要添加的节点元素*/public function unshift($data){array_unshift($this->_llist, $data);return true;}/*** @return 返回尾部节点元素，并把指针指向尾部节点元素*/public function top(){return end($this->_llist);}/*** @return 返回头部节点元素，并把指针指向头部节点元素*/public function bottom(){return reset($this->_llist);}/*** @return 返回链表节点数*/public function count(){return count($this->_llist);}/*** @return 判断链表是否为空*/public function isEmpty(){return ($this->count() == 0);}/*** 设置迭代模式* - 迭代的顺序(先进先出、后进先出)* - SplDoublyLnkedList::IT_MODE_LIFO (堆栈)* - SplDoublyLnkedList::IT_MODE_FIFO (队列)** - 迭代过程中迭代器的行为* - SplDoublyLnkedList::IT_MODE_DELETE (删除已迭代的节点元素)* - SplDoublyLnkedList::IT_MODE_KEEP (保留已迭代的节点元素)** 默认的模式是0 : SplDoublyLnkedList::IT_MODE_FIFO | SplDoublyLnkedList::IT_MODE_KEEP** @param $mode 新的迭代模式*/public function setIteratorMode($mode){$this->_it_mode = $mode;}/*** @return 返回当前的迭代模式* @see setIteratorMode*/public function getIteratorMode(){return $this->_it_mode;}/*** 重置节点指针*/public function rewind(){if ($this->_it_mode & self::IT_MODE_LIFO) {$this->_it_pos = count($this->_llist)-1;} else {$this->_it_pos = 0;}}/*** @return 判断指针对应的节点元素是否存在*/public function valid(){return array_key_exists($this->_it_pos, $this->_llist); }/*** @return 返回当前指针的偏移位置*/public function key(){return $this->_it_pos;}/*** @return 返回当前指针对应的节点元素*/public function current(){return $this->_llist[$this->_it_pos];}/*** 将指针向前移动一个偏移位置*/public function next(){if ($this->_it_mode & self::IT_MODE_LIFO) {if ($this->_it_mode & self::IT_MODE_DELETE) {$this->pop();}$this->_it_pos--;} else {if ($this->_it_mode & self::IT_MODE_DELETE) {$this->shift();} else {$this->_it_pos++;}}}/*** @return 偏移位置是否存在** @param $offset 偏移位置* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常*/public function offsetExists($offset){if (!is_numeric($offset)) {throw new OutOfRangeException("Offset invalid or out of range");} else {return array_key_exists($offset, $this->_llist);}}/*** @return 获取偏移位置对应的值** @param $offset 偏移位置* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常*/public function offsetGet($offset){if ($this->_it_mode & self::IT_MODE_LIFO) {$realOffset = count($this->_llist)-$offset;} else {$realOffset = $offset;}if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) { throw new OutOfRangeException("Offset invalid or out of range");} else {return $this->_llist[$realOffset];}}/*** @return 设置偏移位置对应的值** @param $offset 偏移位置* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常*/public function offsetSet($offset, $value){if ($offset === null) {return $this->push($value);}if ($this->_it_mode & self::IT_MODE_LIFO) {$realOffset = count($this->_llist)-$offset;} else {$realOffset = $offset;}if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) { throw new OutOfRangeException("Offset invalid or out of range");} else {$this->_llist[$realOffset] = $value;}}/*** @return 删除偏移位置对应的值** @param $offset 偏移位置* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常*/public function offsetUnset($offset){if ($this->_it_mode & self::IT_MODE_LIFO) {$realOffset = count($this->_llist)-$offset;} else {$realOffset = $offset;}if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) { throw new OutOfRangeException("Offset invalid or out of range");} else {array_splice($this->_llist, $realOffset, 1);}}}?>。
数据结构之链表篇（单链表，循环链表，双向链表）C语⾔版1.链表 链表是线性表的⼀种，由⼀系列节点（结点）组成，每个节点包含⼀个数据域和⼀个指向下⼀个节点的指针域。
链表结构可以克服数组需要预先知道数据⼤⼩的缺点，⽽且插⼊和删除元素很⽅便，但是失去数组随机读取的优点。
链表有很多种不同类型：单向链表，双向链表和循环链表。
在链表中第⼀个节点叫头节点(如果有头节点）头节点不存放有效信息，是为了⽅便链表的删除和插⼊操作，第⼀个有效节点叫⾸节点，最后⼀个节点叫尾节点。
2.单链表的操作 链表的操作⼀般有创建链表，插⼊节点，删除节点，遍历链表。
插⼊节点的⽅法有头插法和尾插法，头插法是在头部插⼊，尾插法是在尾部插⼊。
下⾯以⼀个带头节点，采⽤尾插法的链表说明链表的各种操作。
1 #include<stdio.h>2 #include<stdlib.h>3//单链表456//节点结构体7 typedef struct node8 {9int value;//数据域10struct node*next;//指针域11 }Node;1213 Node*createList();//创建链表并且返回头节点指针14void deleteNode(Node*head);//删除节点15void insertNode(Node*head);//插⼊节点16void travelList(Node*head);//遍历链表1718int main()19 {20 Node*head=createList();21 travelList(head);22 insertNode(head);23 travelList(head);24 deleteNode(head);25 travelList(head);26return0;27 }28//创建链表，返回头节点指针29 Node*createList()30 {31//采⽤尾插法32 Node*head;//头节点33 Node*tail;//尾节点34 Node*temp=NULL;35int i,value,size;36 head=(Node*)malloc(sizeof(Node));//头节点37 head->value=0;38 head->next=NULL;39 tail=head;40 printf("输⼊节点个数: ");41 scanf("%d",&size);42 printf("输⼊各个节点的值: ");4344for(i=0;i<size;i++)45 {46 scanf("%d",&value);47 temp=(Node*)malloc(sizeof(Node));48 temp->value=value;49 tail->next=temp;//让尾节点的指针域指向新创建的节点50 tail=temp;//尾节点改为新创建的节点51 tail->next=NULL;//让尾节点的指针域为空52 }53return head;54 }55//遍历链表56void travelList(Node*head)57 {58while(head->next!=NULL)59 {60 printf("%d\n",head->next->value);61 head=head->next;62 }63 }64//插⼊节点65void insertNode(Node*head)66 {67int value;68int position;69int pos=0;70 Node*pre=NULL;//⽤来保存要插⼊节点的前⼀个节点71 Node*newNode;72 printf("输⼊要插⼊节点的值: ");73 scanf("%d",&value);74 printf("要插⼊的位置: ");75 scanf("%d",&position);76while(head!=NULL)77 {78 pos++;79 pre=head;80 head=head->next;81if(pos==position)82 {83 newNode=(Node*)malloc(sizeof(Node));84 newNode->value=value;85 newNode->next=pre->next;86 pre->next=newNode;87 }88 }89 }90//删除节点91void deleteNode(Node*head)92 {93int value;94 Node*pre=head;95 Node*current=head->next;96 printf("输⼊要删除节点的值: ");97 scanf("%d",&value);98while(current!=NULL)99 {100if(current->value==value)101 {102 pre->next=current->next;103free(current);//释放空间104break;105 }106 pre=current;107 current=current->next;108 }109 }3.循环链表 循环链表就是让尾节点的指针域不再是NULL,⽽是指向头节点从⽽形成⼀个环。
