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

Question

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

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

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

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

Answer 1

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

У меня нет кода перед мной, но если память:

Возьмите копию Doug Lea «s отлично Concurrent Doubly LinkedList и:

1. Выставляют 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

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

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

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

Answer 3

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

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

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

Answer 4

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