Source of LinkedNodeRecursion.java


  1: //LinkedNodeRecursion.java
  2: //Illustrates recursion applied to a sequence of linked nodes.
  3: //We use recursion to build a sequence of linked nodes containing
  4: //integer values, to display those values in order, to display
  5: //the values in reverse order, and to reverse the actual order
  6: //of the nodes themselves. We also give an iterative version of
  7: //a method to reverse the actual order of the nodes.

  9: /*  Note:
 10:     To read in a number of integer values on the same line, we read
 11:     the entire line as a string, create a Scanner for the line, and
 12:     then use that Scanner to read the integers from the string.
 13: */

 15: import java.util.Scanner;

 17: public class LinkedNodeRecursion
 18: {
 19:     private static Scanner keyboard = new Scanner(System.in);
 20:     private static Scanner lineScanner;
 21:     private static Node head; //A reference to the first Node of the sequence

 23:     public static void main(String[] args)
 24:     {
 25:         System.out.println
 26:         (
 27:             "\nThis program illustrates recursion in "
 28:             + "the context of a sequence of linked\nnodes. It uses four "
 29:             + "recursive functions to perform the following actions."
 30:             + "\nThe program reads in a line of integers, and places "
 31:             + "them into a sequence of \nlinked nodes. Next it displays "
 32:             + "the contents of that sequence of linked nodes,\nfirst in "
 33:             + "their input order, and then in the reverse of that order. "
 34:             + "Then it\nreverses the contents of the nodes, and repeats "
 35:             + "the above two displays."
 36:         );
 37:         LinkedNodeRecursion tester = new LinkedNodeRecursion();
 38:         tester.runTests();
 39:     }

 41:     private void runTests()
 42:     {
 43:         System.out.println
 44:         (
 45:             "\nBegin by entering data values for the nodes "
 46:             + "on the following line:"
 47:         );
 48:         String line = keyboard.nextLine();
 49:         lineScanner = new Scanner(line);

 51:         buildNodeSequenceFromKeyboard();

 53:         System.out.println
 54:         (
 55:             "\nHere, from the linked nodes, are the "
 56:             + "values read in:"
 57:         );
 58:         displaySequenceValues(head);
 59:         System.out.print("\nPress Enter to continue ... ");
 60:         keyboard.nextLine();

 62:         System.out.println
 63:         (
 64:             "\nHere, again from the linked nodes, are the "
 65:             + "values in reverse order:"
 66:         );
 67:         displaySequenceValuesInReverse(head);
 68:         System.out.print("\nPress Enter to continue ... ");
 69:         keyboard.nextLine();
 70:         
 71:         System.out.println
 72:         (
 73:             "\nNext we reverse the order of the actual "
 74:             + "nodes themselves."
 75:         );
 76:         head = reversedSequenceRecursively(head);
 77:         //head = reversedSequenceIteratively(head);
 78:         System.out.print("\nPress Enter to continue ... ");
 79:         keyboard.nextLine();

 81:         System.out.println
 82:         (
 83:             "\nThen we first display them in their new  "
 84:             + "(reversed) order. Here they are:"
 85:         );
 86:         displaySequenceValues(head);
 87:         System.out.print("\nPress Enter to continue ... ");
 88:         keyboard.nextLine();

 90:         System.out.println
 91:         (
 92:             "\nFinally, we display the revised sequence in reverse order,"
 93:             + "\nwhich will be the original order of the values. "
 94:             + "Here they are:"
 95:         );
 96:         displaySequenceValuesInReverse(head);
 97:         System.out.print("\nPress Enter to continue ... ");
 98:         keyboard.nextLine();
 99:     }

101:     //Build sequence of linked nodes with values read from keyboard
102:     private void buildNodeSequenceFromKeyboard()
103:     {
104:         if (lineScanner.hasNextInt())
105:         {
106:             int value = lineScanner.nextInt();
107:             buildNodeSequenceFromKeyboard();
108:             head = new Node(value, head);
109:         }
110:         else
111:         {
112:             head = null;
113:         }
114:     }

116:     private void displaySequenceValues(Node head)
117:     {
118:         if (head != null)
119:         {
120:             System.out.print(head.data + " ");
121:             displaySequenceValues(head.next);
122:         }
123:     }

125:     private void displaySequenceValuesInReverse(Node head)
126:     {
127:         if (head != null)
128:         {
129:             displaySequenceValuesInReverse(head.next);
130:             System.out.print(head.data + " ");
131:         }
132:     }

134:     private Node reversedSequenceRecursively(Node head)
135:     {
136:         if (head == null)
137:             return null; //since the sequence is empty
138:         if (head.next == null)
139:             return head; //since the sequence has only one Node

141:         //Reverse the order of all nodes but the first, and
142:         //then make the former first Node the last Node
143:         Node rest = head.next;
144:         rest = reversedSequenceRecursively(rest);
145:         head.next.next = head;
146:         head.next = null;

148:         return rest;
149:     }

151:     private Node reversedSequenceIteratively(Node head)
152:     {
153:         Node reversedSequence = null;
154:         Node current = null;

156:         while (head != null)
157:         {
158:             //Remove Node from incoming list
159:             current = head;
160:             head = head.next;

162:             //Insert Node into reversed list
163:             current.next = reversedSequence;
164:             reversedSequence = current;
165:         }
166:         return reversedSequence;
167:     }

169:     private class Node
170:     {
171:         private int  data; //Data in the node
172:         private Node next; //Link to next node

174:         //Two constructors
175:         public Node(int data)
176:         {
177:             this(data, null);
178:         }
179:         public Node(int data, Node next)
180:         {
181:             this.data = data;
182:             this.next = next;
183:         }
184:     }
185: }