solidity下的单链表实现

首先在开篇说明一下单链表在solidity中的优势和主要的使用场景。

想象一下如果需要从合约中获取一个排好序的列表数据，那么应该如何设计这个list的数据结构呢？
很容易想到的就是通过数组来实现，数据结构可以这样来定义：

    struct NodeData {
        string someData;
    }
    NodeData[] dataList;

但是这么设计的弊端在于，一次新数据的插入或删除可能带来巨大的数据量的改变。比如这个数组长度为100，那么通过检索发现，新的数据应该排在最前面，那么当把新的节点插入到数组0下标中的同时，还需要将原来的100个节点数据依次往后挪动。那么这次transaction就会造成巨大的gas消耗，不管是从代码效率和经济成本角度来看都非常不合算。
而将其用链表来实现的话就会经济和高效的多，每一次插入只是指针的改变而已。

说完了链表在solidity开发中的使用场景，接下来我们就来讲解具体的实现过程。

首先来定义节点和节点数据的struct：

    struct NodeData {           
        string someData;
    }
    struct Node {
        NodeData data;
        Node next;  //这里会报错
    }

上面那种类似C语言的定义方式是无效的，因为solidity中struct类型没法递归的引用自身，编译器会报错“ TypeError: Recursive struct definition.”：

image.png

那么我们用静态链表的方式，用数组的下标来作为指针，将节点数据存放到一个一维的动态数组中：

    struct HeadNode {
        uint256 listLength;
        uint256 spacePointer;   //备用链指针，指针如果为0，则备用链为空
        uint256 next;           //指向第一个节点的数组下标
    }
    struct NodeData {           //节点数据
        string someData;
    }
    struct Node {
        NodeData data;
        uint256 next;
    }
    struct List {
        HeadNode head;          //头结点
        Node[] nodes;
    }

这里我加入了一个头节点，用来存放节点的长度、头指针（指向链表的第一个元素的数组下标）和备用节点的指针。这里的备用链指的是当某个节点被删除之后，将nodes数组中与之对应的下标放入备用链作为备用。下一次插入节点的时候先从备用链中获取，避免每次新插入数据都扩展nodes数组的长度。

为了防止获取备用链指针时的错判，在列表初始化时需要将nodes数组的第一个元素（下标为0）用空数据填充起来，这样真实的数据节点的指针就不会为0。

    function initList(List storage self)
        internal
        returns(bool)
    {
        require(0 == self.nodes.length, 'no need to initialize');
        self.nodes.push(Node(NodeData(""), 0));
        return true;
    }

接下来定义链表的插入方法（完整代码见文末）：

 function insert(List storage self, uint256 index, NodeData memory data)
        internal
        returns(bool)
    {
        uint256 listLength = getListLength(self);
        require(index > 0 && index <= listLength + 1, 'invalid index.');    //最多只能往链表的末尾加一个节点

        //如果是一个空的list则需要先初始化它
        if (0 == self.nodes.length) {
            initList(self);
        }

        uint256 newNodePointer = popSpacePointer(self);  //获得空闲节点的下标
        if (0 == newNodePointer) {    //备用节点下标为0，需要扩展list的节点数组长度
            Node memory newInitNode = Node(data, 0);
            newNodePointer = self.nodes.push(newInitNode) - 1;    //返回新节点的数组下标
        } else {
            self.nodes[newNodePointer].data = data;
        }

        if (1 == index) {   //如果index == 1，则需要更改头指针指向新节点的数组下标
            self.nodes[newNodePointer].next = self.head.next;
            self.head.next = newNodePointer;
        } else {            //如果index大于1则更改前驱节点的指针和新节点的指针
            Node storage preNode = getNode(self, index - 1);
            self.nodes[newNodePointer].next = preNode.next;
            preNode.next = newNodePointer;
        }

        self.head.listLength++;     //list长度加1
        return true;
    }

在插入节点之前，我们得先判断index参数的有效性以及是否需要初始化nodes数组。接下来我们从备用链中拿出一个空闲节点出来：

    function popSpacePointer(List storage self)
        private
        returns(uint256)
    {
        uint256 spacePointer = self.head.spacePointer;  //找到空闲节点的下标
        if (spacePointer > 0) {
            self.head.spacePointer = self.nodes[spacePointer].next;  //已经拿出一个备用空闲下标，将其的下一个备用空闲下标拿出来做备用
        }
        return spacePointer;
    }

注意这面的代码实现，因为第一个空闲节点的指针已经被拿走使用了，那就需要把备用链的下一个节点指针往前移。

如果备用节点指针为0，则代表nodes长度不够用了，需要使用push方法扩展它，否则将新插入的节点数据放入备用节点指针所指向的下标中。

接下来就是判断数据插入的位置，如果是1，即新数据需要插入到列表首部，那么就需要更改头节点的next指针的指向，否则更改前驱节点和新节点的next指针。

最后将节点的长度加一，当然在头节点里面也可以不定义这个变量，但是每次获取链表长度都得把整个链表轮询一遍，效率就太低了，所以这里选择用空间换时间。

接下来是节点删除的方法：

    function del(List storage self, uint256 index)
        validIndex(self, index)
        internal
        returns(bool)
    {
        uint256 deleteNodePointer = getNodePointer(self, index);
        Node storage deleteNode = self.nodes[deleteNodePointer];
        uint256 listLength = getListLength(self);

        if (1 == listLength) {      //最后一个节点被删除的时候，将头节点next指针重置为0
            self.head.next = 0;
        } else {
            if (1 == index) {       //第一个节点被删除的时候，需要更改头节点的next指针
                self.head.next = deleteNode.next;
            } else {
                Node storage preNode = getNode(self, index - 1);
                preNode.next = deleteNode.next;
            }
        }

        //将待删除节点移到备用节点的最前端，并且将备用节点链接到待删除节点之后
        deleteNode.next = self.head.spacePointer;
        self.head.spacePointer = deleteNodePointer;

        self.head.listLength--;     //list长度减1
        return true;
    }

这里注意方法名不能使用delete，否则编译器会报错。

删除方法里面要注意的就是当所有节点都被删除完之后，和删除第一个节点的时候需要更改头节点的nex指针。
最后将当前删除的节点指针移到备用链上，然后将节点长度更新即可。

至此，单链表的基本实现逻辑就完成了，但是作为一个Library基础库，为了使用的方便，还得微调一下：

library Dataset {
    struct NodeData {           
        string someData;
    }
    function getInitNodeData()
        internal
        pure
        returns(NodeData memory)
    {
        return NodeData("");
    }
}

这里将节点数据的定义，单独从链表Library中分离出来，并定义了一个初始化数据节点数据的方法，然后在链表Library库中引用它们：

struct Node {
    Dataset.NodeData data;
    uint256 next;
}

    function initList(List storage self)
        internal
        returns(bool)
    {
        require(0 == self.nodes.length, 'no need to initialize');
        //填充数组下标为0的元素，防止获取备用链数组下标时错判
        self.nodes.push(Node(Dataset.getInitNodeData(), 0));
        return true;
    }

这样子，每次使用的时候，只需要自定义节点数据的struct结构即可。

至于双向链表的实现，只需要在此基础上加上一个前驱指针即可。

完整的代码在这里查看。

参考资料：
Solidity Library