单链表实现高分榜自动移除最低分的remove()方法问题排查

存在的问题 #

• 数据结构混用冲突：需求要求用单链表实现，但代码同时维护了GameEntry[] games数组和head头节点两个独立存储结构，add、remove、display三个方法分别操作不同的结构，没有做数据同步，最终输出结果和需求完全不符。
• add方法逻辑错误：
  • 新增分数时，不管分数是否满足上榜条件，都先把节点插入到链表头部，不符合「只有分数足够高才进入榜单」的要求
  • 榜单满10条时，仅更新了数组的排序结果，没有同步删除链表中的最低分节点，也没有把排序后的顺序同步到链表，数组和链表的数据完全不一致
• remove方法逻辑错误：
  • 方法开头的games[i] = head是多余的错误逻辑，直接覆盖了数组中排序好的对应位置数据
  • 索引合法性校验写在数组修改操作之后，就算输入索引非法，数组也已经被错误修改，校验逻辑完全不生效
  • 仅删除了数组中的元素，没有同步删除单链表中的对应节点，链表数据依然错误
• display方法逻辑错误：仅遍历单链表输出内容，但你的排序逻辑全部写在数组中，输出的结果不是排序后的高分榜，只是插入顺序的倒序。

修正后可运行代码（纯数组实现，符合高分榜需求） #

public class ScoresSingleLL {
    private static class GameEntry{
        private int score;
        public GameEntry(int score) {
            this.score = score;
        }
        public int getScore() {
            return score;
        }
    }

    private static final int MAX_ENTRIES = 10;
    private int totalAdded = 0;
    private GameEntry[] games = new GameEntry[MAX_ENTRIES];

    public void add(GameEntry game) {
        int score = game.getScore();
        // 先判断分数是否够上榜
        if (totalAdded == MAX_ENTRIES) {
            if (score <= games[totalAdded - 1].getScore()) {
                return;
            }
        } else {
            totalAdded++;
        }
        // 找到插入位置，把比当前分数低的往后移
        int i = totalAdded - 1;
        for (; (i >= 1) && (score > games[i -1].getScore()); i--) {
            games[i] = games[i - 1];
        }
        games[i] = game;
    }

    public void remove(int i) throws IndexOutOfBoundsException {
        // 先做索引校验
        if ((i < 0) || (i >= totalAdded)) {
            throw new IndexOutOfBoundsException("Invalid index: " + i);
        }
        // 前移后面的元素
        for (int j = i; j < totalAdded -1; j++) {
            games[j] = games[j + 1];
        }
        games[totalAdded - 1] = null;
        totalAdded--;
    }

    public void display() {
        for (int k = 0; k < totalAdded; k++) {
            System.out.print("Game Entry [Score = "+ games[k].getScore() +"]" + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        GameEntry game1 = new GameEntry(1);
        GameEntry game2 = new GameEntry(2);
        GameEntry game3 = new GameEntry(3);
        GameEntry game4 = new GameEntry(4);
        GameEntry game5 = new GameEntry(5);
        GameEntry game6 = new GameEntry(6);
        GameEntry game7 = new GameEntry(7);
        GameEntry game8 = new GameEntry(8);
        GameEntry game9 = new GameEntry(9);
        GameEntry game10 = new GameEntry(10);
        GameEntry game11 = new GameEntry(11);

        ScoresSingleLL scores = new ScoresSingleLL();

        scores.add(game1);
        scores.add(game2);
        scores.add(game3);
        scores.add(game4);
        scores.add(game5);
        scores.add(game6);
        scores.add(game7);
        scores.add(game8);
        scores.add(game9);
        scores.add(game10);

        System.out.println("加入10个分数后的榜单：");
        scores.display();
        System.out.println("加入11分后的榜单：");
        scores.add(game11);
        scores.display();
        System.out.println("删除索引0位置后的榜单：");
        scores.remove(0);
        scores.display();
    }
}

如果需要纯单链表实现，只需要去掉数组，add时遍历链表找到对应插入位置，满10条时删除尾节点即可。

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