Implementation of Linked Lists in Solidity
mapping(bytes32 => SimpleStruct) public data;`) and then memorize the reference.
This can be done also with an array, if you want to make things simple.
Doubly Linked
Doubly linked lists are the easiest to understand.
Them main methods of every list are _push and _remove.
`shell
function _push(bytes32 element)
function _remove(bytes32 element)
`
- With the _push we can add an element to the top of the list.
- With the _remove function we can _remove an element.
If we use the LinkedList and not the CheapLinkedList, we also have the number of element in the list.
The LinkedList also has the method `getListAsArray(uint256 page, uint256 pageSize)` usefull if we want get the elements in our list with pagination support.
Parameters:
- page: The page number (0-indexed) to retrieve
- pageSize: The number of elements per page
Example:
`solidity
// Get the first 10 elements (page 0, pageSize 10)
bytes32[] memory firstPage = linkedList.getListAsArray(0, 10);
// Get the second batch of 10 elements (page 1, pageSize 10)
bytes32[] memory secondPage = linkedList.getListAsArray(1, 10);
// Get all elements at once (page 0, large pageSize)
bytes32[] memory allElements = linkedList.getListAsArray(0, 1000);
`
Singly Linked
In this implementation we also have the _push and _remove methods, but there is not check if the element was previously _pushed into the list. THis does not mean that _pushing the same element should be done, this means that the check need to be done off chain. The `isListed(bytes32 element)` can be used for the verification off chain.
`shell
function _push(bytes32 element)
function _remove(bytes32 previous)
`
The function _remove have a different scope. It do not _remove the element passed to the function. This function delete the following (or next) element.
There is a function, to get the previous element, of the element that we want to _remove, `function getPrevious(bytes32 element)`.
MapOfLinkedList
There is also an implementation of list mapped. Each sinlgy and doubly listed are implemented.
`shell
function _push(bytes32 index, bytes32 element)
function _remove(bytes32 index, bytes32 element)
`
The index rappresent the mapping. Before be able to insert data into an index it must be registered by using `function registerIndex(bytes32 index)`
ListOfLinkedList
In this type we have a list that contain the first element of every other list.
`shell
function _push(bytes32 index, bytes32 element)
function _remove(bytes32 index, bytes32 element)
`
This type is more advanced that the MapOfLinkedList. In MapOfLinkedList you cannot retrive the list of indexes, in the ListOfLinkedList type you can.
There is also a usefull function to read the structure called `getStructureAsArray()`. This function return an array of array that rappresent the list of list.
Pagination Support:
All array retrieval methods support pagination:
`solidity
// Get first page of the structure
bytes32[][] memory structure = listOfLinkedList.getStructureAsArray(0, 10);
// Get paginated lists for each index
bytes32[] memory indexList = listOfIndex.getListAsArray(0, 10);
`
MultiPointedListOfLinkedList
This type is the most complex. In this type we have two ListOfLinkedList.
`shell
function _push(bytes32 index, bytes32 element)
function _remove(bytes32 index, bytes32 element)
`
In this type you can retrive which indexes contain a certain element.
Ex:
index 1 = 5->8->4->3
index 2 = 4->6->7->9
index 3 = 11->12->8->13
We can retrive which indexes have the element 8, the result will be 1->3.
This is possibile by accessing the `listOfSecondIndex`, more specifically `listOfSecondIndex.mapOfList(index).getListAsArray(page, pageSize)`.
Example:
`solidity
// Get all indexes containing a specific element (with pagination)
bytes32[] memory indexesWithElement = listOfSecondIndex.mapOfList(elementToFind).getListAsArray(0, 100);
`
Type Of List
There are three type of lists:
- CheapLinkedList
- LinkedList
- MapOfLinkedList
- ListOfLinkedList
- MultiPointedListOfLinkedList
CheapLinkedList have the essential `_push() _remove() isListed()`.
LinkedList have the `getListAsArray(uint256 page, uint256 pageSize)` and the `numberOfElement`.
MapOfLinkedList have the list organized by `index`.
Pagination
All methods that return arrays (like getListAsArray()) support pagination to handle large lists efficiently:
- page: Zero-indexed page number (0 = first page)
- pageSize: Number of elements to return per page
Example usage:
`solidity
// List has 250 elements
uint256 totalElements = linkedList.numberOfElement; // 250
// Get first 50 elements
bytes32[] memory page0 = linkedList.getListAsArray(0, 50); // Elements 0-49
// Get next 50 elements
bytes32[] memory page1 = linkedList.getListAsArray(1, 50); // Elements 50-99
// Get last 50 elements
bytes32[] memory page4 = linkedList.getListAsArray(4, 50); // Elements 200-249
`
Important notes:
- If page * pageSize >= totalElements, an empty array is returned
- If the last page has fewer elements than pageSize, only available elements are returned
- Use pagination to avoid gas limits when dealing with large linked lists
ListOfLinkedList can return the entire structure by using `getStructureAsArray()`. This because it store the indexes in a list.
In MultiPointedListOfLinkedList the index are also pointed by a list. In this way we have a list of indexes called `listOfSecondIndex`.
Functions that returns arrays use pagination! See the implementation for further details.
Class
With a class we intend a contract that can be easily declared as variabile into another contract.
We used the classes to create complex type of lists.
In case you need this type of structure, I suggest you to see the implementation.
Class access is reserved by using the ownable feature.
Tips
I personally suggest to use LinkedList or MapOfLinkedList, they can solve pretty much every problem. CheapLinkedList can be used if we only want to store the information on the blockchain, bu we need to have a good backend to hadle the information.
Example
`shell
contract Example is
UUPSUpgradeable,
MultiPointedListOfLinkedList
{
// the version of the sc
uint256 public version;
struct data
{
uint x;
bytes32 y;
address z;
}
data[] public storing;
function initialize() public initializer {
__MultiPointedListOfLinkedListClass_init();
// deleting the index 0 because it is not supported
storing.push(data(0, bytes32(0), address(0)));
}
// PUBLIC
function push(bytes32 index, uint x, bytes32 y, address z) public {
// 0x0 element is ko
bytes32 ref = bytes32(storing.length);
storing.push(data(x, y, z));
_push(index, ref);
}
function remove(bytes32 index, uint256 ref) public {
_remove(index, bytes32(ref));
}
function register(bytes32 index) external {
if (!listOfIndex.isListed(index))
_registerIndex(index);
if (!listOfSecondIndex.listOfIndex().isListed(index))
listOfSecondIndex.registerIndex(index);
}
function _authorizeUpgrade(
address newImplementation
) internal override {
version++;
}
}
``