Appendix: Java Code Templates
Introduction
This appendix provides reusable Java code templates for common data structures and algorithms (DSAs) covered in the "Java Data Structures and Algorithms for Beginners" curriculum, with a focus on the Binary Search chapter and other core topics such as arrays, linked lists, stacks, queues, hashing, trees, graphs, and sorting and searching algorithms. These templates are designed to be beginner-friendly, modular, and adaptable for use in the problem statements and exercises, enabling students to quickly implement and test solutions. Each template includes comments for clarity and usage notes to guide implementation, aligning with the learning platform’s goal of providing hands-on education with embedded compilers and visualizations. By using these templates, students can focus on understanding algorithmic logic and adapting code to specific problem requirements, such as those in the Binary Search exercises.
Java Code Templates
Below are Java code templates for key data structures and algorithms, with examples drawn from the Binary Search chapter and other curriculum topics. Each template is complete, commented, and ready to be adapted for specific use cases.
1. Iterative Binary Search
Description: A template for iterative Binary Search to find a target integer in a sorted array, returning the index or -1 if not found. Used in Basic Binary Search (artifact_id="850a19d5-b136-4ecc-9dc6-53e9a8fcc6bc") and Performance Analysis (artifact_id="4b5c6d7e-8f9a-4b0c-9d1e-3f4a5b6c7d8e").
Usage Notes: Ensure the input array is sorted in ascending order. Modify to return additional data (e.g., comparisons) or adapt for objects by changing the comparison logic.
public class BinarySearch {
// Iterative Binary Search for a target in a sorted array
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Target not found
}
// Example usage
public static void main(String[] args) {
BinarySearch searcher = new BinarySearch();
int[] arr = {1, 3, 5, 7, 9}; // Sorted array
int target = 7;
int result = searcher.binarySearch(arr, target);
System.out.println("Index of " + target + ": " + result); // Output: Index of 7: 3
}
}
2. Recursive Binary Search
Description: A template for recursive Binary Search, used in Recursive Implementation (artifact_id="311f97d4-8924-4798-9267-d8e029502590"). Calls itself on a smaller range until the target is found or the range is invalid.
Usage Notes: Ensure the array is sorted. Add parameters for tracking comparisons or modify for object searches.
public class RecursiveBinarySearch {
// Recursive Binary Search
public int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) {
return -1; // Target not found
}
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, right); // Search right half
} else {
return binarySearch(arr, target, left, mid - 1); // Search left half
}
}
// Wrapper method for easier calling
public int binarySearch(int[] arr, int target) {
return binarySearch(arr, target, 0, arr.length - 1);
}
// Example usage
public static void main(String[] args) {
RecursiveBinarySearch searcher = new RecursiveBinarySearch();
int[] arr = {1, 3, 5, 7, 9}; // Sorted array
int target = 7;
int result = searcher.binarySearch(arr, target);
System.out.println("Index of " + target + ": " + result); // Output: Index of 7: 3
}
}
3. Linear Search
Description: A template for Linear Search to find a target integer in an array, used in Linear Search exercises (ch05_01). Iterates through the array sequentially.
Usage Notes: Works on sorted or unsorted arrays. Can be modified to count comparisons or find multiple occurrences.
public class LinearSearch {
// Linear Search for a target in an array
public int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Target found
}
}
return -1; // Target not found
}
// Example usage
public static void main(String[] args) {
LinearSearch searcher = new LinearSearch();
int[] arr = {4, 2, 7, 1, 9};
int target = 7;
int result = searcher.linearSearch(arr, target);
System.out.println("Index of " + target + ": " + result); // Output: Index of 7: 2
}
}
4. Array
Description: A template for creating and manipulating arrays, used in Array exercises (ch03_01). Supports initialization and basic operations.
Usage Notes: Adapt for specific tasks like reversal or sorting. Ensure bounds checking to avoid errors.
public class ArrayOperations {
// Create and initialize an array
public int[] createArray(int size) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i + 1; // Example: Fill with 1, 2, ..., size
}
return arr;
}
// Print array
public void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// Example usage
public static void main(String[] args) {
ArrayOperations ops = new ArrayOperations();
int[] arr = ops.createArray(5);
ops.printArray(arr); // Output: [1, 2, 3, 4, 5]
}
}
5. Linked List
Description: A template for a singly linked list, used in Linked List exercises (ch03_03). Includes node structure and basic operations.
Usage Notes: Extend for doubly or circular linked lists. Add methods for specific tasks like reversal or cycle detection.
public class LinkedList {
// Node class
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
// Insert at the end
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// Print list
public void printList() {
Node current = head;
System.out.print("[");
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(", ");
}
current = current.next;
}
System.out.println("]");
}
// Example usage
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.printList(); // Output: [1, 2, 3]
}
}
6. Stack
Description: A template for a stack using an array, used in Stack exercises (ch03_04). Follows Last-In-First-Out (LIFO) order.
Usage Notes: Adjust capacity for dynamic resizing or use a linked list for flexibility.
public class Stack {
private int[] arr;
private int top;
private int capacity;
// Initialize stack
public Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
// Push element
public void push(int data) {
if (top >= capacity - 1) {
System.out.println("Stack Overflow");
return;
}
arr[++top] = data;
}
// Pop element
public int pop() {
if (top < 0) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top--];
}
// Example usage
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
System.out.println("Popped: " + stack.pop()); // Output: Popped: 2
}
}
7. Queue
Description: A template for a queue using an array, used in Queue exercises (ch03_05). Follows First-In-First-Out (FIFO) order.
Usage Notes: Modify for circular queues or priority queues. Add bounds checking for robustness.
public class Queue {
private int[] arr;
private int front;
private int rear;
private int capacity;
// Initialize queue
public Queue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
}
// Enqueue element
public void enqueue(int data) {
if (rear >= capacity - 1) {
System.out.println("Queue Full");
return;
}
arr[++rear] = data;
}
// Dequeue element
public int dequeue() {
if (front > rear) {
System.out.println("Queue Empty");
return -1;
}
return arr[front++];
}
// Example usage
public static void main(String[] args) {
Queue queue = new Queue(5);
queue.enqueue(1);
queue.enqueue(2);
System.out.println("Dequeued: " + queue.dequeue()); // Output: Dequeued: 1
}
}
8. Bubble Sort
Description: A template for Bubble Sort, used in Bubble Sort exercises (ch04_01). Repeatedly swaps adjacent elements if out of order.
Usage Notes: Optimize with a flag for early termination or adapt for descending order.
public class BubbleSort {
// Bubble Sort for ascending order
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Example usage
public static void main(String[] args) {
BubbleSort sorter = new BubbleSort();
int[] arr = {5, 3, 8, 1, 2};
sorter.bubbleSort(arr);
System.out.print("Sorted: [");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]"); // Output: Sorted: [1, 2, 3, 5, 8]
}
}
✅ Tip or Warning Box
✅ Tip: Use these templates as starting points for DSA exercises. Modify them to fit specific problem requirements, such as adding comparison counters for Binary Search or implementing custom object sorting. Test each template with the provided main method to ensure correctness.
⚠ Warning: Always verify input constraints (e.g., sorted arrays for Binary Search, array bounds for stacks/queues) before using these templates. Incorrect usage, such as applying Binary Search to an unsorted array, will produce invalid results.