Converting a 2D Array into a 2D Linked List

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:

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

-
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 w

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>. 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.

StackExchange Code Review Q#157583, answer score: 3