Return to Question

added 12 characters in body

Source Link

edited Mar 13, 2017 at 8:08

25.3k
7
58
141

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

}

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

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

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

}

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

Source Link

asked Mar 12, 2017 at 19:19

Philipp Doerner

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?

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

}

java linked-list