gas优化之使用mapping实现双向链表

双向链表的核心 gas 优势是 O(1) 增删 + 顺序保持，**适合需要动态管理且需要枚举成员的场景，**具体体现在这几个方面：

1. 删除操作固定成本

对比 mapping + 动态数组 的方案：

数组 shift（保持顺序）需要逐个移动后续元素，每个存储写都是 5k gas；即使 swapAndPop 不保持顺序，也要先花 O(n) 的冷 SLOAD 去定位索引。gas随列表长度线性增长，且数组越大gas越贵。

而双向链表，O(1)：直接改 prev.next 和 next.prev ，固定 ~15k-20k gas，与 n 无关。

2. 计数器 O(1)，无需遍历

uint256 public count;   // 增删时同步维护

3. 删除时获得存储清理返还

delete _nodes[_addr];   // 清理两个存储槽（prev + next）
delete _exists[_addr];  // 清理 bool 槽

4. 添加固定为 O(1) 头插

// 不管当前有 10 个还是 1000 个地址，add() 成本几乎不变
_nodes[_addr] = Node(address(0), head);
_exists[_addr] = true;
head = _addr;

头插法永远只操作头节点和新节点，不需要遍历找末尾，也不需要扩容数组。

5. 遍历时的存储访问优化

function getAll() external view returns (address[] memory) {
// ...
current = _nodes[current].next;   // 暖 SLOAD：100 gas
}

链表节点的 next 指针和地址值打包在同一个存储槽里（Node struct），一次 SLOAD 就能读全。如果设计得当，遍历 100 个节点的 getAll 约 6-7 万 gas，属于可接受的 view 调用成本。

具体实现，白名单场景为例：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

contract Whitelist {
    error Unauthorized();
    error AlreadyInList(address addr);
    error NotInList(address addr);

    event Added(address indexed addr);
    event Removed(address indexed addr);

    struct Node {
        address prev;
        address next;
    }

    mapping(address => Node) private _nodes;       // 链表节点
    mapping(address => bool) private _exists;      // 存在性快速检查 (一次暖 SLOAD)
    address public head;                            // 链表头
    uint256 public count;                           // 当前节点数量 (避免遍历计数)

    address public immutable owner;

    modifier onlyOwner() {
        if (msg.sender != owner) revert Unauthorized();
        _;
    }

    constructor() {
        owner = msg.sender;
    }
    /// @notice 添加地址到白名单
    function add(address _addr) external onlyOwner {
        if (_exists[_addr]) revert AlreadyInList(_addr);

        // 更新旧头节点的 prev 指针
        if (head != address(0)) {
            _nodes[head].prev = _addr;               // 一次暖 SSTORE
        }

        // 写入新节点 (一次冷 SSTORE, 两个槽)
        _nodes[_addr] = Node(address(0), head);
        _exists[_addr] = true;                       // 一次冷 SSTORE

        // 更新全局状态
        head = _addr;

        // 计数器递增 (安全无溢出，unchecked)
        unchecked {
            count++;
        }

        emit Added(_addr);
    }

    /// @notice 从白名单移除地址
    function remove(address _addr) external onlyOwner {
        if (!_exists[_addr]) revert NotInList(_addr);

        Node memory node = _nodes[_addr];            // 缓存两个 SLOAD 到内存
        address prev = node.prev;
        address next = node.next;

        // 更新邻居指针
        if (prev != address(0)) {
            _nodes[prev].next = next;                // 暖 SSTORE
        } else {
            head = next;                              // 移除的是头节点
        }
        if (next != address(0)) {
            _nodes[next].prev = prev;                // 暖 SSTORE
        }

        // 删除节点数据，获得 gas 返还
        delete _nodes[_addr];
        delete _exists[_addr];

        // 计数器递减
        unchecked {
            count--;
        }

        emit Removed(_addr);
    }

    /// @notice 返回所有白名单地址（遍历链表）
    function getAll() external view returns (address[] memory) {
        uint256 len = count;                         // 一次 SLOAD 即可获得长度
        address[] memory result = new address[](len);
        address current = head;

        for (uint256 i = 0; i < len; ) {
            result[i] = current;
            current = _nodes[current].next;          // 暖 SLOAD (100 gas)
            unchecked {
                ++i;
            }
        }
        return result;
    }

    /// @notice 查询地址是否在白名单中
    function contains(address _addr) external view returns (bool) {
        return _exists[_addr];
    }
}