Creating a stack in solidity via a linked list.

Share Dialog

Also, because linked lists are dynamic and memory is allocated dynamically according to our needs, we do not waste any memory compared to arrays—which waste memory unless they are full.

A stack is a data structure that contains a collection of items "stacked" on top of each other with two main operations: Push and Pop. Push adds another item onto the stack, and Pop removes the top item off the stack.

Think of a stack like a pile of plates. When you “Push”, you are adding a plate onto the stack, and when you “Pop”, you are taking that plate off.

Stacks can be used for many things! In lower level languages, there are no methods such as .reverse() that you can easily use on strings (solidity does not have .reverse!). Instead, to reverse a string, we can use stack and add each letter of the word sequentially. Afterwards, by popping each letter off the stack we reverse the word.

This is just one, small example. There are plenty more like: storing history (ctrl-z); recursion'; evaluating certain mathematical expressions (Shunting Yard Algorithm);

To create a stack, you can use a single linked-list, where every node has a pointer to the node “under” it.

First, we need to define a struct for a Node, it should contain a value and a next pointer to point to the next node.

When implementing a linked list, you usually use a memory address pointer when defining a node. For example in C++ you can define the Node as a pointer to another Node class instance!

Example of Node class in C++:

class Node {
    private:
        int data;
        Node * next;
    public:
        Node(int data) {
            this->data = data;
            this->next = NULL;
        }
        int getData() {
            return this->data;
        }
        Node * getNext() {
            return this->next;
        }
        void setNext(Node * next) {
            this->next = next;
        }

};

In solidity, it is not possible to do this in the same manner. This is because Solidity does not allow recursive structs:

    struct Node {
        uint256 value;
        Node next;
    }   

So instead of pointing to the memory address of the next node, our struct should contain a key in a mapping which points to the next node:

 struct Node {
        uint256 value;
        bytes32 next;
    }   

 mapping (bytes32 => Node) nodes;  

The ID for the next node should be something unique, for example taking the hash of the old top’s value, id, and the current block timestamp. By using the OldTop’s next-id, we can make sure that we won’t get overlapping keys within the same block:

keccak256(
        abi.encodePacked(
             OldTop.value,
             OldTop.next,
             block.timestamp
        )
);

Then, we take this ID and map it to the the old top node. Here is the main code for push:

 function push(uint256 value) public {
        Node memory node;
        node.value = value;

        if (Top.next == 0) {
            // code if the stack is empty
        }  else {
            Node storage OldTop = Top;
            node.next = keccak256(
                abi.encodePacked(
                    OldTop.value,
                    OldTop.next,
                    block.timestamp
                )
            );
            nodes[node.next] = OldTop;
            Top = node;
        }
    }

So, what is happening in this code block? Lets break it down.

First, we assigned the current Top value in the stack to OldTop. Then, we create an ID based off of the OldTop values and the current block timestamp.

Next, we assign this ID to the new Top node, and then we map this ID to the OldTop node in the mapping. After this, we assign the Top node to the new node that is being pushed to the stack.

This solidity implementation of a linked list works without a counter to count the number of nodes and to use as a key for in the mapping to other nodes in the list.

The way pop works is very simple:

    function pop() public returns (uint256) {
        require(Top.next != 0, "Stack is empty");
        
        Node storage oldTop = Top;
        uint256 oldValue = Top.value;

        Top = nodes[oldTop.next];
        return oldValue;
    }

If the stack is not empty, the ID for the top node is used to get the node under it, and then that node becomes the new top.

Also, it is usually a common practice to return the value of the node being popped off the stack, which is why we return the oldValue at the end.

That’s all folks! There are some other functions such as clear, peek, isEmpty, and size that are not as important to the core design so I chose not to go over them. If you want to see how they work head over to the repo!

https://github.com/d3or/ll-stack-solidity/blob/master/src/LinkedListStack.sol

This is my first ever article, if you have any feedback you can reach me on twitter

https://twitter.com/Deor

Also, because linked lists are dynamic and memory is allocated dynamically according to our needs, we do not waste any memory compared to arrays—which waste memory unless they are full.

A stack is a data structure that contains a collection of items "stacked" on top of each other with two main operations: Push and Pop. Push adds another item onto the stack, and Pop removes the top item off the stack.

Think of a stack like a pile of plates. When you “Push”, you are adding a plate onto the stack, and when you “Pop”, you are taking that plate off.

Stacks can be used for many things! In lower level languages, there are no methods such as .reverse() that you can easily use on strings (solidity does not have .reverse!). Instead, to reverse a string, we can use stack and add each letter of the word sequentially. Afterwards, by popping each letter off the stack we reverse the word.

This is just one, small example. There are plenty more like: storing history (ctrl-z); recursion'; evaluating certain mathematical expressions (Shunting Yard Algorithm);

To create a stack, you can use a single linked-list, where every node has a pointer to the node “under” it.

First, we need to define a struct for a Node, it should contain a value and a next pointer to point to the next node.

When implementing a linked list, you usually use a memory address pointer when defining a node. For example in C++ you can define the Node as a pointer to another Node class instance!

Example of Node class in C++:

class Node {
    private:
        int data;
        Node * next;
    public:
        Node(int data) {
            this->data = data;
            this->next = NULL;
        }
        int getData() {
            return this->data;
        }
        Node * getNext() {
            return this->next;
        }
        void setNext(Node * next) {
            this->next = next;
        }

};

In solidity, it is not possible to do this in the same manner. This is because Solidity does not allow recursive structs:

    struct Node {
        uint256 value;
        Node next;
    }   

So instead of pointing to the memory address of the next node, our struct should contain a key in a mapping which points to the next node:

 struct Node {
        uint256 value;
        bytes32 next;
    }   

 mapping (bytes32 => Node) nodes;  

The ID for the next node should be something unique, for example taking the hash of the old top’s value, id, and the current block timestamp. By using the OldTop’s next-id, we can make sure that we won’t get overlapping keys within the same block:

keccak256(
        abi.encodePacked(
             OldTop.value,
             OldTop.next,
             block.timestamp
        )
);

Then, we take this ID and map it to the the old top node. Here is the main code for push:

 function push(uint256 value) public {
        Node memory node;
        node.value = value;

        if (Top.next == 0) {
            // code if the stack is empty
        }  else {
            Node storage OldTop = Top;
            node.next = keccak256(
                abi.encodePacked(
                    OldTop.value,
                    OldTop.next,
                    block.timestamp
                )
            );
            nodes[node.next] = OldTop;
            Top = node;
        }
    }

So, what is happening in this code block? Lets break it down.

First, we assigned the current Top value in the stack to OldTop. Then, we create an ID based off of the OldTop values and the current block timestamp.

Next, we assign this ID to the new Top node, and then we map this ID to the OldTop node in the mapping. After this, we assign the Top node to the new node that is being pushed to the stack.

This solidity implementation of a linked list works without a counter to count the number of nodes and to use as a key for in the mapping to other nodes in the list.

The way pop works is very simple:

    function pop() public returns (uint256) {
        require(Top.next != 0, "Stack is empty");
        
        Node storage oldTop = Top;
        uint256 oldValue = Top.value;

        Top = nodes[oldTop.next];
        return oldValue;
    }

If the stack is not empty, the ID for the top node is used to get the node under it, and then that node becomes the new top.

Also, it is usually a common practice to return the value of the node being popped off the stack, which is why we return the oldValue at the end.

That’s all folks! There are some other functions such as clear, peek, isEmpty, and size that are not as important to the core design so I chose not to go over them. If you want to see how they work head over to the repo!

https://github.com/d3or/ll-stack-solidity/blob/master/src/LinkedListStack.sol

This is my first ever article, if you have any feedback you can reach me on twitter

https://twitter.com/Deor

<100 subscribers

<100 subscribers