将新项目插入升序链表中

Question

下面是我对ASC链表的插入方法的实现，该方法根据对象的优先级将PQueueItem对象插入到类型为PQueueItem的链表中。

根据优先级，我基本上会检查要插入的项目是否大于当前项目，小于下一个项目，如果是，则插入它。如果等于下一个，则按字母顺序排列。如果它小于当前项，则将其放在它之前。如果它大于当前项和下一项，则遍历列表，直到它满足其他检查之一。

这是一种合适/有效的插入方式吗？如果你认为我的想法是两者都有，那么非代码的想法就太棒了：

1. 不正确
2. 效率低下

干杯！

public void insert(T data, int priority) {
        if(order == ORDER.ASC)
        {
            //current item
            PQueueItem<T> temp = head;
            while(temp.getNext() != null)
            {
                //is inserted item greater than current item
                if(priority > temp.getPriority())
                {
                    //is inserted item smaller than next item
                    if(priority < temp.getNext().getPriority())
                    {
                         //create and insert new item, reassign links in the list
                         PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                         newPQ.setNext(temp.getNext());
                         temp.setNext(newPQ);
                    }
                    //check to see if priority equates to the next item's priority
                    else if(priority == temp.getNext().getPriority())
                    {
                        //is new item's data alphabetically greater than the next item's data
                        if(((String)data).compareToIgnoreCase((String)temp.getNext().getData()) > 0)
                        {
                             PQueueItem<T> nextPQ = temp.getNext();
                             PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                             newPQ.setNext(nextPQ.getNext());
                             nextPQ.setNext(newPQ);
                        }
                        else
                        {
                            PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                            newPQ.setNext(temp.getNext());
                            temp.setNext(newPQ);
                        }
                    }
                    else
                    {
                        //iterate current item
                        temp = head.getNext();
                    }
                } 
                //if item to be inserted is smaller than the current item
                else if(priority < temp.getPriority())
                {
                     PQueueItem<T> newPQ = new PQueueItem<T>(temp.getData(), temp.getPriority());
                     newPQ.setNext(temp.getNext());
                     temp.setData(data);
                     temp.setPriority(priority);
                }
            }
        }   
        else
        {
            //code for DESC             
        }
    }

Answer 1

吸引眼球的是：

• 存在一个伪头节点

首先，一种比较方法产生了意义：

private int compare(T data, int priority, PQueueItem<T> pq) {
    return -1 or 0 or 1;
}

然后在没有头部虚拟节点的情况下：

    PQueueItem<T> prior = null;
    PQueueItem<T> current = head;
    // Walk to the insertion point:
    while (current != null) {
        int comparison = compare(data, priority, current);
        if (comparison >= 0) {
            if (comparison == 0) {
                return; // No insert?
            }
            break;
        }
        prior = current;
        current = current.getNext();
    }
    // Create the link:
    PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
    newPQ.setNext(current);
    if (prior == null) {
        head = newPQ;
    } else {
        prior.setNext(newPQ);
    }

Answer 2

已经有一段时间了，但有一种类似对数搜索的方法，它可以大大提高您的实现速度（您现在的实现速度与列表的大小成线性比例，对数比例与列表的规模成对数比例（为了理解它的含义，在1000000000个元素上，log（1000000000）粗略地是20，非常小）。

算法：你从整个列表开始，然后把它切成两半。要插入的元素正好发生在这两半中的一个中。你选对了，也把它切成两半。您可以继续这样做，直到您查看的列表部分最多有2个元素。然后您就知道将元素插入到哪里了。实现通常是两个包含索引的变量，在每次迭代中，将其中一个变量移动到您当前所看到的一半

每一步都会暂停你要处理的元素，这意味着你最终会在最对数复杂的时间插入你的值。

此外，不要指望有更好的解决方案，对数是很难击败的。如果你想要"即时"插入，你需要一个不同的结构。