php版链表的实现

<?php
class Node {
    private $data;
    private $next;

    public function getData() {
        return $this->data;
    }

    public function setData($data) {
        $this->data = $data;
        return true;
    }

    public function getNext() {
        return $this->next;
    }

    public function setNext($next) {
        $this->next = $next;
        return true;
    }
}

/**
 * 链表类
 */
class Link {
    private $size = 0;
    private $first;
    private $last;

    /**
     * 获取链表长度
     */
    public function getLength() {
        return $this->size;
    }

    /**
     * 链表中插入第一个元素的时候,头和尾部都是同一个元素
     */
    public function oneNode(string $element) {
        $this->first = new Node;
        $this->first->setData($element);
        $this->last = $this->first;
    }

    /**
     * 当只有一个元素的时候,删除$fist和$last
     */
    public function clear() {
        $this->first = $this->last = null;
    }
    
    /**
     * 头节点插入
     */
    public function addHead(string $element) {
        if ($this->size == 0) {
            $this->oneNode($element);
        } else {
            $node = new Node;
            $node->setData($element);
            $node->setNext($this->first);
            $this->first = $node;
        }
        $this->size++;
        return true;
    }
    
    /**
     * 尾节点插入
     */
    public function addTail(string $element) {
        if ($this->size == 0) {
            $this->oneNode($element);
        } else {
            $node = new Node();
            $node->setData($element);
            $this->last->setNext($node);
            $this->last = $node;
        }

        $this->size++;
    }

    /**
     * 中间节点插入
     */
    public function add(int $index, string $element) {
        if ($index <= $this->size) {
            if ($this->size == 0) {
                oneNode($element);
            } elseif ($index == 0) {
                $this->addHead($element);
            } elseif ($index == $this->size) {
                $this->addTail($element);
            } else {
                $tmp = $this->get($index - 1);
                $node = new Node;
                $node->setData($element);
                $node->setNext($tmp->getNext());
                $tmp->setNext($node);
            }
            $this->size++;
        } else {
            throw new \Exception("插入位置无效或超出链表长度");
        }
    }
    
    /**
     * 获取指定位置的元素
     */
    public function get(int $index) {
        $tmp = $this->first;
        for ($i = 0; $i < $index - 1; $i++) {
            $tmp = $tmp->getNext();
        }
        return $tmp;
    }

    /**
     * 删除头节点
     */
    public function deleteFirst() {
        if ($this->size == 0) {
            throw new \Exception("空链表,无元素可删除");
        } elseif ($this->size == 1) {
            $this->clear();
        } else {
            $tmp = $this->first;
            $this->first = $tmp->getNext();
            $this->size--;
        }
    }

    /**
     * 删除尾节点
     */
    public function deleteLast() {
        if ($this->size == 0) {
            throw new \Exception("空链表,无元素可删除");
        } elseif ($this->size == 1) {
            $this->clear();
        } else {
            $tmp = $this->get($this->size - 1);
            $tmp->setNext(null);
            $this->size--;
        }
    }

    /**
     * 删除指定节点
     */
    public function deleteIndex(int $index) {
        if ($this->size == 0) {
            throw new \Exception("空链表,无元素可删除");
        } elseif ($this->size == 1) {
            $this->clear();
        } else {
            $tmp = $this->get($index - 1);
            $tmp->setNext($tmp->getNext()->getNext());
            $this->size--;
        }
    }
    
    /**
     * 反转节点
     */
    public function receve() {
        if ($this->size < 2) {
            return true;
        } else {
            $tmp = $this->first;
            $last = $tmp;
            $next = $this->first->getNext();
            for($i = 0; $i < $this->size - 1; $i++) {
                $nextNext = $next->getNext();
                $next->setNext($tmp);
                $tmp = $next;
                $next = $nextNext;
            }
            $last->setNext(null);
            $this->first = $tmp;
            return true;
        }
    }

    /**
     * 打印现有的所有元素
     */
    public function printLink() {
        $tmp = $this->first;
        if(is_null($tmp)) {
            return false;
        } 
        echo $tmp->getData();
        while(!is_null($tmp->getNext())) {
            $tmp = $tmp->getNext();
            echo "->" . $tmp->getData();
        }
        echo "\n";
    }
}

$link = new Link();
$link->addHead("1");
$link->printLink(); // 1

$link->addHead("5");
$link->printLink(); // 5->1

$link->addTail("9");
$link->printLink(); // 5->1->9

$link->addTail("7");
$link->printLink(); // 5->1->9->7

$link->add(3, "8"); 
$link->printLink(); // 5->1->9->8->7

print_r("链表长度:" . $link->getLength() . "\n");

$link->deleteFirst();
$link->printLink();

$link->deleteLast();
$link->printLink();

$link->deleteIndex(1);
$link->printLink();

print_r("链表长度:" . $link->getLength() . "\n");

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • jq将form 表单数据转为object

    我平常上传数据都是使用$(this).serialize(),但是这次我需要使用上传数据的对象。结果这个方法给我转成了字符串。特别不方便。于是找到一个插件。就可...

    魔王卷子
  • lumen切换 nikic/fast-route 为 illuminate/routing

    接下来我们要替换路由组件。通过读取相关源码,我们知道注册路由组件是通过Laravel\Lumen\Application::bootstrapRouter()进...

    魔王卷子
  • CORS的一点事

    我们公司有个 m 域名,主要是用来访问前端编译文件。然后有一个 api 域名,用来提供接口请求。我发现我们的接口每次访问都会请求两次。第一次是 OPTION 请...

    魔王卷子
  • 第166天:canvas绘制饼状图动画

    半指温柔乐
  • 深入浅出JavaScript之this

    JavaScript中的this比较灵活,根据在不同环境下,或者同一个函数在不同方式调用下,this都有可能是不同的。但是有一个总的原则,那就是this指的是,...

    哲洛不闹
  • 商品多种规格属性的选择(sku 算法)

    如上图中每一个单规格选项,例如==珍珠白==、==12GB+512GB==、==不分期==就是一个规格(sku)。商品和 sku 属于一对多的关系,也就是我们可...

    Krry
  • JavaScript中的 this的理解

    在JavaScript编程中 , this的关键字总是让初学者感到迷惑 , this到底是什么呢?

    越陌度阡
  • 数据结构与JS也可以成为CP(十)Graph图

    1)深度优先搜索算法比较简单:访问一个没有访问过的顶点,将它标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

    萌兔IT
  • Javascript中关键参数this浅析

    Sb_Coco
  • 树莓派 + Node.js 造一个有灵魂的语音助手

    volute(蜗壳)是一个使用 Raspberry Pi+Node.js 制作的语音助手.

    五月君

扫码关注云+社区

领取腾讯云代金券