deor

Solidity Stacks & Linked Lists

Ok, cool. Now what are all these words. A stack? A linked list? Solidity?

Lets start off with going over linked lists.

If you are already familiar with linked lists and stacks, you can skip these parts and go to the end where the solidity code is discussed.

What is a linked list?

A linked list is a data structure that is made up of nodes. Every node contains two things: data, and a pointer to the next node in the list. In this scenario, we are using a single linked list, which is a linked list that only points to the next node.

There are other types of inked lists, such a doubly linked lists, where each node points to the node in front of it and behind it.

Image alt

Why not just use an array?

Linked lists have several advantages over traditional arrays.

For example, when inserting an element at a position in an array, you normally need to shift over all of the elements to the right. On the other hand, to insert data into a linked list you just need to change two pointers: the pointer for the node at Y-1; and the pointer for the current node to point to the node at Y+1.

Image alt

Deletion works similarly.

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.

What is a stack?

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.

Image alt

How are stacks useful?

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);

Coming together

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

Image alt

Solidity Implementation

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!

ll-stack-solidity repository

Back