Ну...
Я бы запилил Блокировку на каждый отдельный элемент.
При досрочном удалении захватываем владение своего, предыдущего и последующего элементов,
Связываем предыдущий с последующим, снимаем блокировку с предылущего и последующего.
Снимаем блокировку со своего, удаляем свой элемент и завершаем воркера