札记之PHP实现循环链表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:head->next = head，换句话说，链表的尾节点指向头节点，形成了一个循环链表。

图示插入删除流程

插入

删除

完整php代码

class ListNode
{
    private $data;
    private $next;
    public function __construct($data)
    {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

// 循环链表类
class CircularLinkedList 
{
    private $head = NULL;
    private $length = 0;
    private $currentNode;

    public function find($data = NULL) 
    {
        $currentNode = $this->head;
        if ($this->head !== NULL) {
            while ($currentNode->data !== $data) {
                $currentNode = $currentNode->next;
            }
            return $currentNode;
        }
        return false;
    }

    // 插入新节点
    public function insert($data = NULL, $query = NULL)
    {
        $newNode = new ListNode($data);
        if ($this->head) {
            $currentNode = $this->find($query);
            if ($currentNode->next !== $this->head) {
                $currentNode->next = $newNode;
                $newNode->next = $currentNode->next;
            } else { 
                // 链表尾端
                $currentNode->next = $newNode;
                $newNode->next = $this->head;
            }
        } else {
            $this->head = &$newNode;
        }
        $this->length++;
        $newNode->next = $this->head;
        return true;
    }

    // 删除节点
    public function delete($data = NULL) 
    {
        $currentNode = $this->head;
        while ($currentNode->next != NULL && $currentNode->next->data != $data) {
            $currentNode = $currentNode->next;
        }
        // 链表中间
        if ($currentNode->next != $this->head) { 
            $currentNode->next = $currentNode->next->next;
        } else { 
            // 链表尾端
            $currentNode->next = $this->head;
        }
    }

    public function display()
    {
        echo 'LinkList length: ' . $this->length . PHP_EOL;
        $currentNode = $this->head;
        while ($currentNode->next != $this->head) {
            echo $currentNode->next->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }
}

print("============插入=========== \n\r");
printf("插入节点33333, 44444, 55555 \n\r");
$CircularLinkObj = new CircularLinkedList();
$CircularLinkObj->insert(33333, 11111);
$CircularLinkObj->insert(44444, 33333);
$CircularLinkObj->insert(55555, 44444);
$CircularLinkObj->display();

print("============删除=========== \n\r");
printf("删除节点55555 \n\r");
$CircularLinkObj->delete(55555);
$CircularLinkObj->display();

运行结果：

============插入===========
插入节点33333, 44444, 55555
LinkList length: 3
44444
55555
============删除===========
删除节点55555
LinkList length: 3
44444