醉丶春风的Blog

单链表

单链表顾名思义就是一个链式数据结构，它有一个表头(Head)，本身不存储数据, 只是用来指向第一个节点的指针, 每个节点有两个元素, 一个为data, 用来存储数据, 一个为next, 用来存储下一个节点的地址, 最后一个节点的next指向null, 如下图:

php实现

用php实现单外链表, 首先我们要定义一个节点类, 用来保存链表节点
再定义一个链表类, 操作节点元素, 代码如下:

节点类

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

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

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

链表类

该链表实现了添加,删除,更新,头部插入,获取元素, 清空链表, 返回链表元素等等方法, 请自行查看代码

/**
 * Class SingleLinkedList
 * 单链表
 */
class SingleLinkedList {
    /**
     * 头指针, 指向第一个元素, 本身变不存储数据
     * @var Node head->next = First Node
     */
    public $head;

    /**
     * 链表长度
     * @var int Linked list Length
     */
    public $length = 0;

    /**
     * 构造方法, 用来插入头指针
     * SingleLinkedList constructor.
     */
    public function __construct()
    {
        $this->head = new Node(null);
    }

    /**
     * 插入数据, 返回$this可链式调用
     * @param $data
     * @return $this
     */
    public function insert($data)
    {
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = new Node($data);
        $this->length ++;
        return $this;
    }

    /**
     * 插入数据
     * @param $data
     * @return SingleLinkedList
     * @see insert
     */
    public function push($data)
    {
        return $this->insert($data);
    }

    /**
     * 从头部插入数据
     * @param $data
     * @return $this
     */
    public function headInsert($data)
    {
        $this->head->next = new Node($data, $this->head->next);
        $this->length ++;
        return $this;
    }

    /**
     * 更新元素
     * @param $index
     * @param $newData
     * @return $this|bool
     */
    public function update($index, $newData)
    {
        if ($this->length === 0 || $index > $this->length) {
            return false;
        }
        $i = 0;
        $current = $this->head->next;
        while ($i != $index) {
            $current = $current->next;
            $i ++;
        }
        $current->data = $newData;
        return $this;
    }

    /**
     * 弹出第一个元素
     * @return bool|string
     */
    public function pop()
    {
        if ($this->length === 0) {
            return false;
        }
        $data = $this->head->next->data;
        $this->head->next = $this->head->next->next;
        $this->length --;
        return $data;
    }

    /**
     * 获取指定元素
     * @param $index
     * @return bool|string
     */
    public function get($index)
    {
        if ($this->length === 0 || $index > $this->length) {
            return false;
        }
        $i = 0;
        $current = $this->head->next;
        while ($i != $index) {
            $current = $current->next;
            $i ++;
        }
        return $current->data;
    }

    /**
     * 删除指定元素
     * @param $index
     * @return bool
     */
    public function delete($index)
    {
        if ($index < 0) {
            $index = $this->length + $index;
        }
        if ($this->length === 0 || $index > $this->length) {
            return false;
        }
        $current = $this->head;
        $i = 0;
        while ($i < $index) {
            $current = $current->next;
            $i ++;
        }
        $current->next = $current->next->next;
        $this->length --;
    }

    /**
     * 清空链表
     * @return $this
     */
    public function clear()
    {
        $this->head->next = null;
        $this->length = 0;
        return $this;
    }

    /**
     * 打印链表元素
     */
    public function print()
    {
        $current = $this->head->next;
        $i = 0;
        echo '<hr>';
        echo sprintf('共有 %d 个元素 :', $this->length);
        while ($current !== null) {
            echo '<br>';
            echo sprintf('当前第 %d 个元素 :  ', $i);
            print_r($current->data);
            $current = $current->next;
            $i ++;
        }
        echo sprintf('<br>打印结束<br><br>');
    }

    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty()
    {
        return $this->length === 0;
    }

    /**
     * 反转链表
     * @return bool
     */
    public function reverse()
    {
        if ($this->length === 0) {
            return false;
        }
        // 从第一个元素开始遍历
        $current = $this->head->next;

        $pre = null;
        while ($current !== null) {
            $next = $current->next;
            // 将当前节点的next指向上一个元素
            $current->next = $pre;
            // 保存上一个节点信息为自己, 为下一个元素指向使用
            $pre = $current;
            // 更新当前操作的元素
            $current = $next;
        }
        // 更新头节点指向最后一个元素
        $this->head->next = $pre;
    }
}

使用

$linkedList = new SingleLinkedList();
$linkedList->insert(1)
    ->insert(2)
    ->insert(['a', 'b', 'c'])
    ->headInsert(-1)
    ->insert(100)
    ->print();

显示结果如下: