How Do i Splice An Array in Solidity

Question

im new to solidity and im trying to figure out the best way to splice an array.

in javascript you have: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

is there a similar way to achieve this in solidity?

the only way i think it would be possible is if you overwrite the value at the array index and replace that value with the value of the item at the next index... then do this for every following index value until the end of the array.

that method sounds like it could be expensive. does anyone have an suggestions of how to better achieve this?

the main thing i am trying to achieve is a way to keep the order of the array even though you can remove items from the middle.

suggestion 1

so thinking about it, how about using a list of structs. for example given a list of strings we want in an array, how about the data be stored into a struct with an additional bool field deleted.

struct Queue {
    string value;
    bool deleted;
}

Queue[] public listOfItems;

function deleteItem(uint index) public {
    Queue[index].deleted = true;
}

given that read operations are free on ethereum, i can get the client to request data from some index, if the data at that index has been marked as deleted, automatically request the subsequent index until a record is found that isn't deleted.

solution 2

i could use linked lists to achieve a similar functionality. this way if an item is to be marked as deleted, i could update the key of the next item in the array.

uint counter;

mapping (uint => string) public comments;

function addComment(string newComment) public {
    comments[counter + 1](newComment);
    comments[counter].nextItem = counter + 1;
}

function removeCommentWithId(uint commentId) public {
    comments[commentId - 1].nextItem = commentId + 1;
}

Answer 1

You may want a linked list.

Removing an element and then shifting all the others over is the best way to deal with this using an array. (BTW, I'm pretty sure that's how JavaScript's splice works, too.) Using a linked list would allow you to efficiently remove an element.

That said, do you also need to insert elements and preserve sorted order? If so, how are you doing the insert? (That also sounds like an O(n) operation.) You could consider other data structures, like a heap or a balanced tree, or you could sort on-demand on the client. It all depends on what your scenario is.

EDIT

In response to the question edit, this is fine, but think about the expected ratio of deleted items to existing items. If, after much use, you have 10 items with 10,000 deleted items in between them, you'll find this is extremely inefficient. A linked list doesn't have this problem.

Also consider using exists = true instead of deleted = false. This may save gas depending on the expected use.

EDIT 2

A hastily-thrown-together doubly linked list implementation. Please test before using. :-)

pragma solidity ^0.4.21;

contract DoublyLinkedList {
    struct Node {
        bytes payload;
        uint256 next;
        uint256 prev;
    }

    uint256 nextNodeID = 1;  // 0 is a sentinel value.
    mapping(uint256 => Node) nodes;
    uint256 head;
    uint256 tail;
    uint256 count = 0;

    function append(bytes payload) public {
        if (tail == 0) {
            // 0 is a sentinel. tail == 0 means head == 0 and the list is empty.
            head = nextNodeID;
            tail = nextNodeID;
            nodes[nextNodeID].payload = payload;
        } else {
            nodes[tail].next = nextNodeID;
            nodes[nextNodeID].payload = payload;
            nodes[nextNodeID].prev = tail;
            tail = nextNodeID;
        }
        nextNodeID += 1;
        count += 1;
    }

    function validNode(uint256 nodeID) internal view returns (bool) {
        return nodeID == head || nodes[nodeID].prev != 0;
    }

    function remove(uint256 nodeID) public {
        require(validNode(nodeID));

        Node storage node = nodes[nodeID];

        // Update head and tail.
        if (tail == nodeID) {
            tail = nodes[nodeID].prev;
        }
        if (head == nodeID) {
            head = nodes[nodeID].next;
        }

        // Update previous node's next pointer.
        if (node.prev != 0) {
            nodes[node.prev].next = node.next;
        }

        // Update next node's previous pointer.
        if (node.next != 0) {
            nodes[node.next].prev = node.prev;
        }

        // Reclaim storage for the removed node.
        delete nodes[nodeID];

        count -= 1;
    }

    function getNodeIDs() public view returns (uint256[] ids) {
        ids = new uint256[](count);

        uint256 current = head;
        for (uint256 i = 0; i < count; i++) {
            ids[i] = current;
            current = nodes[current].next;
        }
    }

    function getPayload(uint256 nodeID) public view returns (bytes) {
        require(validNode(nodeID));

        return nodes[nodeID].payload;
    }
}

Answer 2

Don't do it.

Above all, avoid O(n) operations. Reconsider the need for a splice-like operation. If you think you need it, it's probably a sub-optimal application of blockchain.

Hope it helps.