PHP 使用链表实现映射

class  Node
{
    public $key;
    public $value;
    public $next;

    public function __construct($key=null,$value,Node $next=null)
    {
        $this->key   = $key; 
        $this->value = $value;
        $this->next =$next; 
    }
}

interface Map
{
    function  getSize();

    function  isEmpty();

    function  add($key,$value);

    function contains($key);

    function get($key);

    function set($key,$value);

    function remove($key);
}

class  LinkedMap  implements Map
{

    private $size;

    private $dummyHead;

    public function __construct()
    {
        $this->size =null;
        $this->dummyHead = new Node();
    }

    public function  isEmpty()
    {
        return $this->size == 0;
    }

    public function getSize()
    {
        return $this->size;
    }

    private function getNode($key)
    {
        $cur = $this->dummyHead->next;

        while($cur!=null){
            if($cur->key ==$key)
                return $cur;
            else
                $cur= $cur->next;
        }

        return null;
    }

    public function contains($key)
    {
        $node = $this->getNode($key);
        return $node !=null; 
    }

    public function get($key)
    {
        $node = $this->getNode($key);
        return $node==null ?null : $node->value;
    }

    public function add($key,$value)
    {
        $node = $this->getNode($key);

        if($node==null){
            $this->dummyHead->next = new Node($this->dummyHead->next);
            $this->size++;
        }else
            $node->value = $value;
    }

    public function set($key,$newValue)
    {
        $node = $this->getNode($key);
        if($node==null)
            throw new  \InvalidArgumentException("set does't exists");

        $node->value =$newValue;
    }

    public function remove($key)
    {
        $prev = $this->dummyHead;

        while($prev->next!=null){
            if($prev->next->key ==$key)
                continue;
            else
                $prev= $prev->next;
        }

        if($prev->next!=null){
            $delNode = $prev->next;
            $prev->next= $delNode->next;
            $delNode->next = null;
            $this->size --;
            reutrn $delNode->value;
        }

        return null;
    }
}

测试用例

$words=[
    'jack','jackson','jack','huan','wang','li','jack','li','king','tom'
];

$map = new \map\LinkedMap();
foreach ($words as $word){
    if($map->contains($word))
        $map->set($word,$map->get($word)+1);
    else
        $map->add($word,1);
}

echo 'total words'.count($words),'<br/>';
echo 'total different words'.$map->getSize(),'<br/>';
echo 'Frenquency of jack: '. $map->get('jack'),'<br/>';
echo 'Frenquency of li: '. $map->get('li'),'<br/>';
echo 'Frequency of huan: '. $map->get('huan'),'<br/>';

本作品采用《CC 协议》，转载必须注明作者和本文链接