Вставить элемент перед указанным элементом в связанном списке

Question

Как вставить элемент перед указанным элементом в связанном списке, чтобы сложность по времени составляла n.Например, я хочу вставить 100 до 7

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= 10; i++) {
    linkedList.add(i);
}

Я могу сделать это следующим образом

int index = linkedList.indexOf(7);
if (-1 != index) {
    linkedList.add(index, 100);
}

Но таким образом я дважды просмотрел связанный список.На самом деле мы можем сделать это, пройдя один раз.Так как я могу это сделать?
PS: просто используйте LinkedList

Answer 1

Существует способ сделать это за один проход , используя ListIterator. ListIterator похож на обычный Iterator, за исключением того, что вы можете изменить направление итерации, и вы можете add элемент в текущей позиции; см javadoc .

Итак, код выглядит примерно так:

    LinkedList<SomeType> list = ...
    SomeType a, b = ..

    // Insert 'b' before the first element equal to 'a' in 'list'
    ListIterator<SomeType> iterator = list.listIterator(0);
    while (iterator.hasNext()) {
        SomeType e = iterator.next();
        if (e.equals(a)) {
            iterator.previous();  // returns 'e' again.  But the real purpose
                                  // is to reset the iteration position
                                  // so that 'next()' would return 'e' again.
            iterator.add(b);      // inserts before 'next()'.
            break;
        }
    }

Операция ListIterator::add является «необязательной», но поддерживается LinkedList. LinkedList javadoc говорит, что приведенное выше не вызовет ConcurrentModificationException.

Answer 2

Как насчет этого:

LinkedList<Integer> linkedList = new LinkedList<>();
int addNumber = 100, beforeTheNumber = 7;
for(int i = 1; i <= 10; i++) {
    if(i == beforeTheNumber)
        linkedList.add(addNumber);
    linkedList.add(i);
}

Теперь элементы

linkedList должны выглядеть следующим образом: 1,2,3,4,5,6,100,7,8,9,10.

Редактировать: Если вы хотите вставить какое-либо значение в уже существующее LinkedList:

linkedList.add((linkedList.indexOf(beforeTheNumber) >= 0 ? linkedList.indexOf(beforeTheNumber) : linkedList.size()), addNumber);

Этот код предполагает, что:

1. linkedList существует и является LinkedList<Integer>.
2. beforeTheNumber и addNumber существуют и являются целыми числами.

Если linkedList не имеет beforeTheNumber, addNumber будет добавлено в конец.