循环链表-头插、尾插

本文概要

• 循环单链表 头插、尾插

头插

    class node
    {
        public $data = '';
        public $next = null;

        function __construct($data)
        {
            $this->data = $data;
        }
    }

class linkList
{
    public $size   = 0;
    public $header = null;

    /** 左插 */
    function lLoop($data)
    {
        $node = new node($data);
        // 因是左插，把header赋值给新值【node】
        $node->next   = $this->header;
        $this->header = $node;
        if ($this->size > 0) {
            // 定义临时变量，这里为什么要指向下一节点，请看下面 注释1
            $current = $this->header->next;
            while (true) {
                if ($current->next == $this->header->next) {
                    $current->next = $node;
                    break;
                }

                // 移动下一节点
                $current = $current->next;
            }
        } else {
            // 第一次插入时，尾结点为 next 是自己
            $this->header->next= $node;
        }
        $this->size++;

        return $this;
    }
}

循环单链表图-1

注释1：

因为我先进行了 $node->next = $this->header 赋值；
所在当第三次插入时打印$this->header和$this->header->next结果如下：

header打印

用一张图描述此时数据结构：

image.png

所以 $this->header->next 一直会在入口结点，也就是现在的 2 的位置
而 $current->next; 开始定义了 $current = $this->header->next; 快一步它会循环到尾结点后更新环入口

尾插

    function rLoop($data)
    {
        $node = new node($data);

        if ($this->size > 0) {
            $current = $this->header;
            while (true) {
                if ($current->next == $this->header) {
                    $node->next    = $this->header;
                    $current->next = $node;
                    break;
                }
                $current = $current->next;
            }
        } else {
            $node->next   = $node;
            $this->header = $node;
        }
        $this->size++;

        return $this;
    }

也许有更好的办法，欢迎同学提出！