List order maintenance

Для такого списка команда выдаст .

List order maintance — проблема поддержки списка со следующими командами:

[math]\mathrm{insert(p, q)}[/math] — вставка нового элемента [math]p[/math] в список сразу после [math]q[/math];
[math]\mathrm{remove(p)}[/math] — удаление элемента [math]p[/math] из списка;
[math]\mathrm{order(p, q)}[/math] — команда, возвращающая [math]\mathrm{true}[/math] , если [math]p[/math] в списке находится до [math]q[/math] и [math]\mathrm{false}[/math] иначе.

Существует реализация списка с командой порядка, где все операции выполняются за амортизационную [math]O(1)[/math].

Алгоритм

Эта структура данных может быть реализована как на односвязном, так и на двусвязном списке, рассмотрим первый случай.