Converting a 2D Array into a 2D Linked List

Question

I'm currently still working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there.

The current exercise asks you to write a program that converts a sparse int matrix into a multi-linked-list with Nodes only for values that are not 0.

I wrote a program that writes a singly-linked-list of doubly-linked lists so as to use only one type of node, in which each node contains 2 references to other nodes and to get maximum use out of having 2 references per Node.

Basic code idea: Result of the code is a singly-linked-list of linked-list heads, in which each head is the first node of a doubly linked list. In these doubly-linked-lists the heads only use 1 pointer ("next") to point at the second Node. They use their other pointer "priorOrNext" to point at the next linked-list head, creating the singly-linked-list. Every Node in the doubly-linked-lists except the first one use their pointer "priorOrNext" to point at their previous Node and their second pointer "next" to point at the next Node.

First create a matrix "twoDmatrix" to convert, then create the 2D-list as described above with "head" as pseudonode pointing at the 2D-list, then print the matrix and the 2D-list respectively for checking purposes.

The code itself is provided below. My main questions are:

1. Should I have rather gone with using two different types of nodes to make the entire list either singly-linked or doubly-linked?

2. The code always uses a while-loop to find the first cell in a row of "twoDmatrix" that has a value != 0 and then, in a separate for-loop, checks the rest of the cells. I didn't like that solution, but it was the cleanest I could come up with. Improvements?

public class Aufgabe3_70 {
    static class Node {
        Node priorOrNext;
        Node next;
        int value;

        Node(Node pON, Node n, int v) {
            /*
             * For Nodes that make up heads of lists, priorOrNext will point at
             * the next head node of the list. For normal nodes of lists
             * priorOrNext will point at the previous node.
             */
            this.priorOrNext = pON;
            this.next = n;
            this.value = v;
        }

        public static void main(String[] args) {
            /*
             * Create a 2D array.Set even cells of even rows and uneven cells of
             * uneven rows to 1.
             */
            int[][] twoDmatrix = new int[7][7]; // matrix to convert
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    if (i % 2 == 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 1;
                    } else if (i % 2 == 0 && j % 2 != 0) {
                        twoDmatrix[i][j] = 0;
                    } else if (i % 2 != 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 0;
                    } else {
                        twoDmatrix[i][j] = 1;
                    }
                }
            }

            /*
             * Convert Matrix into a 2DLinkedList, a linked list of linked
             * lists. Between "head" and "tail" are the heads of the different
             * linked lists. Every head points at its next head with its
             * "priorOrNext" value. Between the individual head nodes and their
             * individual tail nodes (including the head tail nodes) are the
             * Nodes containing cells that had values != 0
             */
            Node head = new Node(null, null, 0);
            Node tail = head;
            for (int i = 0; i < twoDmatrix.length; i++) {
                /*
                 * Get first cell j of row i that has a value != 0. Avoid
                 * leaving the array with the j < twoDmatrix[i].length
                 * condition. If there is no cell with value != 0, skip this
                 * loop-iteration with the if-condition
                 */
                int j = 0;
                while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) {
                    j++;
                }
                if (j < twoDmatrix[i].length) {
                    /*
                     * The first cell in row i that has a value != 0 is the head
                     * of the list that will contain all Nodes of row i. cHead = 
                     *current head node, cTail = current tail node
                     */
                    Node cHead = new Node(null, null, twoDmatrix[i][j]);
                    Node cTail = cHead;

                    /*
                     * Connect and move along the overall tail of the 2DList
                     * (tail) to cHead.
                     */
                    tail.priorOrNext = cHead;
                    tail = tail.priorOrNext;

                    /*
                     * Make the doubly-linked-list of all other Nodes in row i,
                     * using cHead as head for it. Look for further Nodes at the
                     * cell after j (j++)
                     */
                    for (j++; j < twoDmatrix[i].length; j++) {
                        /*
                         * For all cells with value=!0 in row i, create new Node
                         * with its value. Point new Node at previous Node with
                         * "priorOrNext". Connect and move along the tail of
                         * this list (cTail) to the new Node
                         */
                        while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) {
                            j++;
                        }
                        if (j < twoDmatrix[i].length) {
                            cTail.next = new Node(cTail, null, twoDmatrix[i][j]);
                            cTail = cTail.next;
                        }
                    }
                }
            }

            /* Print out the matrix, followed by the 2D LinkedList */
            System.out.println("The 2D Matrix");
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    System.out.print(twoDmatrix[i][j] + " ");
                }
                System.out.println();
            }

            System.out.println();
            System.out.println("The 2D Linked List");

            /* Print out the values from the superList */
            for (Node cHead = head; cHead != null; cHead = cHead.priorOrNext) {
                for (Node cTail = cHead; cTail != null; cTail = cTail.next) {
                    System.out.print(cTail.value + " ");
                }
                System.out.println();
            }
        }
    }
}

Answer 1

Node

            /*
             * For Nodes that make up heads of lists, priorOrNext will point at
             * the next head node of the list. For normal nodes of lists
             * priorOrNext will point at the previous node.
             */
            this.priorOrNext = pON;

This is clever, but consider splitting this into two fields. E.g. prior and nextRow. A very small increase in memory costs and a much simpler interface. As a general rule, simple is preferable to clever in computer programming. It is easier to maintain in the long run.

If you had a nextRow, then it would also be easy enough to add a priorRow as well.

If you made Node generic, you could make head nodes of type Node<Node<Integer>>. Then you'd have two different kinds of Node without having to write two sets of code.

        int value;

You never actually need this here, as the entire linked list after head only has the value 1.

It's also more common to explicitly make object fields private rather than implicitly making them package private (the default).

main

Why put main in Node? You have an outer class, why not put main there? Then your inner Node class would be clean and reusable.

Consider moving some of the functionality that is currently in main into other methods, either on Node or the outer class. In particular, consider adding an add method on Node.

Consider

                while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) {
                    j++;
                }

Now make a method on the outer class.

    public static int findNext(int[] row, int j) {
        while (j < row.length && row[j] == 0) {
            j++;
        }

        return j;
    }

Which you can use like

    int j = findNext(twoDmatrix[i], 0);

and

    j = findNext(twoDmatrix[i], j + 1);

The second one allows you to change the enclosing for loop to a while loop.

Simplifying

            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    if (i % 2 == 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 1;
                    } else if (i % 2 == 0 && j % 2 != 0) {
                        twoDmatrix[i][j] = 0;
                    } else if (i % 2 != 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 0;
                    } else {
                        twoDmatrix[i][j] = 1;
                    }
                }
            }

You can simplify this to just

            for (int i = 0; i < twoDmatrix.length; i++) {
                int oddRemainder = i % 2;
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    twoDmatrix[i][j] = (oddRemainder == j % 2) ? 1 : 0;
                }
            }

This only calculates i % 2 once per value of i. Your compiler may already do this optimization.

It also simplifies the four cases of the original down to just two. Either the remainders are equal or not.

Or you could do something like

            int next = 1;
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    twoDmatrix[i][j] = next;
                    next = 1 - next;
                }

                next = 1 - twoDmatrix[i][0];
            }

The logic is different, but the result is the same.

This saves a comparison per iteration of the inner loop.

Functionality

The current exercise asks you to write a program that converts a sparse int matrix into a multi-linked-list with Nodes only for values that are not 0.

Does your code solve this problem? I would have thought that part of the problem space is that you would need to be able to go from the multi-linked list back to the sparse int array. But I don't see how to do that with your code. I.e. I think that a solution to this should include position as well as value.

It is of course quite possible that you are right in your interpretation and I am wrong. I just wanted to point out that yours isn't the only interpretation of the problem.