LinkedList节点存储多对象时如何比较？基于myInt2优先级排序实现问题

第一步：实现节点比较逻辑 #

有两种可选方案，可根据实际场景选择：

方案1：让类本身实现Comparable接口 #

适合myInt2降序是该类默认排序规则的场景，直接修改原类即可：

class GroupOfFourInts implements Comparable<GroupOfFourInts>
{
   int myInt1;
   int myInt2;
   int myInt3;
   int myInt4;

   public GroupOfFourInts(int a, int b, int c, int d)
   {
     myInt1 = a; myInt2 = b; myInt3 = c; myInt4 = d;
   }

   @Override
   public int compareTo(GroupOfFourInts o) {
     // 按myInt2降序排序，返回正数说明当前对象优先级低于传入对象，负数则更高
     return o.myInt2 - this.myInt2;
   }
}

方案2：自定义Comparator比较器 #

如果不想修改原类，或者需要灵活切换排序规则，就用这种方式，单独定义比较器即可：

import java.util.Comparator;

public class GroupOfFourIntsMyInt2DescComparator implements Comparator<GroupOfFourInts> {
    @Override
    public int compare(GroupOfFourInts o1, GroupOfFourInts o2) {
        // 同样按myInt2降序排列
        return o2.myInt2 - o1.myInt2;
    }
}

第二步：基于LinkedList实现有序插入的优先队列 #

插入时遍历链表找到匹配位置插入即可，两种比较方案对应的插入实现如下：

对应Comparable方案的插入代码 #

import java.util.LinkedList;

public class MyPriorityQueue {
    private LinkedList<GroupOfFourInts> queue = new LinkedList<>();

    public void insert(GroupOfFourInts element) {
        // 空队列直接插入
        if (queue.isEmpty()) {
            queue.add(element);
            return;
        }
        // 遍历找到第一个优先级比当前元素低的位置，插入到它前面
        for (int i = 0; i < queue.size(); i++) {
            if (element.compareTo(queue.get(i)) < 0) {
                queue.add(i, element);
                return;
            }
        }
        // 所有元素优先级都比当前元素高，插入到末尾
        queue.addLast(element);
    }

    // 出队直接取队首（优先级最高的元素）
    public GroupOfFourInts poll() {
        return queue.pollFirst();
    }
}

对应Comparator方案的插入代码 #

import java.util.LinkedList;
import java.util.Comparator;

public class MyPriorityQueue {
    private LinkedList<GroupOfFourInts> queue = new LinkedList<>();
    private Comparator<GroupOfFourInts> comparator = new GroupOfFourIntsMyInt2DescComparator();

    public void insert(GroupOfFourInts element) {
        if (queue.isEmpty()) {
            queue.add(element);
            return;
        }
        for (int i = 0; i < queue.size(); i++) {
            if (comparator.compare(element, queue.get(i)) < 0) {
                queue.add(i, element);
                return;
            }
        }
        queue.addLast(element);
    }

    public GroupOfFourInts poll() {
        return queue.pollFirst();
    }
}

补充说明 #

如果没有强制要求必须基于LinkedList实现，Java标准库自带的PriorityQueue类本身就支持优先队列逻辑，传入自定义的Comparator即可直接使用，性能比自己基于LinkedList实现的更高：它内部基于堆结构实现，插入时间复杂度为O(logn)，而LinkedList遍历插入的时间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者potroast12