Linked List 中的 Remove() 方法删除最低分数

Question

我希望GameEntry Score在添加到GameEntry后如果有高分则删除最低分。我设置的最大条目是 10。如果超过 10，它应该删除最低分数并替换索引。我尝试使用 remove() 方法在 main 中显示。这里我使用的是单链表。请帮助审查和反馈我 missed.Thanks.


public class ScoresSingleLL {

private GameEntry head; //head node to hold the list

    //It Contains a static inner class Game Entry
    private static class GameEntry{
        private int score;
        private GameEntry next;
        
        public GameEntry(int score) {
            this.score = score;
            this.next = null;
        }
        
        public int getScore() {
        return score;
        }

    }
    
    private static final int highestScoregames = 10;
    private int totalAdded = 0;
    private GameEntry[] games = new GameEntry[highestScoregames];
    
    
    public void add(GameEntry game) {
        game.next = head;
        head = game;
        int score = game.getScore();
        if (totalAdded == highestScoregames) {
        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 {

        GameEntry game = head;
        games[i] = game;
        
        if ((i < 0) || (i >= totalAdded)) { //i is score where less than total added score
        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() {

        GameEntry current = head;
        while(current != null){
            System.out.print("Game Entry [Score = "+ current.score +"]" + "  ");
            current = current.next;             
        }
        System.out.println("null");
    }


    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); 
        
        scores.display();   
        scores.add(game11);
        scores.remove(0);
        scores.display();
        

    }

}

Answer 1

您的代码将对象维护为链表和作为数组。这是矫枉过正。您的代码中有多个实例您没有保持同步。您应该只选择其中一种数据结构。

由于你的问题是关于链表的，我建议放弃数组。你也不需要 totalAdded.

这是两个函数的更正代码。 add 函数还将确保列表不会变得太长。发生这种情况时，它将在最后删除项目：

    private static final int highestScoregames = 10;
    
    public void add(GameEntry game) {
        if (highestScoregames == 0) { // Nothing allowed
             head = null;
             return;
        }
        if (head == null) {
            head = game;
            return;
        }
        int score = game.getScore();
        int count = 1;
        GameEntry current = head;
        if (score >= head.getScore()) {
            game.next = head;
            current = head = game;
        } else {
            while (current.next != null && current.next.getScore() > score) {
                current = current.next;
                count++;
            }
            // Insert game here
            game.next = current.next;
            current.next = game;
        }
        while (current.next != null && count < highestScoregames) {
            current = current.next;
            count++;
        }
        // Clip the rest of the list
        current.next = null;
    }
    
    public void remove(int i) throws IndexOutOfBoundsException {
        if (i < 0 || head == null) {
            throw new IndexOutOfBoundsException("Invalid index: " + i);
        } 
        if (i == 0) {
            head = head.next;
            return;
        }
        GameEntry game = head;
        for (int j = 1; j < i; j++) {
            game = game.next;
            if (game == null || game.next == null) {
                throw new IndexOutOfBoundsException("Invalid index: " + i);
            }
        }
        // Remove game.next
        game.next = game.next.next;
    }

Answer 2

下面的代码 - 在最后添加新的 GameEntry，直到总条目少于 10。删除给定索引处的 GameEntry。一旦总的 GameEntry 达到 10，下一个要添加的 GameEntry 将插入到现有的 GameEntry 中，得分最小。

public class ScoresSingleLL {
    private GameEntry head;
    private int size;

    private static class GameEntry {
        private int score;
        private GameEntry next;

        GameEntry(int score) {
            this.score = score;
        }

        @Override
        public String toString() {
            return "GameEntry{" +
                    "score=" + score +
                    '}';
        }
    }

    /**
     * 1. Adds new GameEntry
     * 2. If size exceeds 10 then replace GameEntry with min score with the new GameEntry
     */
    public void add(GameEntry gameEntry) {
        if(size == 10) {

            // 1. Find the GameEntry with min score  and its index
            // 2. Call remove(index) to remove GameEntry at index from #1
            // 3. Call add(gameEntry, index) to replace a new GameEntry at index from #1
            GameEntry current = head;
            int min = current.score;
            int index = 0;
            for(int i = 1; i < size; i++) {
                current = current.next;
                if(current.score < min) {
                    min = current.score;
                    index = i;
                }
            }

            remove(index);
            add(gameEntry, index);
            return;
        }

        // Adds new GameEntry by appending towards the end

        if(head == null) {
            head = gameEntry;
            head.next = null;

        } else {
            GameEntry current = head;
            while(current.next != null) {
                current = current.next;
            }
            current.next = gameEntry;
            gameEntry.next = null;
        }
        size++;
    }

    /**
     Called only when removing GameEntry with min score and replace it with new GameEntry
     */
    private void add(GameEntry gameEntry, int index) {
        if(index < 0) {
            throw new UnsupportedOperationException("Index : " + index);
        }
        if(index == 0) {
            gameEntry.next = head;
            head = gameEntry;
            size++;
            return;
        }

        GameEntry current = head;
        GameEntry previous = null;

        for(int i = 1; i <= index; i++) {
            previous = current;
            current = current.next;
        }

        previous.next = gameEntry;
        gameEntry.next = current;
        size++;
    }

    /**
     * Remove GameEntry at the given index
     */
    public void remove(int index) {
        if(size == 0 || index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("" + index);
        }

        if(index == 0) {
            head = head.next;
            size--;
            return;
        }

        GameEntry current = head;
        GameEntry previous = null;

        for(int i = 1; i <= index; i++) {
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
        size--;
    }

    /**
     * Print all present GameEntry
     */
    public void display() {
        if(head == null) {
            System.out.println("No GameEntry Present");
            return;
        }

        GameEntry current = head;
        while(current != null) {
            System.out.println(current);
            current = current.next;
        }
    }

    public static void main(String[] args) {

        ScoresSingleLL scoresList = new ScoresSingleLL();
        System.out.println("\n-------- GameEntry at the beginning --------");
        scoresList.display();

        System.out.println("\n-------- Adding 10 GameEntry --------");
        scoresList.add(new GameEntry(1));
        scoresList.add(new GameEntry(2));
        scoresList.add(new GameEntry(3));
        scoresList.add(new GameEntry(3));
        scoresList.add(new GameEntry(4));
        scoresList.add(new GameEntry(6));
        scoresList.add(new GameEntry(7));
        scoresList.add(new GameEntry(8));
        scoresList.add(new GameEntry(9));
        scoresList.add(new GameEntry(-2));
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(10) in place of min score = -2 --------");
        scoresList.add(new GameEntry(10));
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(11) in place of min score = 1 --------");
        scoresList.add(new GameEntry(11));
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(13) in place of min score = 2 --------");
        scoresList.add(new GameEntry(13));
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(14) in place of 1st occurrence of min score = 3 --------");
        scoresList.add(new GameEntry(14)); // Add in place of 1st occurrence of min = 3
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(5) in place of min score = 3 --------");
        scoresList.add(new GameEntry(5)); // Add in place of min = 3
        scoresList.display();

        System.out.println("\n-------- Remove GameEntry at 5th index i.e. score 6 --------");
        scoresList.remove(5); // Removes element at 5th index i.e. score 6
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(15) towards the end --------");
        scoresList.add(new GameEntry(15)); // Add new entry towards the end
        scoresList.display();

        System.out.println("\n-------- Add GameEntry(16) in place of min score = 4 --------");
        scoresList.add(new GameEntry(16)); // Add in place of min = 4
        scoresList.display();

        System.out.println("\n-------- Remove all GameEntry one by one --------");
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.remove(0);
        scoresList.display();
    }

}

输出

-------- GameEntry at the beginning --------
No GameEntry Present

-------- Adding 10 GameEntry --------
GameEntry{score=1}
GameEntry{score=2}
GameEntry{score=3}
GameEntry{score=3}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=-2}

-------- Add GameEntry(10) in place of min score = -2 --------
GameEntry{score=1}
GameEntry{score=2}
GameEntry{score=3}
GameEntry{score=3}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Add GameEntry(11) in place of min score = 1 --------
GameEntry{score=11}
GameEntry{score=2}
GameEntry{score=3}
GameEntry{score=3}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Add GameEntry(13) in place of min score = 2 --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=3}
GameEntry{score=3}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Add GameEntry(14) in place of 1st occurrence of min score = 3 --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=14}
GameEntry{score=3}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Add GameEntry(5) in place of min score = 3 --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=14}
GameEntry{score=5}
GameEntry{score=4}
GameEntry{score=6}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Remove GameEntry at 5th index i.e. score 6 --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=14}
GameEntry{score=5}
GameEntry{score=4}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}

-------- Add GameEntry(15) towards the end --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=14}
GameEntry{score=5}
GameEntry{score=4}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}
GameEntry{score=15}

-------- Add GameEntry(16) in place of min score = 4 --------
GameEntry{score=11}
GameEntry{score=13}
GameEntry{score=14}
GameEntry{score=5}
GameEntry{score=16}
GameEntry{score=7}
GameEntry{score=8}
GameEntry{score=9}
GameEntry{score=10}
GameEntry{score=15}

-------- Remove all GameEntry one by one --------
No GameEntry Present

Linked List 中的 Remove() 方法删除最低分数

Remove () method in Linked List to remove lowest score

java

linked-list