醉丶春风的Blog

循环单链表

循环单链表也是单链表的一种, 他和单链表的区别就在于最后一个节点, 单链表的最后一个节点指向null, 而循环单链表的最后一个节点指向head,这样就形成了一个循环, 如下图

php实现

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

节点类

class Node {
    /**
     * @var mixed data
     */
    public $data;

    /**
     * @var self $next
     */
    public $next = null;

    public function __construct($data, $next = null)
    {
        $this->data = $data;

        $this->next = $next;
    }
}

链表类

该链表实现了添加,删除,更新,头部插入,清空链表, 反转链表等方法, 请自行查看代码

class CycleSingleLinkedList {

    public $head = null;

    public $length = 0;

    /**
     * CycleSingleLinkedList constructor.
     * 初始化链表, 使head->next = head
     * @param null $data
     */
    public function __construct($data = null)
    {
        $this->head = new Node($data);
        $this->head->next = $this->head;
    }

    public function getHead()
    {
        return $this->head;
    }

    /**
     * 插入数据, 把最后一个插入的元素指向head
     * @param $data
     * @return $this
     */
    public function insert($data)
    {
        $current = $this->head->next;
        while ($current->next != $this->head) {
            $current = $current->next;
        }

        $current->next = new Node($data, $this->head);

        $this->length ++;
        return $this;
    }

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

    /**
     * 更新数据, 不更新指针, 只更新数据, 所以只要找到对应的元素就行了
     * @param $index
     * @param $data
     * @return $this|bool
     */
    public function update($index, $data)
    {
        if ($index > $this->length || $this->length <= 0) {
            return false;
        }
        $index = $index < 0 ? $this->length + $index : $index;
        $current = $this->head->next;
        $i = 0;
        while ($i != $index) {
            $current = $current->next;
            $i ++;
        }
        $current->data = $data;
        return $this;
    }

    /**
     * 删除元素, 从head开始查找, 不从第一位查找, 这样找到的元素就是要删除的元素前一个, 直接更改指针指向即可
     * @param $index
     * @return $this|bool
     */
    public function delete($index)
    {
        if ($index > $this->length || $this->length <= 0) {
            return false;
        }
        $index = $index < 0 ? $this->length + $index : $index;
        // 查找到要删除的元素的前一位, 把指向该元素的指针指向该元素指向的指针, 故从head开始查找
        $current = $this->head;
        $i = 0;
        while ($i != $index) {
            $current = $current->next;
            $i ++;
        }
        $current->next = $current->next->next;
        $this->length --;
        return $this;
    }

    public function print()
    {
        echo '<hr>';
        $current = $this->head->next;
        $i = 0;
        while ($current != $this->head) {
            echo sprintf('当前第%d个元素: ', $i);
            print_r($current->data);
            echo '<br>';
            $i ++;
            $current = $current->next;
        }
    }

    /**
     * 清空链表, head->next->head
     */
    public function clear()
    {
        $this->head->next = $this->head;
    }

    /**
     * 链表反转, head->1->2->3 变成  head->3->2->1
     * @return $this
     */
    public function reverse()
    {
        $current = $this->head->next;
        $pre = $this->head;

        while ($current != $this->head)
        {
            $next = $current->next;
            $current->next = $pre;
            $pre = $current;
            $current = $next;
        }

        $this->head->next = $pre;
        return $this;
    }
}

测试使用

$linkedList = new CycleSingleLinkedList();
$linkedList->insert(1)
    ->insert(2)
    ->insert(3)
    ->insert(4)
    ->headInsert(0)
    ->headInsert(-1)
    ->update(2, 11)
    ->update(-1, 'last')
    ->print();
// 反转链表
$linkedList->reverse()->print();

$linkedList1 = new CycleSingleLinkedList();
$linkedList1->insert(1)
    ->headInsert(0)
    ->insert(2)
    ->delete(1)
    ->delete(0)
    ->delete(0)
    ->print();