immutability – Is there a better method to implement an immutable double ended queue, that uses two single link lists internally for the dequeue using C++?

I am writing an immutable interpreter in C++ for fun. Originally standard vectors and dequeues were used to create a double ended queue data type, but it was very slow, because each operation require a whole new copy of the original container to be created.

So it was redone using a custom immutable single linked node lists which only requires a single node to be recreated during each operation on list like data types. And a double ended queue was implemented using two of these single linked lists. While it doesn’t require the whole data type and each element to be copied during each operation. It does require a limited recreation of the data type during dequeue operations to rebalance the two lists, which is expensive.

Is there a more efficient, and less copy expensive method, that could have been used to implement the double ended queue? Which does not require rebalancing the lists, and the original data still remains immutable during each operation.

class list {

        let    _lead;
        let    _last;
        int_t  _size;

    public:

        list();
        list(const list& exp);
        list(let exp);
        virtual ~list();

        friend str_t           __type__(const list& self);
        friend bool_t            __is__(const list& self);
        friend real_t          __comp__(const list& self, const let& other);
        friend void             __str__(stream_t& out, const list& self);
        friend void            __repr__(stream_t& out, const list& self);

        friend int_t            __len__(const list& self);
        friend let             __lead__(const list& self);
        friend let             __last__(const list& self);
        friend let       __place_lead__(const list& self, const let& other);
        friend let       __shift_lead__(const list& self);
        friend let       __place_last__(const list& self, const let& other);
        friend let       __shift_last__(const list& self);
        friend let          __reverse__(const list& self);

    private:
        void  balance();
    };

    /********************************************************************************************/
    //
    //                               'list' Class Implimentation
    //
    /********************************************************************************************/

    list::list() : _lead(__node__()), _last(__node__()), _size(0) {
    }

    list::list(const list& exp) : _lead(exp._lead), _last(exp._last), _size(exp._size) {
    }

    list::list(let exp) : _lead(__node__()), _last(__node__()), _size(0) {
        
        while (exp.is()) {

            _lead = _lead.place_lead(pop_lead(exp));

            _size += 1;
        }

        balance();
    }

    list::~list() {
    }

    std::string __type__(const list& self) {
        return "list";
    }

    bool_t __is__(const list& self) {

        if (self._lead.is() || self._last.is()) {
            return true;
        }

        return false;
    }

    real_t __comp__(const list& self, const let& other) {

        const list* e = other.cast<list>();

        if (e) {

            if ((self._lead == e->_lead) && (self._last == e->_last)) {
                return 0.0;
            }
        }

        return NOT_A_NUMBER;
    }

    void __str__(stream_t& out, const list& self) {

        if (!__is__(self)) {
            out << "()";
            return;
        }

        out << "(";

        out << str(self._lead);

        if (self._last.is()) {

            if (self._lead.is()) {
                out << " ";
            }

            out << str(self._last.reverse());
        }

        out << ")";
    }

    void __repr__(stream_t& out, const list& self) {

        if (!__is__(self)) {
            out << "()";
            return;
        }

        out << "(";

        out << repr(self._lead);

        if (self._last.is()) {

            if (self._lead.is()) {
                out << " ";
            }

            out << repr(self._last.reverse());
        }

        out << ")";
    }

    int_t __len__(const list& self) {
        return self._size;
    }

    let __lead__(const list& self) {

        if (!self._lead.is()) {
            return self._last.lead();
        }

        return self._lead.lead();
    }

    let __last__(const list& self) {

        if (!self._last.is()) {
            return self._lead.lead();
        }

        return self._last.lead();
    }

    let __place_lead__(const list& self, const let& other) {

        if (other.is_nothing()) {
            return self;
        }

        list e = self;

        e._lead = e._lead.place_lead(other);

        e._size += 1;

        if (!e._last.is()) {
            e.balance();
        }

        return e;
    }

    let __shift_lead__(const list& self) {

        if (__len__(self) == 0) {
            return self;
        }

        list e = self;

        if (!e._lead.is()) {

            if (e._last.shift_lead().is()) {
                // Balance if _last has more than one element.
                e.balance();
            }
            else {
                e._last = e._last.shift_lead();
                return e;
            }
        }

        e._lead = e._lead.shift_lead();

        if (!e._lead.is()) {

            if (e._last.shift_lead().is()) {
                e.balance();
            }
        }

        return e;
    }

    let __place_last__(const list& self, const let& other) {

        if (other.is_nothing()) {
            return self;
        }

        list e = self;

        e._last = e._last.place_lead(other);

        e._size += 1;

        if (!e._lead.is()) {
            e.balance();
        }

        return e;
    }

    let __shift_last__(const list& self) {

        if (__len__(self) == 0) {
            return self;
        }

        list e = self;

        if (!e._last.is()) {

            if (e._lead.shift_lead().is()) {
                // Balance if _last has more than one element.
                e.balance();
            }
            else {
                e._lead = e._lead.shift_lead();
                return e;
            }
        }

        e._last = e._last.shift_lead();

        if (!e._last.is()) {

            if (e._lead.shift_lead().is()) {
                e.balance();
            }
        }

        return e;
    }

    let __reverse__(const list& self) {

        if (__len__(self) < 2) {
            return self;
        }

        list e;

        e._lead = self._last;
        e._last = self._lead;
        e._size = self._size;

        return e;
    }

    void list::balance() {

        // print("lead = " + str(_lead) + " : last = " + str(_last));

        bool_t flip = _last.is() && !_lead.is();

        if (flip) {
            std::swap(_lead, _last);
        }

        int_t i = _size < 2 ? 1 : _size / 2;

        _lead = _lead.reverse();
        _last = _last.reverse();

        while (i --> 0) {

            _last = _last.place_lead(_lead.lead());
            _lead = _lead.shift_lead();
        }

        _lead = _lead.reverse();
        _last = _last.reverse();

        if (flip) {
            std::swap(_lead, _last);
        }
    }
```