插入Sorted LinkedList Java

Question

我在下面有这个代码,我将一个新的整数插入到一个有序的LinkedList中,但我不认为这是"正确"的做事方式,因为我知道有一个单独的链表,指针指向下一个值和双链表指向下一个和上一个值的指针.我试图使用Nodes来实现以下情况,但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);
            }
        }
    }
}

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

    }

}

这个方法将以排序的方式管理List中的插入而不使用 Collections.sort(list)