Учитывая указатель, удаление элемента из коллекции LinkedList - PullRequest
Новая
       77

Учитывая указатель, удаление элемента из коллекции LinkedList

0 голосов
/ 11 июня 2018

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

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

Но этот метод не соответствует моим требованиям.

Поскольку у меня есть указатель на объект, который я хочу удалить, я смогу удалить его за O(1) время, поскольку LinkedList - это двусвязный список. Есть ли другой способ сделать это без реализации моего LinkedList класса?

Ответы [ 3 ]

0 голосов
/ 11 июня 2018

Вы не можете удалить объект из LinkedList в O (1), если все, что у вас есть, это ссылка на сам объект.

Вы можете удалить объект, если удерживаете объект ListIterator<E> в положениина элемент, который вы хотели бы удалить, вызвав remove() на итераторе, но это не очень помогает, потому что ваш итератор будет признан недействительным в момент изменения списка.

Вот пример того, как сохранить удаление O (1).Поиск остается O (n), хотя: 

List<String> list = new LinkedList<>();
list.add("hello");
list.add("world");
list.add("one");
list.add("two");
list.add("three");
System.out.println(Arrays.toString(list.toArray()));
ListIterator<String> iter = list.listIterator();
String s;
while ((s = iter.next()) != null && !s.equals("world"))
    ;
// When it is time to delete
iter.remove();
System.out.println(Arrays.toString(list.toArray()));

Из-за ConcurrentModificationException написание собственной реализации LinkedList<E> и сохранение ссылки на узел для последующего удаления остается вашим лучшим вариантом с чисто связаннымиlists.

Другой вариант - использование LinkedHashSet<E>, которое предлагает предсказуемый порядок перечисления и O (1) удаления в обмен на использование дополнительной памяти.

0 голосов
/ 16 июня 2018

Хорошим решением моей проблемы было совместное использование List и HashSet.Так как мы используем HashSet, мы не можем работать с дубликатами.

Вставка: Вставка в оба List и HashSet.O(1) время.
Удаление: Удалить из HashSet, если существует.O(1) время.
Обход: Обход List.Доступ только в том случае, если HashSet содержит этот объект.

Обратите внимание, что я не пытаюсь повторить работу LinkedList здесь.Я просто делюсь тем, что сработало для меня.

0 голосов
/ 11 июня 2018

Как насчет: 

public void remove(Car searchedFor) {
  for (Iterator<Car> it = list.iterator(); it.hasNext(); ) {
    Car c = it.next;
      if (c == searchedFor) {
        it.remove();
      }
    }
  }
...