1

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

Improve this question
4
  • 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? Commented Apr 28, 2019 at 3:53
  • 4
    Possible duplicate of How to insert and element before another in a linked list Commented Apr 28, 2019 at 4:05
  • @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? Commented Apr 28, 2019 at 5:07
  • 1
    No that is not a valid dup link. It is talking about a custom linked list class. This question is about LinkedList. Commented Apr 28, 2019 at 6:04

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

6 Comments

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?
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.
@Cole Petersen, it is exactly what author proposed by himself.
@xja The answer has been updated with an example of how to do this with a LinkedList. Is this what you were looking for?
@Cole This new answer will still traverse the linked list twice. The following Stephen C's answer perfectly solves this problem.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.