Java: Разница между двумя списками

Приложение для разведения кошек моей компании отслеживает колонну кошек. Периодически ему нужно сравнивать previousOrder с currentOrder (каждый из них является ArrayList ) и уведомлять обработчиков котов о любых изменениях.

Каждая кошка уникальна и может появляться в каждом списке только один раз (или не появляться вовсе). В большинстве случаев списки previousOrder и currentOrder имеют одинаковое содержимое в одном и том же порядке, но может произойти любое из следующего (от более частого к менее частому):

1. Порядок кошек полностью перемешан
2. Кошки по отдельности перемещаются вверх или вниз в списке
3. Новые кошки присоединяются в определенном месте в колонне
4. Кошки покидают колонну

Это выглядит как редактировать проблему расстояния мне. В идеале я ищу алгоритм, который определяет шаги, необходимые для сопоставления previousOrder currentOrder :

• MOVE Fluffy в позицию 12
• ] INSERT Snuggles в позиции 37
• DELETE Mr. Чаббс
• и т. Д.

Алгоритм также должен распознавать сценарий №1, и в этом случае новый приказ передается полностью.

Какой подход для этого лучше всего?

( This post и в сообщении возникают похожие вопросы, но они оба имеют дело со отсортированными списками. Мои упорядочены , но несортированы .)

РЕДАКТИРОВАТЬ

Алгоритм Левенштейна - отличное предложение, но меня беспокоит время / потребность в пространстве для создания матрицы. Моя главная цель - как можно быстрее определить и сообщить об изменениях. Что-то более быстрое, чем поиск дополнений и отправка сообщения типа «Вот новые кошки, а вот текущий порядок».