javadata-structurescollectionslinked-list

Inserting into Sorted LinkedList Java


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;
    
    }
    

    }


Solution

  • 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)