插入到已排序的 LinkedList Java

Question

我在下面有这段代码，我将一个新整数插入到一个排序的整数链表中，但我认为这不是“正确”的做事方式，因为我知道有指向下一个值的指针的单链表和指向下一个值的双链表指向下一个和上一个值的指针。我尝试使用节点来实现以下情况，但 Java 正在导入此导入 org.w3c.dom.Node（文档对象模型），因此卡住了。

插入盒

1. 插入空数组
2. 如果要插入的值小于所有值，则在开头插入。
3. 如果要插入的值大于所有内容，则插入最后一个。
4. 如果值小于/大于 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;

   }

}

原文由 cloudviz 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

使用此代码：

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

    }

}

这种方法将以排序方式管理列表中的插入，而无需使用 Collections.sort(list)

原文由 Master 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果我们使用 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);
            }
        }
    }
}

原文由 Amruth 发布，翻译遵循 CC BY-SA 3.0 许可协议