Circular Linked List in Solidity!
Aren’t mappings great?
At Modular, we’re busy working on building a great set of standard libraries that are easy to use, well documented, well tested, and most importantly, secure. We want to help make Ethereum and Solidity safer and more accessible for anyone doing development, whether they are a complete newbie or a seasoned pro. A couple months ago, I realized that a linked list would be useful for a few different applications, most importantly the implementation of the Interactive Token Sale that we are close to finishing building. So I did some research!
Never Start From Scratch unless you need to
I could have started from scratch but why do that when you can take advantage of the shared knowledge and work of all the other amazing developers in the community! That is something that everyone needs to take to heart here. Odds are, if there is something you want to do, someone has at least started working on it, and there is a lot you can learn from engaging with the community. We found Darryl Morris’s repo here and thought it was a great place to start.
From Wikipedia: In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next.
A circular doubly linked list is when two consecutive elements are linked by previous and next pointer and the last node points to first node by next pointer and also the previous pointer of the head node points to the tail node.
Check out the full library here!
The Linked List library provides functionality needed to create and manipulate a uint256-indexed Circular Linked List Data structure by allowing a multitude of different functions to be used to interact with the struct. Functions like push() and pop() can be used to create a FILO stack or FIFO ring buffer. getAdjacent() can also be used to iterate over the list. Here is a brief description of the functionality:
- Can check if the list exists and find the size.
- Can check if a certain node exists.
- Gets adjacent nodes to a specified node.
- Finds a spot in a sorted list for a new node to be placed.
- Insert nodes and create links between nodes.
- Remove, push, and pop nodes from the list.
LinkedList is a nested mapping with the first key being the node index (uint256) and the second being the bidirectional link (bool) to a neighboring node. Key 0 implies the head so writes to LinkedList.list[0] or manually linking to Linkedlist.list[0] (e.g. list[var1][false] = 0;) are to be avoided by the calling contract.
struct LinkedList{
mapping (uint256 => mapping (bool => uint256)) cll;
}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:
/// @dev returns true if the node exists
/// @param self stored linked list from contract
/// @param _node a node to search for
function nodeExists(LinkedList storage self, uint256 _node)
internal
view returns (bool)
{
if (self.list[_node][PREV] == HEAD &&
self.list[_node][NEXT] == HEAD)
{
if (self.list[HEAD][NEXT] == _node) {
return true;
} else {
return false;
}
} else {
return true;
}
}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:
mapping (uint256 => uint256) numEntries;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.
/// @dev Can be used before `insert` to build an ordered list
/// @param self stored linked list from contract
/// @param _node an existing node to search from, e.g. HEAD.
/// @param _value value to seek
/// @param _direction direction to seek in
// @return next first node beyond '_node' in direction `_direction`
function getSortedSpot(LinkedList storage self, uint256 _node, uint256 _value, bool _direction)
internal view returns (uint256)
{
if (sizeOf(self) == 0) { return 0; }
require((_node == 0) || nodeExists(self,_node)); bool exists;
uint256 next;
(exists,next) = getAdjacent(self, _node, _direction); while ((next != 0) && (_value != next) && ((_value < next) != _direction)) next = self.list[next][_direction]; return next;
}
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.
/// @dev Returns the link of a node `_node` in direction `_direction`.
/// @param self stored linked list from contract
/// @param _node id of the node to step from
/// @param _direction direction to step in
function getAdjacent(LinkedList storage self, uint256 _node, bool _direction)
internal view returns (bool,uint256)
{
if (!nodeExists(self,_node)) {
return (false,0);
} else {
return (true,self.list[_node][_direction]);
}
}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.
- Copy the LinkedListLib.sol into your contracts folder.
- Include these lines at the beginning of your contract:
import "./LinkedListLib.sol";
contract <Contract Name> {
using LinkedListLib for LinkedListLib.LinkedList;
uint256 constant NULL = 0;
uint256 constant HEAD = 0;
bool constant PREV = false;
bool constant NEXT = true;
LinkedListLib.LinkedList list;3. Thats it! Now you can call any of the functions in the library by using the dot operator.
return list.getAdjacent(_node,_direction);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.
