俺は Rust 書けない C++ マンだけど、双方向リンクリストのサンプルコードを書いてみた。
Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
リストの要素数に関わらず insert, remove 操作を固定計算量で実行可能であればそれは O(1) です。

https://wandbox.org/permlink/AHWR4LIjkMCvWuZE

insert, remove 実装のコードだけここに貼ります。全てのコードは上記で確認願います。

--------------------------------
node *insert(node *target, int value) // ノードを target の直後へ挿入
{
　node *n = new node;
　n->value = value;
　n->prev = target;
　n->next = (target != nullptr) ? target->next : nullptr;

　if (n->prev != nullptr) n->prev->next = n;
　if (n->next != nullptr) n->next->prev = n;
　if (head == nullptr) head = n;
　if (tail == target) tail = n;

　return n;
}
void remove(node *n) // 指定ノードを削除
{
　if (n->next != nullptr) n->next->prev = n->prev;
　if (n->prev != nullptr) n->prev->next = n->next;
　delete n;
}