Java: лучший способ найти и удалить элемент из связанного списка - PullRequest
Новая
       30

Java: лучший способ найти и удалить элемент из связанного списка

2 голосов
/ 12 мая 2019

Я довольно долго размышлял об этом и пока не нашел хорошего ответа на этот вопрос в SO.

Я хочу найти элемент в связанном списке и удалить его.это сразу.Если бы я сам создал связанный список, это было бы легко, поскольку я просто перебрал бы дважды связанный список: 

-> N1 <-> N2 <-> N3 <-> N4 <-> N5 <-

, а когда вы найдете, например, N3, вы измените указатели node.previous и node.next.такой что: 

-> N1 <-> N2 <-> N4 <-> N5 <-

Если элемент находится посередине, это потребует примерно n / 2 шагов.

Есть ли правильный подход для этого в java.util.LinkedList<Integer>?

Подход, который для меня недостаточен: 

Integer found = null;
for(Integer elem : list){
    if(hasCertainProperty(elem)){
        found = elem;
    } 
}
if(found != null){
    list.remove(found);
}

Если элемент является средним элементом в списке (двойной связанный список, поэтому выполняйте поиск с конца спискатеоретически возможно, если индекс известен), это потребовало бы максимум примерно n / 2 + n / 2 = n шагов.Принимая во внимание, что при самодельном прохождении потребуется только n / 2 шага.

Я знаю, что эти 2 и другие подходы в O (n), но вы знаете, иногда, что n / 2 имеет значение на практике.

Спасибо за вашу помощь.

1 Ответ

5 голосов
/ 12 мая 2019

Java 8 сделает это за вас. 

list.removeIf(x -> hasCertainProperty(x));

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

Кроме того, вы должны использовать ListIterator, который был специально создан для этой цели.Вы получаете его с помощью LinkedList # listIterator : 

ListIterator<Integer> listIter = list.listIterator(0);
while (listIter.hasNext()) {
    Integer element = listIter.next();

    if (hasCertainProperty(element)) {
        listIter.remove();
        break;
    }
}

Его remove не нуждается в поиске, поскольку он поддерживает указатель на узел во время итерации.Таким образом, у него есть руки на узле, который вы хотите удалить.

...