Insert an element before the specified element in the linked list

Question

How to insert an element before the specified element in the linked list, so that the time complexity is n. For example I want to insert 100 before 7

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

I can do it like this

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

But I have traversed the linked list twice by this way. Actually we can do this just by traversing one time. So how can I do that?
PS:just use LinkedList

• umop apisdn: Do you need it in complexity O(n), or must it strictly be a single iteration over the list? Also, are you free to implement your own linked list or must you use Java's implementation?
• YetAnotherBot: Possible duplicate of How to insert and element before another in a linked list
• xja: @umop apisdn Sorry, I didn't describe it clearly. I mean that I want to know how to do it under strictly a single iteration by just using Linkedlist in java. I know we can write an own class to do that. But as a typical linked list class ,can we just use linkedlist?
• Stephen C: No that is not a valid dup link. It is talking about a custom linked list class. This question is about LinkedList.

Answer 1

There is a way to do this in one pass using a ListIterator. A ListIterator is like a regular Iterator except that you can change the direction of iteration, and you can add an element at the current position; see javadoc.

So the code goes something like this:

 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;
 }
 }

The ListIterator::add operation is an "optional" operation, but it is supported by LinkedList. The LinkedList javadoc say that the above won't cause a ConcurrentModificationException.

Answer 2

How about this:

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's elments should now read: 1,2,3,4,5,6,100,7,8,9,10.

Edit: If you want to insert some value in an already existing LinkedList:

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

This code assumes that:

1. linkedList exists and is a LinkedList<Integer>.
2. beforeTheNumber and addNumber exist and are integers.

If linkedList does not have beforeTheNumber, addNumber will be added to the end instead.

• xja: Thanks your answer. By this way we can traverse just once. But if there is a given linkedlist, we need another list to copy to Implement insertion。So there isn't a simple way to insert an element like typical C linked list in Linkedlist?
• Cole Petersen: The java.util package has a number of types similar to LinkedList. Each one is used for different purposes and has a different set of methods. See the official Java tutorial for more information. For example, the ArrayList type has a method add(int i, E e) that lets you add an element e at index i. ArrayList also has a method called indexOf(Object o) which gets the index of the first occurrence of o.
• Dzmitry Alifer: @Cole Petersen, it is exactly what author proposed by himself.
• Cole Petersen: @xja The answer has been updated with an example of how to do this with a LinkedList. Is this what you were looking for?
• xja: @Cole This new answer will still traverse the linked list twice. The following Stephen C's answer perfectly solves this problem.