Insert into LinkedList Java sorted link

Question

I have this code below, where I insert a new integer into a sorted LinkedList from ints, but I don’t think that this is the “right” way to do things, because I know that there is a separate linked list with a pointer to the next value and twice linked a list with pointers to the next and previous value. I tried to use Nodes to implement the case below, but Java imports this import org.w3c.dom.Node (document object model), so I'm stuck.

Inserts>

• Paste into an empty array
• If the value is entered less than all, insert at the beginning.
• If the value you want to insert is larger than everything, paste in the last.

• May be between them if the value is less / more than certain values ​​in LL.

  import java.util.*; public class MainLinkedList { public static void main(String[] args) { LinkedList<Integer> llist = new LinkedList<Integer>(); llist.add(10); llist.add(30); llist.add(50); llist.add(60); llist.add(90); llist.add(1000); System.out.println("Old LinkedList " + llist); //WHat if you want to insert 70 in a sorted LinkedList LinkedList<Integer> newllist = insertSortedLL(llist, 70); System.out.println("New LinkedList " + newllist); } public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){ llist.add(value); Collections.sort(llist); return llist; } 

  }

Answer 1

This can serve your purpose perfectly:

Use this code:

 import java.util.*; public class MainLinkedList { private static LinkedList<Integer> llist; public static void main(String[] args) { llist = new LinkedList<Integer>(); addValue(60); addValue(30); addValue(10); addValue(-5); addValue(1000); addValue(50); addValue(60); addValue(90); addValue(1000); addValue(0); addValue(100); addValue(-1000); System.out.println("Linked List is: " + llist); } private static void addValue(int val) { if (llist.size() == 0) { llist.add(val); } else if (llist.get(0) > val) { llist.add(0, val); } else if (llist.get(llist.size() - 1) < val) { llist.add(llist.size(), val); } else { int i = 0; while (llist.get(i) < val) { i++; } llist.add(i, val); } } } 

This one method will manage the attachment in the list in a sorted way, without using Collections.sort(list)

Answer 2

If we use listIterator, the get execution complexity will be O (1).

 public class OrderedList<T extends Comparable<T>> extends LinkedList<T> { private static final long serialVersionUID = 1L; public boolean orderedAdd(T element) { ListIterator<T> itr = listIterator(); while(true) { if (itr.hasNext() == false) { itr.add(element); return(true); } T elementInList = itr.next(); if (elementInList.compareTo(element) > 0) { itr.previous(); itr.add(element); System.out.println("Adding"); return(true); } } } } 

Answer 3

@Atrakeur

"sorting the entire list each time a new item is added is ineffective"

This is true, but if you want the list to always be in sorted state, this is really the only option.

"The best way is to insert the element directly where it should be (in its correct position). To do this, you can encode all the positions to find where this number belongs."

This is exactly what the sample code does.

"or use Collections.binarySearch so that this optimized search algorithm does the job for you"

Binary search is effective, but only for random access lists. That way you can use a list of arrays instead of a linked list, but then you have to deal with copies of memory as the list grows. You will also consume more memory than you need if the capacity of the list is higher than the actual number of elements (which is quite common).

So, what data structure / approach will greatly depend on your storage and access requirements.

[edit] In fact, there is one problem with the sample code: this leads to multiple scrolling through the list.

 int i = 0; while (llist.get(i) < val) { i++; } llist.add(i, val); 

The get (i) call will go through once to go to the i-th position. Then the call to add (i, val) crosses it again. So it will be very slow.

A better approach would be to use ListIterator to move around the list and perform the insertion. This interface defines the add () method, which you can use to insert an element at its current position.

Answer 4

Take a look at com.google.common.collect.TreeMultiset .

This is actually a sorted set that allows multiple instances of the same value.

This is a good compromise for what you are trying to do. Insertion is cheaper than ArrayList, but you still get the benefits of binary / tree search.

Answer 5

You must find where to insert the data, knowing the order criteria.

A simple method is to search for brute force at the insertion position (go to list, binary search ...).

Another method, if you know the nature of your data, is to evaluate the insertion position in order to reduce the number of checks. For example, if you insert "Zorro" and the list is ordered alphabetically, you should start at the back of the list ... or evaluate where your letter may be (possibly towards the end). This can also work for numbers if you know where they came from and how they spread. This is called interpolation search: http://en.wikipedia.org/wiki/Interpolation_search

Also think about batch insertion: If you quickly insert a lot of data, you might consider making many inserts at a time and sorting only once after that.

Answer 6

A linked list is not the best implementation for a SortedList

In addition, sorting the entire list each time a new item is added is inefficient. The best way is to insert the element directly where it should be (in its correct position). To do this, you can loop all the positions to find where this number is, then insert it or use Collections.binarySearch so that this optimized search algorithm does the job for you.

BinarySearch returns the index of the object if the object is in the list (if necessary, you can check for duplicates here) or (- (insertion point) - 1) if the object has not already been installed in the list (and the insertion point is the index where the object should be posted to maintain order)

Answer 7

You can do this in log (N) mode simply. No need to iterate over all values. you can use binary search to add value to a sorted linked list. Just add a value to the position of the top border of this function. Check the code ... you can understand better.

  public static int ubound(LinkedList<Integer> ln, int x) { int l = 0; int h = ln.size(); while (l < h) { int mid = (l + h) / 2; if (ln.get(mid) <= x) l = mid + 1; else h = mid; } return l; } public void solve() { LinkedList<Integer> ln = new LinkedList<>(); ln.add(4); ln.add(6); ln.add(ubound(ln, 5), 5); out.println(ln); } 

Output: [4, 5, 6]

you can learn more about binary search: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/