java - 添加 Java 的 LinkedList

Question

我有一个我制作的节点类，它有一个 int 表示行、列和数据。我正在尝试制作一个稀疏矩阵。我想在添加它们时对它们进行排序，以提高效率。我首先需要按行排序，如果行相同则按列排序。我尝试了几种不同的方法，但没有一个有效。我正在使用 Java linkedList 类以及 Iterator。例如，如果添加元素(1,1,3)，(2,2,4)和(1,3,5)，当我打印出来时，它应该是(1,1,3)，(1 、3、5)和(2、2、4)。

这是我到目前为止的代码:

public void addElement(int row, int col, int data) {
    if(matrix.size() == 0){
        Node new_node = new Node(row, col, data); 
        matrix.add(new_node);
        System.out.print("test \n");
    }
    Iterator<Node> iterator = matrix.iterator();
    Node temp = new Node();
    temp = iterator.next(); 
    int i = -1; // counter
    int size = matrix.size();
    int node_row  = temp.getRow();
    int node_col = temp.getColumn();
    System.out.print("iterator test \n");
    while(iterator.hasNext() || size == 1){
        System.out.print("test 5");
        while(row>node_row){
            i++;
            node_row++;
        }
        while(row == node_row && col>node_col){
            i++;
            node_col++;
        }
        break; 
    }
    if(i<=0){
        Node new_node = new Node(row, col, data); 
        matrix.add(0, new_node);
    }
    else{
    Node new_node = new Node(row, col, data); 
    matrix.add(i, new_node);
    }
}

感谢您的帮助!!

Answer 1

我的解决方案实现了一个自定义插入方法，获取要插入的元素、要插入的列表(任何列表实现)以及要使用的比较器。您可能应该使用二分搜索方法来优化插入逻辑，但至少它很容易理解。这假设传入的列表中的所有元素都已排序。

public class SortMatrixCells
{
    static class Cell<T>
    {
        private int column;
        private int row;
        private T value;

        Cell(int row, int column, T value)
        {
            this.row = row;
            this.column = column;
            this.value = value;
        }    

        public String toString()
        {
            return String.format("[%s,%s,%s]", row, column, value);
        }
    }

    private final static Comparator<Cell> cellComparator = new Comparator<Cell>() {

        @Override
        public int compare(Cell c1, Cell c2)
        {
            int result = 0;

            // Compare row values.
            if (c1.row < c2.row)
            {
                result = -1;
            }
            else if (c1.row > c2.row)
            {
                result = 1;
            }

            // If rows are equal, compare column values.
            else
            {
                if (c1.column < c2.column)
                {
                    result = -1;
                }
                else if (c1.column > c2.column)
                {
                    result = 1;
                }
            }

            return result;
        }
    };

    public static void main(String[] args)
    {
        List<Cell<Integer>> matrixCells = new ArrayList<>();

        insert(new Cell<Integer>(2, 2, 4), matrixCells, cellComparator);
        System.out.println("List so far: " + matrixCells);

        insert(new Cell<Integer>(1, 3, 5), matrixCells, cellComparator);
        System.out.println("List so far: " + matrixCells);

        insert(new Cell<Integer>(1, 1, 3), matrixCells, cellComparator);
        System.out.println("List so far: " + matrixCells);
    }

    private static <T> void insert(T elementToInsert, List<T> list, Comparator comparator)
    {
        boolean inserted = false;

        ListIterator<T> itrElements = list.listIterator();

        for (; itrElements.hasNext();)
        {
            int comparison = comparator.compare(elementToInsert, itrElements.next());

            switch (comparison)
            {
                case -1:
                case 0:
                    itrElements.previous();
                    itrElements.add(elementToInsert);
                    inserted = true;

                    break;
            }

            if (inserted)
            {
                break;
            }
        }

        if (!inserted)
        {
            itrElements.add(elementToInsert);
        }
    }
}

还有一件事:除非您有最重要的理由在将它们添加到列表时对它们进行排序，否则我真的建议您简单地创建列表，并将所有元素添加到尾部。然后只需调用实现合并排序的 Collections.sort (list, cellComparator) 即可。即使使用二分搜索方法，这最终也应该比直接排序更高效。