Share this post on

Elevate Your Smart Contracts with Linked Lists

Smart contract developers are at the forefront of creating groundbreaking applications in the fast-evolving blockchain world.

A crucial part of this creation process is the choice of data structures, which form the backbone of smart contract coding in Solidity.

Linked Lists are a powerful tool, especially in web3 and DeFi spaces where data management and gas efficiency are paramount.

Unlike standard arrays and mappings, Linked Lists offer dynamicefficient solutions for managing data in smart contracts, showcasing the versatility and robustness of Solidity in tackling real-world blockchain challenges.

Existing Data Structures in Solidity

In Solidity, developers frequently use arrays and mappings. Let’s delve into each:

Arrays:

  • Order Preservation: Retains the order of elements.
  • Indexed Access: Direct access to elements using an index.
  • Size Immutability (in memory): Size needs to be known beforehand in memory.
  • Costly Operations: Expensive insertions and deletions due to shifting elements.

Example: Storing a list of token holders in a DeFi project. For instance, the order could be relevant for distributing rewards based on the order of joining.

Mappings:

  • Quick Access: Fast data access using unique keys.
  • No Size Limit: Can store an unlimited amount of data.
  • No Order Preservation: Elements have no particular order.
  • No Enumeration: Cannot iterate over elements or obtain a list of keys.

Example: Token contract balances can be efficiently managed using a mapping to retrieve address-specific balance information.

These structures are foundational in Solidity yet have limitations, paving the way for exploring other data structures like Linked Lists.

The Downsides of Arrays and Mappings in DeFi

Arrays are great for maintaining a list of stakeholders in a liquidity pool. When the size of the list expands, iterating through arrays can become costly, even leading to DoS attacks under extreme conditions.

Mappings, adept at quick data retrieval like fetching a user’s stake in a pool, stumble when you need to iterate over all stakeholders to update their rewards. This lack of enumeration and order can be a bottleneck in operations requiring a complete traverse through the data.

Linked Lists in Solidity

Linked Lists help when you have a lot of data that changes often. Unlike arrays, they make adding or removing data easy and cheap. Also, they keep the order of data, which mappings don’t do. This is useful when the order of transactions or user actions is important.

Practical Dive: Linked List Implementation

The following code demonstrates a simple implementation of a LinkedList contract in Solidity. The contract defines a struct Node representing each element and mapping nodes holding the list. It provides CRUD functions to (add, update, retrieve, and remove nodes). The head variable keeps track of the list’s start, making it a valuable structure for managing data dynamically.

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

/// @title A simple linked list implementation in Solidity
contract LinkedList {
    struct Node {
        uint256 data;
        address next;
    }

    mapping(address => Node) public nodes;
    address public head;

    constructor() {
        head = address(0);
    }

    /// @notice Adds a new node to the list
    /// @param _addr The address to be used as the node identifier
    /// @param _data The data to be stored in the node
    function addNode(address _addr, uint256 _data) public {
        require(nodes[_addr].next == address(0), "Node already exists");
        nodes[_addr] = Node({data: _data, next: head});
        head = _addr;
    }

    /// @notice Retrieves a node's data and the next node's address
    /// @param _addr The address of the node to retrieve
    /// @return The data and the next node's address
    function getNode(address _addr) public view returns (uint256, address) {
        Node memory node = nodes[_addr];
        return (node.data, node.next);
    }

    /// @notice Updates a node's data
    /// @param _addr The address of the node to update
    /// @param _newData The new data to be stored in the node
    function updateNodeData(address _addr, uint256 _newData) public {
        require(nodes[_addr].next != address(0) || head == _addr, "Node does not exist");
        nodes[_addr].data = _newData;
    }

    /// @notice Removes a node from the list
    /// @param _addr The address of the node to remove
    function removeNode(address _addr) public {
        require(nodes[_addr].next != address(0) || head == _addr, "Node does not exist");
        address iterator = head;
        address prev = address(0);
        while (iterator != _addr && iterator != address(0)) {
            prev = iterator;
            iterator = nodes[iterator].next;
        }
        if (prev == address(0)) {
            head = nodes[head].next; // Removing the head node
        } else {
            nodes[prev].next = nodes[iterator].next; // Removing a middle or tail node
        }
        delete nodes[_addr];
    }
}

A linked List like the one in the provided example contract can help manage a growing list of data. Unlike arrays, when a new lender joins or leaves, the Linked List easily updates without rearranging other items. This means adding or removing lenders can be more straightforward and predictable in gas usage, which is beneficial in a busy protocol.

Conclusion

Choosing the right data structure is key. While arrays and mappings are useful, their limitations in some DeFi scenarios become apparent. The LinkedList contract we explored opens up a path to managing data more efficiently in these cases. It’s a step towards building more flexible and cost-effective DeFi applications, showcasing the richness of smart contract development in Solidity.

Explore More:

Connect with me on:

Share this post on