How to optimize this smart contract function in Solidity about deleting an element in particular index of an array

Question

I used the following library code to delete an element in array according to its index. The only way in my mind is using loop, but it costs a lot of gas. Is there any other optimized code to solve this problem?

library ArrayLibrary {
    function remove(uint[] storage _arr, uint _removedIndex) public returns(uint[] memory){
        require(_arr.length > 0, "No element in Array.");
        for(uint i; i < _arr.length - 1; i++){
            if (i >= _removedIndex) {
                _arr[i] = _arr[i + 1];               
            } 
        }
        _arr.pop();
        return _arr;
    }
}


contract TestLibrary {
    uint[] arr;
    using ArrayLibrary for uint[];

    function deleteArrEle(uint[] calldata _arr, uint deletedIndex) public returns (uint[] memory deletedArr) {
        arr = _arr;
        deletedArr = arr.remove(deletedIndex);
    }
}

Answer 1

If you don't mind switching order of the items, you can copy the last item to the position of the unwanted item and then remove the last.

function remove(uint[] storage _arr, uint _removedIndex) public returns(uint[] memory){
    require(_arr.length > 0, "No element in Array.");
    _arr[_removedIndex] = _arr[_arr.length-1];
    _arr.pop();
    return _arr;
}

Input array [1,2,3,4], removing at index 1 (value 2). Output [1,4,3].

---

There is also a bit more complex workaround with linked sorted list. Example code in Liquity protocol's SortedTroves for example.

The sorted data is not stored in an array but in a mapping of structs that point to previous and next items.

• key A:
  • value 1
  • link to previous key: empty (meaning there's no previous value)
  • link to next key: D
• key C:
  • value 7
  • link to previous key: D
  • link to next key: empty (meaning there's no next key)
• key D:
  • value 5
  • link to previous key: A
  • link to next key: C

The contract also holds info about keys of lowest and highest value.

When you're removing an item, you only remove this specific item, and change the 2 links (next and previous) that originally pointed to this item.