Solidity中的循环链接列表!

映射不是很好吗？

在Modular，我们正忙于建立一套伟大的标准库 ，这些标准库 易于使用，文档齐全，测试良好，最重要的是，安全。我们想帮助使Ethereum和Solidity更安全，更容易为任何从事开发的人所接受，无论他们是完全的新手还是经验丰富的专家。几个月前，我意识到一个链接列表对一些不同的应用是有用的，最重要的是我们即将完成的互动代币销售的实现。所以我做了一些研究!

除非你需要，否则绝不要从头开始

我可以从头开始，但为什么要这样做，因为你可以利用社区中所有其他了不起的开发者的共享知识和工作！这是每个人都需要记住的。这是每个人都需要记住的事情。很有可能，如果有你想做的事情，至少有人已经开始在做了，而且你可以从参与社区活动中学到很多东西。我们发现

达里尔-莫里斯

的 repo，并认为这是一个很好的开始。

来自维基百科。在计算机科学中，链表是数据元素的线性集合，其中的线性顺序不是由它们在内存中的物理位置决定的。相反，每个元素都指向下一个元素。

循环双链表是指两个连续的元素通过上一个和下一个指针相连，最后一个节点通过下一个指针指向第一个节点，同时头部节点的上一个指针也指向尾部节点。

在这里查看完整的图书馆!

链接列表库提供了创建和操作uint256索引的循环链接列表数据结构所需的功能，允许使用多种不同的函数来与该结构进行交互。像push()和pop()这样的函数可以用来创建FILO堆栈或FIFO环形缓冲区。getAdjacent()也可以用来在列表上迭代。下面是对该功能的简要描述。

• 可以检查列表是否存在并找到尺寸。
• 可以检查某个节点是否存在。
• 获取指定节点的相邻节点。
• 在一个排序的列表中为一个新的节点找到一个位置来放置。
• 插入节点并在节点之间建立链接。
• 从列表中删除、推送和弹出节点。

LinkedList是一个嵌套的映射，第一个键是节点索引（uint256），第二个键是到相邻节点的双向链接（bool）。键值0意味着头部，因此调用合约要避免向LinkedList.list[0]写入或手动链接到LinkedList.list[0]（例如，list[var1][false] = 0;）。

Design Decisions

Linked lists are powerful data structures and can be implemented in a variety of ways. I saw what

Darryl Morris

did in his implementation and I knew that was the best place to start.

Using a mapping:

Using the mapping to store the list made the most sense because of the efficiency benefits. Checking if a node exists in the linked list requires only a few lookups because you can instantly check to see if that entry in the mapping has a valid PREV and NEXT pointer. No iterating through the list is required, essentially making this a O(1) operation.

One drawback of using a mapping is that there can only be one entry per number. This could cause some potential problems in the future, but can be circumvented by having another mapping that indicates how many entries there are at a certain index:

Another drawback of the mapping is that it limits the amount of information that can be stored in the first order data struct. I think this is a necessary tradeoff for usability because the goal of this is to make it useable by anyone. Keeping the list struct as simple as possible accomplishes that. If someone wants to store other information about the node, they can use a separate mapping that is indexed by the nodes in the linked list, like the numEntries case explained above.

Indexing with uint256:

If you think about it, these could be indexed with any data type, but I chose uint256. I think this is the best choice because it allows for linked lists sorted smallest to largest. This again allows for easy lookups and inserts, because when searching for a sorted spot, you can use knowledge about what is already in the list to expedite the search, saving gas.

As you can see, you can make a prediction about where the node to be inserted will go, potentially speeding up the search. Obviously, the search is still O(n), but can potentially be sped up.

Descriptive Function Returns:

You’ll see that some of the functions return multiple values, some including booleans. That is because I want the contracts to be as easy to use and understand as possible. I only want state to get modified if arguments are sent correctly. This is something that we believe is a good design practice for smart contracts in general.

Unless explicitly needed, always do whatever you can to ensure that the sender of function calls is sending all the correct arguments, even if it is the owner of the contract.

People make mistakes all the time and it is important to help avoid those causing issues.

Using the Library in Your Contract

You can find examples in the repo about how to use the Linked List library, but I will give a quick rundown of how to use it.

1. Copy the LinkedListLib.sol into your contracts folder.
2. Include these lines at the beginning of your contract:

3. Thats it! Now you can call any of the functions in the library by using the dot operator.

We have more detailed instructions in our repo for this and all our other libraries! Go check us out!

Conclusion

Again, here is the link to our library that you can use.

I hope you all enjoyed my quick foray into Solidity linked lists! We’re always looking for ways to improve, so any suggestions about the implementation to help with security, usability, efficiency, or documentation are greatly encouraged and appreciated!

We care a lot about making Ethereum secure and useable, so check out our website to see what we do!

Thanks to

C. Brown

for help on the article and library.