数据结构之php实现单向链表

thinkabel 的个人博客 / 102 / 0 / 创建于 3年前 / 更新于 3年前

在前面的文章中, 我们一起学习了, 数组, 栈, 队列. 他们有共同的特点, 线性数据结构。我们实现他们，都是依托于（静态）数组, 靠resize来解决固定容量问题（在PHP中体现不出静态数组和动态数组的区别，放到java中，就能深有体会了），因为底层通过数组实现，在存储过程中都是有序的进行存储。今天我们一起学习的链表也是一种线性的数据结构，但是在存储的时候，是无序的。

我们带着几个问题往下进行学习

数组和链表它们之间相同点，不同点是什么？
有了数组为什么还要有链表？

一、概念

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

维基百科

通过定义我们能看到，链表是最常见的一种基础的，存储的是无序的一种线性数据结构。

(单向链表的示意图)

链表中最简单一种是单向链表, 或叫做单链表, 它包含两个域和一个指针域, 指针域用于指向下一个节点信息, 而最后一个节点则指向一个空值, 如图所示:

(链表域的示意图)

单向链表的节点通常由两个部分构成,一个是节点储存的值e, 另一个就是节点的指针next. 链表与数组类似, 也可以进行查找, 插入, 删除, 读取等操作, 但是由于链表与数组的特性不同, 导致不同操作的复杂度也不同。

二、操作流程图分析

在学习链表这一章节，有时候觉得会特别的绕，希望大家不要总是盯着代码，在脑子里面想。尽量使用图，图是最容理解的，也会很清晰的看到是怎么个流程。

** 1. 添加操作**

我们先来看下往 链表头部添加元素

（链表头部添加元素）

现在我们想往头部添加元素, 就需要把当前 node 的下一个节点指向当前 head , 插入进去后, 头部节点就变成了当前插入的 node. 我们维护一下链表长度, 代码即是:

 node.next = head

(插入成功后的示意图)

在链表头插入是最简单的, 只需要一次操作就可以插入成功。我们看下在链表任意位置插入，又是怎么操作的呢？

比如我们在“**索引”为2的地方添加元素 888 （在链表中没有索引的概念, 我们只是延伸一下数组的概念,方便我们进行手动定位位置*）, *第一步,我们需要创建出 888 这个节点, 然后需要找到索引为 2 的上一个节点, 然后把上一个节点的 next 赋值给当前插入节点的 next, 然后再把上一个节点的next 指向当前节点。**（这里的顺序一定不能反了，如果说先把上一个节点的next 指向当前节点, 再把上一个节点的next 赋值给当前插入节点的next, 大家仔细想一下, 是不是都指向当前的节点, 链表就断了）, 所以这里大家一定不要写反了。

我们来看下流程图是怎样的？

（创建节点和定义prev示意图）

这个时候，我们创建了一个 888节点 node，然后定义了上一个节点 prev , 这时候我们遍历循环链表到上一个节点。

（遍历节点到上一个节点示意图）

然后我们将上一个节点的 next 节点信息, 给当前节点的 next , 然后上节点的 next 指向当前节点,维护链表长度, 看图:

（链表交换示意图）

代码实现也就是:

node.next = prev.next

（插入成功示意图）

*现在我们思考一下, 如果插入在头部的话, 怎么办? *头部并没有上一个节点可以供我们使用, 所以我们这个时候, 有两种处理方法:

1、我们在插入首位的时候，做个特殊处理，利用上面插入首位的方法进行插入。

2、我们可以设立一个虚拟节点来实现，这样首位也是有前一个节点了。就想我们在学习循环队列时，有意的浪费掉一个空间，这个原理也是一样的。

第一种方式我就不进行画图了，我们直接看第二种设立虚拟头结点（dummyHead），先看下图：

（虚拟头结点示意图）

引入虚拟头节点

引入虚拟头节点dummyHead使得 LinkedList 成了只包含虚拟头节点的数据结构，在初始化 LinkedList 的时候，为dumyHead分配了空间（不像 head指针在初始化的时候没有分配空间，只是指向 null），此时 dumyHead中，dumyHead.e = null，dumyHead.next = null；
由于虚拟头节点的引入，使得向 LinkedList 的指定位置添加元素时，无需针对在队首插入元素的情况做特殊处理；
由于链表的插入需要找到插入节点的前驱节点，因此游标 prev 要停在插入位置的前一个位置；初始时，将 prev 指向 dumyHead，当 i = 0 时，prev 向右移动一格，prev 指向索引为 0 的节点，即第一个元素（dumyHead 是第一个节点的前驱节点），所以 i = index - 1 时，prev 也指向了 index - 1 ，即：插入位置的前一个位置，从而找到了插入节点的前驱节点；

** 2. 修改操作**

遍历循环链表, 头部节点应该是 dummyHead->next, 才是正式节点。通过传递的索引, 进行修改需要修改的元素, 这个比较简单，只是替换 node 节点中的元素信息.

** 3. 删除操作**

首先我们也是和添加操作一样, 需要找到要删除元素的前一个节点, 看下图:

(找到要删除的节点和上一个节点)

然后将前一个节点的 next 指向要删除节点的 next 节点,这个时候, 要删除的节点已经断开连接, 然后把要删除的next 节点指向 null, 等垃圾回收机制删除这个节点就好, 我们维护链表长度. 看下图:

(找到要删除的节点和上一个节点)

三、代码实现
LinkedList.php

<?php
/**
 * Created by : PhpStorm
 * User: think abel
 * Date: 2021/1/11 0011
 * Time: 22:12
 */

class LinkedList
{
    // 链表虚拟头结点
    private $dummyHead;

    // 链表的元素数
    private $size;

    /**
     * LinkedList constructor.
     */
    public function __construct()
    {
        $this->dummyHead = new Node(null, null);
        $this->size      = 0;

    }

    /**
     * Notes: 获取链表中的元素个数
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 22:28
     *
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;

    }

    /**
     * Notes: 链表是否为空
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 22:28
     *
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;

    }

    /**
     * Notes: 在链表的第 index 处 添加新的元素 e
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 22:45
     *
     * @param $index
     * @param $e
     *
     * @return string
     */
    public function add($index, $e)
    {
        try {
            if ($index < 0 || $index > $this->size) {
                throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * @var Node $prev 为虚拟头结点, 所以遍历 输入的 index 次 就是前一个节点
             */
            $prev = $this->dummyHead;
            for ($i = 0; $i < $index; $i ++) {
                $prev = $prev->next;
            }

            /**
             * 通过 当前传递的 数据 和 上一个节点所指向的下一个节点信息 来创建 当前 节点
             * 并把 上一个节点 所指向的下一个节点信息 变为当前创建的节点
             */
            $prev->next = new Node($e, $prev->next);
            $this->size ++;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 在链表头添加新的元素 e
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 22:34
     *
     * @param $e
     */
    public function addFirst($e)
    {
        $this->add(0, $e);

    }

    /**
     * Notes: 向链表末尾添加元素 e
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:23
     */
    public function addLast($e)
    {
        $this->add($this->size, $e);

    }

    /**
     * Notes: 获取第 index 位置的 元素
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:36
     *
     * @param int $index
     *
     * @return string
     */
    public function get(int $index)
    {
        try {
            if ($index < 0 || $index > $this->size) {
                throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * @var Node $cur 当前节点的下一个节点, 因为前面有一个虚拟节点
             */
            $cur = $this->dummyHead->next;
            for ($i = 0; $i < $index; $i ++) {
                $cur = $cur->next;
            }

            return $cur->e;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 获取第一个元素
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:40
     *
     * @return string
     */
    public function getFirst()
    {
        return $this->get(0);

    }

    /**
     * Notes: 获取最后一个元素
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:40
     *
     * @return string
     */
    public function getLast()
    {
        return $this->get($this->size - 1);

    }

    /**
     * Notes: 更新一个元素
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:44
     *
     * @param int $index
     * @param     $e
     *
     * @return string
     */
    public function set(int $index, $e)
    {
        try {
            if ($index < 0 || $index > $this->size) {
                throw new Exception("修改失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * @var Node $cur 当前节点的下一个节点, 因为前面有一个虚拟节点
             */
            $cur = $this->dummyHead->next;
            for ($i = 0; $i < $index; $i ++) {
                $cur = $cur->next;
            }

            $cur->e = $e;

        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 查找元素是否存在
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:49
     *
     * @param $e
     *
     * @return bool
     */
    public function contains($e): bool
    {
        /**
         * @var Node $cur
         */
        $cur = $this->dummyHead->next;

        /**
         * 不知道遍历多少次, 使用 while 循环
         * 如果 当前的元素 == $e 说明 存在, 返回true
         * 否则 将 当前的下一个元素 赋值给 当前元素 继续遍历
         * 如果 都没有, 说明不存在, 返回 false
         */
        while ($cur != null) {
            if ($cur->e == $e) {
                return true;
            }

            $cur = $cur->next;
        }

        return false;

    }

    /**
     * Notes: 删除 index 位置的元素
     * User: think abel
     * Date: 2021/1/12 0012
     * Time: 0:15
     *
     * @param int $index
     *
     * @return string|null
     */
    public function remove(int $index)
    {
        try {
            if ($index < 0 || $index > $this->size) {
                throw new Exception("删除失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * @var Node $prev 当前节点的下一个节点, 因为前面有一个虚拟节点
             */
            $prev = $this->dummyHead;
            for ($i = 0; $i < $index; $i ++) {
                $prev = $prev->next;
            }

            /**
             * @var Node $removeNode
             */
            $removeNode = $prev->next;
            $prev->next = $removeNode->next;

            $removeElement = $removeNode->e;
            $removeNode    = null;
            $this->size --;

            return $removeElement . PHP_EOL;


        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除第一个元素
     * User: think abel
     * Date: 2021/1/12 0012
     * Time: 0:16
     *
     * @return string|null
     */
    public function removeFirst()
    {
        return $this->remove(0);
    }

    /**
     * Notes: 删除最后一个元素
     * User: think abel
     * Date: 2021/1/12 0012
     * Time: 0:16
     *
     * @return string|null
     */
    public function removeLast()
    {
        return $this->remove($this->size - 1);
    }

    /**
     * Notes: 打印输出
     * User: think abel
     * Date: 2021/1/11 0011
     * Time: 23:52
     *
     * @return string
     */
    public function toString(): string
    {
        /**
         * @var Node $cur
         */
        $cur = $this->dummyHead->next;

        $str = '';
        for ($cur; $cur != null; $cur = $cur->next) {
            $str .= $cur->e . '-->';
        }

        $str .= 'NULL';
        return $str . PHP_EOL;

    }
}

/**
 * 创建节点类
 * Class Node
 */
class Node
{
    // 节点元素
    public $e;

    // 指向下一个节点信息
    public $next;

    /**
     * Node constructor.
     *
     * @param null $e
     * @param null $next
     */
    public function __construct($e = null, $next = null)
    {
        $this->e    = $e;
        $this->next = $next;

    }

}

index.php

<?php

include "LinkedList.php";
$linkedList = new LinkedList();
for ($i = 0; $i < 10; $i++) {
    $linkedList->addFirst($i);
    echo $linkedList->toString();
}

$linkedList->add(2, 666);
echo $linkedList->removeLast();
echo $linkedList->toString();

四、简单复杂度分析

O: 描述是算法的运行时间和输入数据之间的关系 — 程序运行时间和数数据成线性关系 O(n)

添加操作 O(N)

addLast           O(N)
addFirst          O(1)
add(index, e)     O(N/2) = O(N)

修改操作 O(N)
```
set(index, e)     O(N)
```

删除操作 O(N)

removeLast(e)     O(N)
removeFirst(e)    O(1)
remove(index, e)  O(N/2) = O(N)

查找操作 O(N)
```
get(index)     O(N)
contains(e)    O(N)
```
我们看到, 增删改的操作都是O(N), 但是想一下, 我们只对链表头进行操作的话, 复杂度就是O(1)

五、总结

链表的一些基础操作已经学习完了, 现在将文章开始的几个问题进行一下总结回答.
1、数组和链表它们之间相同点，不同点是什么？
—相同点：都是线性数据结构
—不同点：存储的顺序是不相同的，数组是有序的，链表是无序的。

2、有了数组为什么还要有链表？
链表和数组，他俩是各有千秋，毕竟什么都是双面性的。
数组的特点在于随机访问性强, 查找速度快。缺点在于插入和删除时效率低，可能会存在浪费内存的情况，内存要求高，必须要有足够的连续内存空间。
链表的特点在于插入删除效率高，内存利用率高，不会浪费内存，大小没有固定，容易拓展。但是链表在读取时效率慢。
所以他俩是进行互补的状态

最后祝大家工作开心，永不加班~ 加油……