Java LinkedList实现稀疏矩阵有序添加问题求助

我来帮你搞定这个稀疏矩阵的有序插入需求！你遇到的问题主要是没利用好元素的比较规则和LinkedList的ListIterator来精准找到插入位置。下面一步步给你实现方案：

第一步：让Node类支持排序比较 #

首先，给你的Node类实现Comparable<Node>接口，重写compareTo方法，这样就能明确两个节点的排序逻辑——先比行号，行号相同再比列号：

class Node implements Comparable<Node> {
    int row;
    int column;
    int data;

    public Node(int row, int column, int data) {
        this.row = row;
        this.column = column;
        this.data = data;
    }

    @Override
    public int compareTo(Node other) {
        // 行号不同时，行号小的排前面
        if (this.row != other.row) {
            return Integer.compare(this.row, other.row);
        }
        // 行号相同时，列号小的排前面
        return Integer.compare(this.column, other.column);
    }

    // 重写toString方便输出查看
    @Override
    public String toString() {
        return String.format("(%d,%d,%d)", row, column, data);
    }
}

第二步：实现有序插入的逻辑 #

接下来用LinkedList配合ListIterator来实现插入。普通Iterator只能遍历，而ListIterator支持在遍历过程中移动指针并插入元素，正好适合我们找位置的需求：

import java.util.LinkedList;
import java.util.ListIterator;

class SparseMatrix {
    private LinkedList<Node> nodeList = new LinkedList<>();

    public void addElement(Node newNode) {
        // 链表为空直接加
        if (nodeList.isEmpty()) {
            nodeList.add(newNode);
            return;
        }

        ListIterator<Node> iterator = nodeList.listIterator();
        while (iterator.hasNext()) {
            Node currentNode = iterator.next();
            int compareResult = newNode.compareTo(currentNode);
            
            if (compareResult < 0) {
                // 新节点比当前节点小，插在当前节点前面
                iterator.previous(); // 回退到当前节点的前一个位置
                iterator.add(newNode);
                return;
            } else if (compareResult == 0) {
                // 如果行和列都重复，这里选择覆盖数据（你也可以改成抛异常或忽略）
                currentNode.data = newNode.data;
                return;
            }
        }
        // 所有节点都比新节点小，直接加在末尾
        nodeList.add(newNode);
    }

    // 打印所有元素验证顺序
    public void printElements() {
        for (Node node : nodeList) {
            System.out.print(node + " ");
        }
        System.out.println();
    }
}

第三步：测试验证 #

写个main方法测试你给的例子：

public class Main {
    public static void main(String[] args) {
        SparseMatrix matrix = new SparseMatrix();
        matrix.addElement(new Node(1, 1, 3));
        matrix.addElement(new Node(2, 2, 4));
        matrix.addElement(new Node(1, 3, 5));
        
        matrix.printElements(); // 输出：(1,1,3) (1,3,5) (2,2,4)
    }
}

为什么之前用Iterator没成功？ #

普通的Iterator没有add方法，也不能回退指针，没法在遍历过程中精准插入到指定位置。而ListIterator解决了这个问题，再配合我们定义的compareTo规则，就能每次插入时都把元素放到正确的位置，保证链表始终有序。

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