CODEWITHSUNDEEP
javalist
Karol Dowbecki
Karol Dowbecki

Reputation: 44980

Inserting elements into a LinkedList in ascending order

I'm trying to find an efficient way to insert Integer elements into a java.util.LinkedList list while always maintaining ascending order. For example:

5 -> []        => [5]
1 -> [5]       => [1, 5]
3 -> [1, 5]    => [1, 3, 5]
0 -> [1, 3, 5] => [0, 1, 3, 5]

This is purely theoretical problem to understand the impact of list traversal in linked data structure, see this presentation. I'm not interested in batch inserting Integer elements or sorting the LinkedList at the end.

I can use the ListIterator however it requires two method calls. I have to perform set() followed by add() like:

var numbers = new Integer[] { 5, 1, 3, 0, ... };
var list = new LinkedList<Integer>();
outer:
for (Integer num : numbers) {
  var it = list.listIterator();
  while (it.hasNext()) {
    var el = it.next();
    if (num <= el) {
      it.set(num);
      it.add(el);
      continue outer;
    }
  }
  it.add(num);
}

Is there a more efficient way to solve this?

Unless there is a different implementation of linked list data structure already in the JDK and it will be more suited for this task I'm not interested in swapping out java.util.LinkedList for something else.

Upvotes: 0

Views: 143

Answers (1)

Vaisakh K M
Vaisakh K M

Reputation: 255

Add method can take two inputs.

void add(int index, Object element)

https://www.geeksforgeeks.org/java-util-linkedlist-add-method-in-java/

Do binary search, find the position, use add method....

Upvotes: 1

Related Questions