数据结构-php采用虚拟头节点实现单链表
1、链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
2、链表存储方法
链接方式存储的线性表简称为链表（Linked List）。
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
3、链表结构
/**
* 构建链表节点
*/
Class Node
{
public $e;
public $next;
public function __construct($e = null, $next = null)
{
$this->e = $e;
$this->next = $next;
}
}单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。
4、链表添加操作
/**
* 在链表头添加新的元素e
* @param $e
*/
public function addFirst($e)
{
$this->head = new Node($e, $this->head);
$this->size ++;
}
/**
* 在链表的index(0-based)位置添加新的元素e
* 在链表中不是一个常用的操作，练习用：
* @param $index
* @param $e
* @throws Exception
*/
public function add($index, $e){
if($index < 0 || $index > $this->size)
throw new Exception("Add failed. Illegal index.");
if($index == 0)
{
$this->addFirst($e);
} else {
$prev = $this->head;
for($i = 0 ; $i < $index - 1 ; $i ++)
{
$prev = $prev->next;
}
// $node = new Node($e);
// $node->next = $prev->next;
// $prev->next = $node;
$prev->next = new Node($e, $prev->next);
$this->size ++;
}
}这里我们可以看到，在添加的时候在链表头部插入与在链表指定索引位置插入，我们采用不同的插入方式，为了可以采用共同的方法，我们在下面引入虚拟头节点，$dummyHead，我们定义$dummyHead为存在与head之前的节点，这样head节点也可以当作普通节点来处理，就不需要再单独做处理。
4、php实现链表的常用操作
定义文件名为dummyLink.php
/**
* 构建链表节点
*/
Class Node
{
public $e;
public $next;
public function __construct($e = null, $next = null)
{
$this->e = $e;
$this->next = $next;
}
}
class LinkedList
{
public $dummyHead;
private $size;
public function __construct()
{
$this->dummyHead = new Node();
$this->size = 0;
}
/**
* 获取链表中的元素个数
* @return int
*/
public function getSize()
{
return $this->size;
}
/**
* 返回链表是否为空
* @return bool
*/
public function isEmpty()
{
return $this->size == 0;
}
/**
* 在链表的index(0-based)位置添加新的元素e
* 在链表中不是一个常用的操作，练习用：
* @param $index
* @param $e
* @throws Exception
*/
public function add($index, $e)
{
if ($index < 0 || $index > $this->size)
throw new \Exception("Add failed. Illegal index.");
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
$prev->next = new Node($e, $prev->next);
$this->size++;
}
/**
* 在链表头添加新的元素e
* @param $e
*/
public function addFirst($e)
{
$this->add(0, $e);
}
/**
* 在链表末尾添加新的元素e
* @param $e
* @throws Exception
*/
public function addLast($e)
{
$this->add($this->size, $e);
}
/**
* 获得链表的第index(0-based)个位置的元素
* @param $index
* @return mixed
* @throws Exception
*/
public function get($index)
{
if ($index < 0 || $index >= $this->size)
throw new \Exception("Get failed. Illegal index.");
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++)
$cur = $cur->next;
return $cur->e;
}
/**
* 获得链表的第一个元素
* @return mixed
* @throws Exception
*/
public function getFirst()
{
return $this->get(0);
}
/**
* 获得链表的最后一个元素
* @return mixed
* @throws Exception
*/
public function getLast()
{
return $this->get($this->size - 1);
}
/**
* 修改列表中某一个索引位置的值
* @param $index
* @param $e
* @throws Exception
*/
public function set($index, $e)
{
if ($index < 0 || $index >= $this->size)
throw new \Exception("Set failed. Illegal index.");
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++)
$cur = $cur->next;
$cur->e = $e;
}
/**
* 查找链表中是否有元素e
* @param $e
* @return bool
*/
public function contains($e)
{
$cur = $this->dummyHead->next;
while ($cur != null) {
if ($cur->e == $e) {
return true;
}
$cur = $cur->next;
}
return false;
}
/**
* 从链表中删除index(0-based)位置的元素, 返回删除的元素
* @param $index
* @return mixed
*/
public function remove($index){
if ($index < 0 || $index >= $this->size)
throw new \Exception("Remove failed. Index is illegal.");
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++)
$prev = $prev->next;
$retNode = $prev->next;
$prev->next = $retNode->next;
$retNode->next = null;
$this->size --;
return $retNode->e;
}
/**
* 从链表中删除第一个元素, 返回删除的元素
* @return mixed
*/
public function removeFirst(){
return $this->remove(0);
}
/**
* 从链表中删除最后一个元素, 返回删除的元素
* @return mixed
*/
public function removeLast(){
return $this->remove($this->size - 1);
}
/**
* 从链表中删除元素e
* @param $e
*/
public function removeElement($e){
$prev = $this->dummyHead;
while($prev->next != null){
if($prev->next->e == $e)
break;
$prev = $prev->next;
}
if($prev->next != null){
$delNode = $prev->next;
$prev->next = $delNode->next;
$delNode->next = null;
}
}
public function __toString()
{
$res = '';
for($cur = $this->dummyHead->next ; $cur != null ; $cur = $cur->next)
$res .= $cur->e."->";
$res.="NULL".PHP_EOL;
return $res;
}
}5、测试
$list = new LinkedList();
$arr = [3,6,4,9,8];
foreach ($arr as $v) {
$list->addLast($v);
}
$list->add(2,15); //指定位置插入
var_dump($list->dummyHead); //查看对象形式的链表结构
echo $list.PHP_EOL;
var_dump($list->get(2)); //获取索引2位置的结果
$list->removeLast(); //移除最后一个元素
echo $list; //查看最后结果测试结果：
6、链表的应用
在知乎上专门查询了一下链表的应用，找到两个比较好的整理如下
当数据量不大时（比如只有一万个数据），顺序表在所有方面的表现全都优于链表。就连在插入和删除时也是如此。因为链表插入新的结点要构造对象，这是非常耗时的；而在删除时，同于现代的计算机进行复制操作的效率极高，因为表现不比链表差。链表删除时还要执行析构操作，所以会慢不少。当顺序表长度大于一定的值时，插入和删除操作速度就会变得不如链表。链表的缺点主要在于按元素序号随机访问时效率低下。一些其它数据结构，比如图和树，在形式上也类似链表。（当然也有基于顺序表的实现）
相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList，不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。 我觉得在以下场景LinkedList比ArrayList有优势：1) 你的应用不会随机访问数据。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。2) 你的应用更多的插入和删除元素，更少的按索引读取数据（如果只是遍历，区别不大）。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。