List order maintenance

Для такого списка команда [math]\mathrm{order(D,B)}[/math] выдаст [math]\mathrm{false}[/math].

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].

Алгоритм

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

См. также

• Список
• Персистентный стек

Источники информации

• — Лекция А.С. Станкевича
• — Wikipedia: order maintance problem