Inserting into Sorted LinkedList Java

Question

I have this code below where I am inserting a new integer into a sorted LinkedList of ints but I do not think it is the "correct" way of doing things as I know there are singly linkedlist with pointer to the next value and doubly linkedlist with pointers to the next and previous value. I tried to use Nodes to implement the below case but Java is importing this import org.w3c.dom.Node (document object model) so got stuck.

Insertion Cases

1. Insert into Empty Array
2. If value to be inserted less than everything, insert in the beginning.
3. If value to be inserted greater than everything, insert in the last.

4. Could be in between if value less than/greater 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 might 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 insertion in the List in sorted manner without using Collections.sort(list)

Answer 2

You can do it in log (N) time Complexity simply. No need to iterate through all the values. you can use binary search to add value to sorted linked list.just add the value at the position of upper bound of that function. Check code... you may 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 about binary search more at : https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/