CODEWITHSUNDEEP
javalinked-listinsertion
Ahmad Ibrahem
Ahmad Ibrahem

Reputation: 117

Java: How to add (somewhere in the middle) multiple elements in a linked list?

adding an element to a linked list is known to be O(1).

However, adding it in position X is O(X) and if i want to add R elements in this position the total running time would be O(R*X).

but there must be an O(X+R) solution.

And the question is how to do the O(R+X) in java?

Upvotes: 2

Views: 1657

Answers (3)

Lie Ryan
Lie Ryan

Reputation: 64913

Assuming you're using java.util.LinkedList, there is the LinkedList.listIterator() method that returns a ListIterator:

public ListIterator listIterator(int index)

Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. [...]

The list-iterator is fail-fast: if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator's own remove or add methods, the list-iterator will throw a ConcurrentModificationException. [...]

And you can use ListIterator.add() to safely add an item in the middle of the LinkedList:

void add(E e)

Inserts the specified element into the list (optional operation). [...]

For example, say you want to put list2 in the 5th position of the list1, you can do so by doing the following:

LinkedList list1 = ...;
LinkedList list2 = ...;

ListIterator it1 = list1.listIterator(5);
for (Object item : list2) {
    it1.add(item);
}

Upvotes: 2

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340903

You have a list of pairs (element, X) where X is an index and element is the item you want to put under that index. Sort this list by X and add elements one after another using an Iterator. Here is an example:

Your input is: [(E1, 5), (E2, 3), (E3, 7)].

  1. Sort it by index: [(E2, 3), (E1, 5), (E3, 7)]

  2. Create an iterator and advance it by 3.

  3. Add E2 using an iterator.

  4. Advance the same iterator by 2 (5 - 3).

  5. Add E1.

  6. ...

Notice that this algorithm has an of-by-one bug. It should be relatively easy to fix it.

UPDATE: just noticed that your problem is much simpler. In your case just create an iterator, advance it X times and add elements one by one using that iterator.

Upvotes: 2

Mikko Maunu
Mikko Maunu

Reputation: 42114

Put elements to collection and then you can use addAll method to add them all.

Upvotes: 1

Related Questions