Как разрешить объекту удалить себя из LinkedList в Java?

Question

Основной вопрос: Я ищу способ дать объекту в LinkedList ссылку на себя в списке, чтобы он мог (эффективно) удалить себя из указанного списка (без сортировки спискаищет себя. Я бы хотел, чтобы он просто вырезал себя из списка и связал вместе предыдущий и следующий элементы.).

Меньше необходимых деталей: Я сделал разумныйЯ не нашел ничего, кроме людей, советующих не использовать циклические ссылки.

Я хотел бы сделать это, когда я разрабатываю игру, и в игре объекты могут реализовывать различные интерфейсы, которые позволяют имбыть в различных списках, которые расположены по приоритетам.Один объект может находиться в цикле отрисовки, цикле, который пропускает его через кадры анимации, логическом цикле с высоким приоритетом и логическом цикле с низким приоритетом одновременно.Я хотел бы реализовать removeFrom | TypeOfLoop |метод в каждом соответствующем интерфейсе, чтобы, если объект решает, что он больше не должен находиться в цикле, он может непосредственно удалить себя.Это делает объекты, которые выполняют фактическое зацикливание, приятно простыми.

В качестве альтернативы, если нет способа сделать это, я думаю о реализации системы маркировки, где список проверяет, хочет ли каждый элемент бытьудалены на основе переменной в элементе.Однако мне не нравится идея сделать это достаточно, чтобы, возможно, просто создать свой собственный LinkedList, который можно удалить по ссылке.

Answer 1

Я сделал это недавно.Я искал O (1) добавить O (1) удалить без блокировки Collection.В конце концов я написал свой собственный Ring, потому что я хотел контейнер фиксированного размера, но вы можете найти метод, который я использовал для моей первой попытки значения.

У меня нет кода передо мной, но еслиПамять обслуживает:

Возьмите копию Превосходный Даг Ли Concurrent Doubly LinkedList и:

1. Expose the Node класс.Я использовал interface, но это зависит от вас.

2. Измените методы add, offer ..., чтобы они возвращали Node вместо boolean. Теперь это больше не Java Collection, но см. Мой комментарий позже.

3. Откройте метод delete класса Nodeили добавьте метод remove, который принимает Node.

Теперь вы можете удалять элементы из списка за O (1) раз, и это Lock Free .

Добавлено

Вот реализация метода remove(Node), взятая из его реализации Iterator.Обратите внимание, что вы должны продолжать пытаться, пока не добьетесь успеха.

public void remove(Node<E> n) {
  while (!n.delete() && !n.isDeleted())
    ;
}

Answer 2

Самый простой способ - изменить алгоритм, чтобы использовать Iterator для перебора объектов List и использовать метод Iterator.remove () для удаления текущего элемента.

Answer 3

Если вы используете LinkedList, нет более эффективного способа удалить элемент, чем выполнить итерацию по нему и выполнить iterator.remove (), когда вы найдете свой элемент.

Если вы используете коллекции Google или гуаву, вы можете сделать это в oneliner:

Iterables.removeIf(list.iterator(), Predicates.equalTo(this));

Answer 4

Я думаю, что ваша альтернатива намного лучше, чем позволить элементу удалить себя из цикла. Это уменьшает ответственность объектов в списке и позволяет избежать циклических ссылок.

Более того, вы можете использовать метод Guava Iterables.filter() и выполнять итерацию по отфильтрованному списку, а не проверять явно, должен ли объект отображаться или нет на каждой итерации.

Даже если бы то, что вы хотите сделать, было бы возможным, вы бы получили исключение ConcurrentModificationException при удалении объекта из списка при итерации по нему. Единственный способ сделать это - удалить текущий объект из итератора.