目前只实现增删改查。

<?php

/**
* 节点类
*/
class Node 
{
    public $id;
    public $data;
    public $prev;
    public $next;

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

/**
* 双向链表
*/
class DoubleLinkedList
{
    private $head; //头节点

    function __construct($id = null,$data = null)
    {
        $this->head = new Node($id,$data);
    }

    /**
     * 添加节点
     * [addNode description]
     * @param [type] $node [description]
     */
    public function addNode($node)
    {
        $current = $this->head;
        while($current->next != null)
        {
            if($current->id == $node->id)
            {
                echo "节点{$node->id}已存在\n";
                return;
            }
            if ($current->next->id > $node->id) {
                break;
            }
            $current = $current->next;
        }
        $node->prev = $current;
        $node->next = $current->next;
        if($current->next != null){
            $current->next->prev = $node;
        }
        $current->next = $node;
    }

    /**
     * 删除节点
     * [delLink description]
     * @param  [type] $id [description]
     * @return [type]     [description]
     */
    public function delLink($id)
    {
        $ret = $this->findNode($id, true);
        if ($ret['result']) {
            $current = $ret['current'];
            if ($current->next == null) {
                $current->prev->next = null;
            } else {
                $current->prev->next = $current->next;
                $current->prev = $current->prev->prev;
            }
        } else {
            echo "未找到节点{$id}\n";
        }
    }

    /**
     * 查找节点值
     * [findNode description]
     * @param  [type]  $id           [description]
     * @param  boolean $return_array [description]
     * @return [type]                [description]
     */
    public function findNode($id, $return_array = false)
    {
        $current = $this->head;
        if($current->next == null)
        {
            echo "链表为空\n";
            return;
        }
        $found = false;
        while ($current->next != null) {
            if ($current->next->id == $id) {
                $found = true;
                break;
            }
            $current = $current->next;
        }
        //查询结果字符串返回
        $value = empty($current->next->data) ? "未找到节点{$id}" : $current->next->data;
        //是否数组形式返回
        $result = !$return_array ? $value : array('result' => $found,'current' => $current->next);
        return $result;
    }

    /**
     * 更新节点值
     * [updateLink description]
     * @param  [type] $id   [description]
     * @param  [type] $data [description]
     * @return [type]       [description]
     */
    public function updateLink($id, $data)
    {
        $ret = $this->findNode($id, true);
        if ($ret['result']) {
            $current = $ret['current'];
            $current->data = $data;
        } else {
            echo "未找到节点{$id}\n";
        }
    }

    /**
     * 打印链表
     * [getLinkList description]
     * @return [type] [description]
     */
    public function getLinkList()
    {
        $current = $this->head;
        if($current->next == null)
        {
            echo "链表为空\n";
            return;
        }
        $link = '';
        while($current->next != null){
            $link .= $current->next->id."({$current->next->data})".'->';
            $current = $current->next;
        }
        echo rtrim($link,'->')."\n";
    }

    /**
     * 获取链表长度
     * [getLinkLength description]
     * @return [type] [description]
     */
    public function getLinkLength()
    {
        $l = 0;
        $current = $this->head;
        while ($current->next != null) {
            $l++;
            $current = $current->next;
        }
        return $l;
    }

    /**
     * 链表是否为空
     * [isEmpty description]
     * @return boolean [description]
     */
    public function isEmpty()
    {
        return $this->head->next == null;
    }

}

$doubleLists = new DoubleLinkedList();
$doubleLists->addNode(new Node(4,'aaaa'));
$doubleLists->addNode(new Node(1,'eeee'));
$doubleLists->addNode(new Node(3,'bbbb'));
$doubleLists->getLinkList();
echo "链表的长度为:".$doubleLists->getLinkLength()."\n";
$del = 3;
echo "-----------删除节点$del--------\n";
$doubleLists->delLink($del);
$doubleLists->getLinkList();
echo "链表的长度为:".$doubleLists->getLinkLength()."\n";
$update = 4;
echo "-----------更新节点$update--------\n";
$doubleLists->updateLink($update,'cccc');
$doubleLists->getLinkList();
$find = 3;
echo "-----------查询节点$find--------\n";
echo "查询结果:".$doubleLists->findNode($find)."\n";



发表评论

电子邮件地址不会被公开。 必填项已用*标注