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

   }

Peraea

If all numbers are unique (no duplicates), you could use a TreeSet. – Combined

If you beforehand knew the maximum range range of numbers and the number of elements to be added you could create your own collection, as the index is easy to find. – Ordination

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)

Jainism

Thanks to all who responded. Great help. – Peraea

This should work but do not expect it to be fast with large lists as finding the insert point could lead to iterating through the whole list in the worst case. – Conation

Yes, It is based on the insertion sort. I might use Collections.sort() method from Java which uses either Quick Sort or Merge Sort on the basis of content. But here is what the learning of the person who has asked the question would be not that good. That is why I implemented it with Insertion Sort. Any one can use API; but I do not recommend until you do not know how the work is being done inside. – Jainism

Learning with this implementation is not ideal either. You use indexing into a linked list as if they are free operations. But both llist.get(i) and llist.add(i, val) have O(n) performance, so your whole algorithm has O(n log n + n) performance. Don't use indices with a linked list. – Seismic

@Jainism this is not efficient for larger size of LinkedList. Complexity of your code is O(N). This can be done in log( N) simply.Checkout my answer . – Witty

@ChristopheRoussy chekout my answer.. did it in log(N) – Witty

Answer 2

If we use listIterator the complexity for doing get 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);
            }
        }
    }
}

Reason

Thanks for this; it is clearly the better answer. How could this be cleaned up to avoid excessive return statements scattered throughout the loop? – Cusec

Wouldn't it be O(n)? – Landward

This is clear O(n), the addition itself is O(1) but finding the spot where to add it is at worst case O(n)... - so, no quick win here. Plus, unless you have some extra info on the ordering (e.g. bucket sort or so), at best you could have O(logN) to find the spot where to insert... O(1) is out of reach... – Moluccas

@Cusec see my simplified version based on this answer – Johst

Answer 3

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/

Witty

It's not O(log(N)) as list.get(i) is already O(N). I would say it is O(N*log(N)). – Lipsey

Answer 4

@Atrakeur

"sorting all the list each time you add a new element isn't efficient"

That's true, but if you need the list to always be in a sorted state, it is really the only option.

"The best way is to insert the element directly where it has to be (at his correct position). For this, you can loop all the positions to find where this number belong to"

This is exactly what the example code does.

"or use Collections.binarySearch to let this highly optimised search algorithm do this job for you"

Binary search is efficient, but only for random-access lists. So you could use an array list instead of a linked list, but then you have to deal with memory copies as the list grows. You're also going to consume more memory than you need if the capacity of the list is higher than the actual number of elements (which is pretty common).

So which data structure/approach to take is going to depend a lot on your storage and access requirements.

[edit] Actually, there is one problem with the sample code: it results in multiple scans of the list when looping.

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

The call to get(i) is going to traverse the list once to get to the ith position. Then the call to add(i, val) traverses it again. So this will be very slow.

A better approach would be to use a ListIterator to traverse the list and perform insertion. This interface defines an add() method that can be used to insert the element at the current position.

Chromium

Answer 5

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

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

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

Trillbee

Answer 6

You have to find where to insert the data by knowing the order criteria.

The simple method is to brute force search the insert position (go through the list, binary search...).

Another method, if you know the nature of your data, is to estimate an insertion position to cut down the number of checks. For example if you insert 'Zorro' and the list is alphabetically ordered you should start from the back of the list... or estimate where your letter may be (probably towards the end). This can also work for numbers if you know where they come from and how they are distributed. This is called interpolation search: http://en.wikipedia.org/wiki/Interpolation_search

Also think about batch insert: If you insert a lot of data quickly you may consider doing many insertions in one go and only sort once afterwards.

Conation

Answer 7

Linked list isn't the better implementation for a SortedList

Also, sorting all the list each time you add a new element isn't efficient. The best way is to insert the element directly where it has to be (at his correct position). For this, you can loop all the positions to find where this number belong to, then insert it, or use Collections.binarySearch to let this highly optimised search algorithm do this job for you.

BinarySearch return the index of the object if the object is found in the list (you can check for duplicates here if needed) or (-(insertion point) - 1) if the object isn't allready in the list (and insertion point is the index where the object need to be placed to maintains order)

Ware

Answer 8

Solution of Amruth, simplified:

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(itr.hasNext()) {
            if (itr.next().compareTo(element) > 0) {
                itr.previous();
                break;
            }
        }
        itr.add(element);
    }
}

Obviously it's O(n)

Johst

Answer 9

This is an implementation of @Atrakeur's suggestion, using binarySearch to insert into an ArrayList or similar, which is assumed to be correctly sorted before insertSorted is called.

public static <T extends Comparable<? super T>> boolean insertSorted(List<T> sortedList, T item) {
    return insertSorted(sortedList, item, Comparator.<T>naturalOrder());
}

/**
 * Assuming sortedList is correctly sorted according to comparator, this quickly
 * inserts item in the correct location to maintain sorting.
 * <p>
 * Duplicates are not added.
 *
 * @return true if sortedList did not already contain the specified element
 */
public static <T> boolean insertSorted(List<T> sortedList, T item, Comparator<? super T> comparator) {
    // binarySearch() returns the index of the search key, if it is contained in the list;
    // otherwise returns (-(insertion point) - 1).
    int search = Collections.binarySearch(sortedList, item, iComparator);
    if (search >= 0) {
        // Found.
        return false;
    } else {
        // Not found.
        int insertIndex = -1 * (search + 1);
        iSortedList.add(insertIndex, item);
        return true;
    }
}

Ablebodied