{"author":{"address":null,"user":"https://learnblockchain.cn/people/13459"},"content":{"body":"## 简介\r\n\r\n有时Solidity语言本身的数据结构无法很好地满足开发需求，此时我们需要实现相关库。下面是一个双向链表的库合约，在其它合约中引入即可使用。\r\n\r\n\r\n\r\n## 实现\r\n\r\n```solidity\r\n// SPDX-License-Identifier: LGPL-3.0-only\r\npragma solidity 0.8.11;\r\n\r\n/**\r\n * @title Maintains a doubly linked list keyed by bytes32.\r\n * @dev Following the `next` pointers will lead you to the head, rather than the tail.\r\n */\r\nlibrary LinkedList {\r\n\r\n  // 链表节点\r\n  struct Element {\r\n    bytes32 previousKey;\r\n    bytes32 nextKey;\r\n    bool exists;\r\n  }\r\n\t\r\n  // 整条链的信息\r\n  struct List {\r\n    bytes32 head;\r\n    bytes32 tail;\r\n    uint256 numElements;\r\n    mapping(bytes32 =\u003e Element) elements;\r\n  }\r\n\r\n  /**\r\n   * @notice Inserts an element into a doubly linked list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The key of the element to insert.\r\n   * @param previousKey 在previousKey键所对应的节点之前插入\r\n   * @param nextKey 在nextKey键所对应的节点之后插入\r\n   */\r\n  function insert(List storage list, bytes32 key, bytes32 previousKey, bytes32 nextKey) internal {\r\n    require(key != bytes32(0), \"Key must be defined\");\r\n    require(!contains(list, key), \"Can't insert an existing element\");\r\n    require(\r\n      previousKey != key \u0026\u0026 nextKey != key,\r\n      \"Key cannot be the same as previousKey or nextKey\"\r\n    );\r\n\r\n    Element storage element = list.elements[key];\r\n    element.exists = true;\r\n\r\n    if (list.numElements == 0) {  // 首个节点\r\n      list.tail = key;\r\n      list.head = key;\r\n    } else {\r\n      require(    // 不能全为0 （因为只有插入首个节点时，才是全为0）\r\n        previousKey != bytes32(0) || nextKey != bytes32(0),\r\n        \"Either previousKey or nextKey must be defined\"\r\n      );\r\n\r\n      element.previousKey = previousKey;\r\n      element.nextKey = nextKey;\r\n\r\n      if (previousKey != bytes32(0)) {  // 等于0时表示插入末尾\r\n        require(\r\n          contains(list, previousKey),\r\n          \"If previousKey is defined, it must exist in the list\"\r\n        );\r\n        Element storage previousElement = list.elements[previousKey];\r\n        // 检查previousKey和nextKey一开始是不是相邻的\r\n        require(previousElement.nextKey == nextKey, \"previousKey must be adjacent to nextKey\");\r\n        previousElement.nextKey = key;\r\n      } else {\r\n        list.tail = key;\r\n      }\r\n\r\n      if (nextKey != bytes32(0)) {\r\n        require(contains(list, nextKey), \"If nextKey is defined, it must exist in the list\");\r\n        Element storage nextElement = list.elements[nextKey];\r\n        require(nextElement.previousKey == previousKey, \"previousKey must be adjacent to nextKey\");\r\n        nextElement.previousKey = key;\r\n      } else {\r\n        list.head = key;\r\n      }\r\n    }\r\n\r\n    list.numElements = list.numElements + 1;\r\n  }\r\n\r\n  /**\r\n   * @notice 在双向链表的节点插入一个元素\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The key of the element to insert.\r\n   */\r\n  function push(List storage list, bytes32 key) internal {\r\n    insert(list, key, bytes32(0), list.tail);\r\n  }\r\n\r\n  /**\r\n   * @notice Removes an element from the doubly linked list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The key of the element to remove.\r\n   */\r\n  function remove(List storage list, bytes32 key) internal {\r\n    Element storage element = list.elements[key];\r\n    require(key != bytes32(0) \u0026\u0026 contains(list, key), \"key not in list\");\r\n    if (element.previousKey != bytes32(0)) {\r\n      Element storage previousElement = list.elements[element.previousKey];\r\n      previousElement.nextKey = element.nextKey;\r\n    } else {\r\n      list.tail = element.nextKey;\r\n    }\r\n\r\n    if (element.nextKey != bytes32(0)) {\r\n      Element storage nextElement = list.elements[element.nextKey];\r\n      nextElement.previousKey = element.previousKey;\r\n    } else {\r\n      list.head = element.previousKey;\r\n    }\r\n\r\n    delete list.elements[key];\r\n    list.numElements = list.numElements - 1;\r\n  }\r\n\r\n  /**\r\n   * @notice Updates an element in the list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The element key.\r\n   * @param previousKey The key of the element that comes before the updated element.\r\n   * @param nextKey The key of the element that comes after the updated element.\r\n   */\r\n  function update(List storage list, bytes32 key, bytes32 previousKey, bytes32 nextKey) internal {\r\n    require(\r\n      key != bytes32(0) \u0026\u0026 key != previousKey \u0026\u0026 key != nextKey \u0026\u0026 contains(list, key),\r\n      \"key on in list\"\r\n    );\r\n    remove(list, key);\r\n    insert(list, key, previousKey, nextKey);\r\n  }\r\n\r\n  /**\r\n   * @notice Returns whether or not a particular key is present in the sorted list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The element key.\r\n   * @return Whether or not the key is in the sorted list.\r\n   */\r\n  function contains(List storage list, bytes32 key) internal view returns (bool) {\r\n    return list.elements[key].exists;\r\n  }\r\n\r\n  /**\r\n   * @notice Returns Element based on key.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param key The element key.\r\n   * @return Whether or not the key is in the sorted list.\r\n   */\r\n  function get(List storage list, bytes32 key) internal view returns (Element memory) {\r\n    return list.elements[key];\r\n  }\r\n\r\n  /**\r\n   * @notice Returns the keys of the N elements at the head of the list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @param n The number of elements to return.\r\n   * @return The keys of the N elements at the head of the list.\r\n   * @dev Reverts if n is greater than the number of elements in the list.\r\n   */\r\n  function headN(List storage list, uint256 n) internal view returns (bytes32[] memory) {\r\n    require(n \u003c= list.numElements, \"not enough elements\");\r\n    bytes32[] memory keys = new bytes32[](n);\r\n    bytes32 key = list.head;\r\n    for (uint256 i = 0; i \u003c n; i = i + 1) {\r\n      keys[i] = key;\r\n      key = list.elements[key].previousKey;\r\n    }\r\n    return keys;\r\n  }\r\n\r\n  /**\r\n   * @notice Gets all element keys from the doubly linked list.\r\n   * @param list A storage pointer to the underlying list.\r\n   * @return All element keys from head to tail.\r\n   */\r\n  function getKeys(List storage list) internal view returns (bytes32[] memory) {\r\n    return headN(list, list.numElements);\r\n  }\r\n}\r\n```\r\n\r\n\r\n\r\n## 如何使用\r\n\r\n上面库合约中只是进行了节点的链接，并不能存放值。我们应该这样使用：\r\n\r\n```solidity\r\nimport \"./LinkedList.sol\";  // 引入\r\n\r\ncontract Test {\r\n    using LinkedList for LinkedList.List;\r\n\r\n    struct List {\r\n        LinkedList.List list;\r\n        mapping(bytes32 =\u003e uint256) values;\r\n    }\r\n    \r\n    function insert(\r\n    \tList storage list,\r\n    \tbytes32 key,\r\n    \tuint256 value,\r\n    \tbytes32 previousKey, \r\n    \tbytes32 nextKey\r\n    ) {\r\n    \t// 关键部分\r\n    \tlist.list.insert(key, previousKey, nextKey);\r\n    \tlist.values[key] = value;\r\n    }\r\n}\r\n```\r\n\r\n\u003cbr\u003e\r\n\r\n\u003e 区块链\\\u0026web3开发技术交流群（纯净版）欢迎加入交流:\u003chttps://t.me/+PGwDonY3f2o3NDg1\u003e","title":"Solidity库 | 双向链表"},"history":null,"timestamp":1733297023,"version":1}