醉丶春风的Blog

什么是链表？

链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将碎片内存进行合理的利用，解决空间的问题。

双向链表

双向链表， 顾名思义， 每个节点都有指向下一个节点地址和上一个节点地址的链表
如下图：

带有使用尾部哨兵, 可以简化插入倒序排列等操作

php代码实现

先定义一个节点元素类

节点元素有三个属性

• prev: 指向上个元素的地址
• data: 保存节点数据
• next: 指向下个元素的地址

/**
 * Class Node
 * 链表元素
 */
class Node {
    /**
     * 存储链表元素数据
     * @var string Node data
     */
    public $data = '';

    /**
     * 指向下一个元素的地址
     * @var self next Node
     */
    public $next = null;

    /**
     * 指向上一个元素的地址
     * @var self prev Node
     */
    public $prev = null;

    /**
     * 构造方法, 自动插入数据
     * @param $data
     * @param $prev
     * @param $next
     */
    public function __construct($data, $prev = null, $next = null)
    {
        $this->data = $data;
        $this->prev = $prev;
        $this->next = $next;
    }
}

双向链表类

/**
 * Class DoublyLinkedList
 * 双向链表
 */
class DoublyLinkedList {

    public $head; // next 指向链表头部

    public $tail; // prev 指向链表尾部

    public $length;

    public function __construct()
    {
        $this->head = new Node(null);
        $this->tail = new Node(null, $this->head);
        $this->head->next = $this->tail;
    }

    /**
     * 插入数据
     * @param $data
     * @return $this
     */
    public function insert($data)
    {
        // 创建一个node, prev = tail->prev, next = tail
        $node = new Node($data, $this->tail->prev, $this->tail);
        $this->tail->prev->next = $node;
        $this->tail->prev = $node;
        $this->length ++;
        return $this;
    }

    public function print()
    {
        $current = $this->head->next;
        echo '<hr>';
        while ($current !== null) {
            print_r($current->data);
            echo '<br>';

            $current = $current->next;
        }
    }

    /**
     * 删除元素
     * @param $index
     * @return bool
     */
    public function delete($index)
    {
        if ($index < 0) {
            $index = $this->length + $index;
        }
        if ($index >= $this->length) {
            return false;
        }

        $current = $this->head;
        $i = 0;
        // 找到index对应的元素的上一个
        while ($i != $index) {
            $current = $current->next;
            $i ++;
        }
        $current->next = $current->next->next;
        $current->next->prev = $current;
        $this->length--;

        return true;
    }
}