数据结构与算法之PHP实现链表类(单链表/双链表/循环链表)
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。
链表分为单链表、双链表、循环链表。

1. 单向链表

单向链表 插入:链表中插入一个节点的效率很高。向链表中插入一个节点,需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点(见下图)。 单向链表插入节点

由上图可知,B、C之间插入D,三者之间的关系为

current为插入节点的前驱节点 current->next = new // B节点指向新节点D
new->next = current->next // 新节点D指向B的后继节点C
删除:从链表中删除一个元素,将待删除元素的前驱节点指向待删除元素的后继节点,同时将待删除元素指向 null,元素就删除成功了(见下图)。

单向链表插入节点

由上图可知,A、C之间删除B,三者之间的关系为

current为要删除节点的前驱节点
current->next = current->next->next // A节点指向C节点

<?php

class Node
{
    public $data;

    private $next;

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

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

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

class Links
{
    private $header;
    public function __construct($data)
    {
        $this->header = new Node($data);
        //$this->header->setNext($this->header); 加上这句话为循环列表
    }

    public function find($data)
    {
        $current = $this->header;
        while ($current->data != $data) {
            $current = $current->getNext();
        }
        return $current;
    }

    public function put($header, $data)
    {
        $node = new Node($data);

        $current = $this->find($header);
        if ($current->data && $current->getNext() != $this->header) {
            $node->setNext($current->getNext());
            $current->setNext($node);
        } else {
            $current->setNext($node);
            $node->setNext($this->header);
        }

    }

    public function del($data)
    {
        $current = $this->header;
        while ($current->getNext()->data != $data) {
            $current = $current->getNext();
        }

        if ($current->getNext() != $this->header) {
            // 链表中间
            $current->setNext($current->getNext()->getNext());
        } else {
            // 链表尾端
            $current->setNext($this->header);
        }
    }

}

$ln = new Links('');
// print_r($ln);

$ln->put('', 'two');
// print_r($ln);

$ln->put('two', 'three');
// print_r($ln);

$ln->put('three', 'four');
// print_r($ln);
// exit;

$ln->del('three');
print_r($ln);

2. 双向链表

单链表从链表的头节点遍历到尾节点很简单,但从后向前遍历就没那么简单了。它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。
所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
单向链表 插入:插入一个节点时,需要指出该节点正确的前驱和后继。
修改待插入节点的前驱节点的next属性,使其指向新加入的节点,而新插入的节点的next属性则指向原来前驱指向的节点,同时将原来前驱指向的节点的previous属性指向新节点,而新加入节点的previous属性指向它前驱节点(见下图)。
单向链表插入节点 由上图可知,B、C之间插入D,三者之间的关系为
current为插入节点的前驱节点
current->next = new // B的next属性指向新节点D
new->next = current->next // 新节点D的next属性指向B的后继节点C
current->next->previous = new // B的后继节点C的previous属性指向新节点D(原先是C的previous属性指向B)
删除:双向链表的删除操作比单向链表的效率更高,因为不需要再查找前驱节点了。
首先需要在链表中找出存储待删除数据的节点,然后设置该节点前驱的 next 属性,使其指向待删除节点的后继;设置该节点后继的 previous 属性,使其指向待删除节点的前驱。
单向链表插入节点 由上图可知,B、C之间删除D,三者之间的关系为
current为要删除的节点
current->previous->next = current->next // B的前驱节点A的next属性指向B的后继节点C
current->next->previous = current->previous // B的后继节点C的previous属性指向B的前驱节点A
current->previous = null // B的previous属性指向null
current->next = null // B的next属性指向null

<?php

class Node
{
    public $data;

    private $next;

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

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

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

class Links
{
    private $header;
    public function __construct($data)
    {
        $this->header = new Node($data);
        $this->header->setNext($this->header);
    }

    public function find($data)
    {
        $current = $this->header;
        while ($current->data != $data) {
            $current = $current->getNext();
        }
        return $current;
    }

    public function put($header, $data)
    {
        $node = new Node($data);

        $current = $this->find($header);
        if ($current->data && $current->getNext() != $this->header) {
            $node->setNext($current->getNext());
            $current->setNext($node);
        } else {
            $current->setNext($node);
            $node->setNext($this->header);
        }

    }

    public function del($data)
    {
        $current = $this->header;
        while ($current->getNext()->data != $data) {
            $current = $current->getNext();
        }

        if ($current->getNext() != $this->header) {
            // 链表中间
            $current->setNext($current->getNext()->getNext());
        } else {
            // 链表尾端
            $current->setNext($this->header);
        }
    }

}

$ln = new Links('');
// print_r($ln);

$ln->put('', 'two');
// print_r($ln);

$ln->put('two', 'three');
// print_r($ln);

$ln->put('three', 'four');
// print_r($ln);
// exit;

$ln->del('three');
print_r($ln);

results matching ""

    No results matching ""

    results matching ""

      No results matching ""