LinkedList adding Java

Question

I have a node class that I made which has an int for row, column, and data. I am trying to make a sparse matrix. I want to sort them as I add them to be more efficient. I first need to sort by row, then by column if the row is the same. I have experimented with a few different ways but none of them are working. I am using the Java linkedList class as well as the Iterator. For example, if add elements (1,1,3), (2,2,4), and (1,3,5), when I print it out, it should be (1,1,3), (1,3,5), and (2,2,4).

This is my code so far:

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);
    }
}

Thank you for the help!!

Could you be more specific about your question? What about it doesn't work? Also, could you add your main method as well so that we can have the same inputs and be able to replicate your problem? — user9190555
– user9190555, Commented Feb 16, 2018 at 2:33

Michael Mogley · Accepted Answer · 2018-11-12 20:48:50Z

My solution implements a custom insert method, taking the element to insert, the List to insert to (any List implementation), and the Comparator to use. You probably should optimize the insert logic using a binary-search approach, but at least it's easy to understand. This assumes any elements in the passed-in List are already sorted.

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);
        }
    }
}

One more thing: unless you have an overriding reason to have them sorted as you add them to the list, I would really recommend you simply create the list with all the elements added to the tail. Then just call Collections.sort (list, cellComparator) which implements a merge-sort. This should in the end be more performant than sorting as you go, even with the binary search method.

Collectives™ on Stack Overflow

LinkedList adding Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related