如何根据优先级将对象插入LinkedList

Question

我有一个“优先级”为1-3的int的对象，递增意味着优先级更高。

我有一个链表，其中有一种队列中的对象。基本上，我要做的是循环遍历LinkedList，并将新对象与列表中已有的对象进行比较，如果对象到达的对象的int优先级高于下一个对象，我希望将其插入到优先级较低的对象之前。

如果对象与其他对象具有相同的优先级，我希望将其插入到具有相同优先级的对象后面。如果对象找不到另一个优先级比它低的对象，我只想在末尾插入它。

这就是我现在拥有的

User s;
ListIterator <User> queue = getList().listIterator();
if (queue.hasNext()) {
    User next;
    while (queue.hasNext()) {
        next = queue.next();
        if (queue.hasNext() && next.getId() < s.getId()) {
            queue.add(next);
            queue.set(s);
        } else {
            queue.add(next);
        }
    }
}else {
  queue.add(s);
}

Answer 1

改用java.util.PriorityQueue。

为了满足必须按插入顺序删除同等优先级条目的要求，您需要提供一个基于优先级和时间戳的自定义比较器。如果无法修改条目对象以包含时间戳，则需要创建一个包装器来保存该条目的优先级、时间戳和引用。但是，它将确保具有相同优先级的后续条目在删除顺序中出现得较晚。

还要注意这样一个事实，即优先级队列的迭代器以随机顺序返回条目，而不是以优先级顺序进行迭代。只有删除才能保证按优先级顺序返回条目。（参见https://stackoverflow.com/a/8129239/18157解释原因）