插入已排序的LinkedList Java

Question

我有下面的代码，我在一个整数排序的LinkedList中插入了一个新的整数，但我不认为这是“正确”的方法，因为我知道，有指向下一个值的单LinkedList和指向下一个和上一个值的双LinkedList。我试图使用节点来实现以下情况，但Java正在导入这个导入组织。w3c。多姆。节点（文档对象模型）因此卡住了。

插入盒

>

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

您可以在log（N）时间复杂度简单地做到这一点。您可以使用二进制搜索来添加值到排序链接list.just添加该函数上界位置的值。检查代码...你可能会更明白。

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

    }

输出：[4,5,6]

有关二进制搜索的更多信息，请访问：https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

Answer 2

这可能完全符合你的目的：

使用以下代码：

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

    }

}

这一方法将以排序方式管理列表中的插入，而不使用集合。排序（列表）

Answer 3

如果我们使用listIterator，那么执行get的复杂度将是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);
            }
        }
    }
}