public class LinkedNodeRecursion
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: }