浅谈php实现映射的两种方法「链表和二叉树」

1. 链表实现映射

链表是一种非常常见的数据结构，通过节点之间的指针连接来存储和访问数据。在PHP中，可以使用链表来实现映射的数据结构。

1.1. 链表节点

首先，我们需要定义一个链表节点的类，该类包含两个属性：key和value。key表示映射中的键，value表示映射中的值。同时，节点类还需要包含一个指向下一个节点的指针，用于构建链表结构。

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

1.2. 链表实现映射

接下来，我们可以定义一个映射类，该类内部使用链表来实现映射的功能。映射类需要包含以下几个方法：

put: 向映射中添加一个键值对。

get: 根据键获取映射中对应的值。

remove: 根据键从映射中删除对应的键值对。

具体实现如下：

class LinkedListMap {
    private $dummyHead; // 虚拟头节点
    private $size; // 映射的大小
    
    public function __construct() {
        $this->dummyHead = new Node(null, null); // 初始化虚拟头节点
        $this->size = 0;
    }
    
    public function put($key, $value) {
        $cur = $this->dummyHead->next;
        while ($cur != null) {
            if ($cur->key == $key) { // 如果键已存在，更新对应的值
                $cur->value = $value;
                return;
            }
            $cur = $cur->next;
        }
        $newNode = new Node($key, $value); // 创建新节点
        $newNode->next = $this->dummyHead->next; // 将新节点插入到虚拟头节点后面
        $this->dummyHead->next = $newNode;
        $this->size++;
    }
    
    public function get($key) {
        $cur = $this->dummyHead->next;
        while ($cur != null) {
            if ($cur->key == $key) {
                return $cur->value;
            }
            $cur = $cur->next;
        }
        return null; // 如果键不存在，返回null
    }
    
    public function remove($key) {
        $prev = $this->dummyHead;
        while ($prev->next != null) {
            if ($prev->next->key == $key) {
                $delNode = $prev->next;
                $prev->next = $delNode->next;
                $delNode->next = null; // 断开删除节点的连接
                $this->size--;
                return $delNode->value;
            }
            $prev = $prev->next;
        }
        return null; // 如果键不存在，返回null
    }
    
    public function getSize() {
        return $this->size;
    }
    
    public function isEmpty() {
        return $this->size == 0;
    }
}

使用链表实现映射的优点是插入和删除操作的时间复杂度为O(1)，但查找操作的时间复杂度为O(n)。