java - 插入到已排序的 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;
   
   }
   

Answer 1

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