Generics and data
structures
Introduction
Generics in Java are a powerful feature that allows you to define classes,
interfaces, and methods with placeholder types.
With generics, we can define classes, interfaces, and methods that operate on a
parameterized type.
This type parameter is supplied at the time of instantiation or method invocation,
allowing for compile-time type checking and eliminating the need for explicit
casting.
Why generics?
● Type Safety: Generics provide compile-time type checking and reduce the risk
of ClassCastException.
● Code Reusability: You can write a method or a class that works with any data
type.
● Elimination of Casts: The code becomes cleaner because you don't need to
cast objects.
Simple generics example
public class Box<T> { Box<Integer> integerBox = new Box<>();
private T t; integerBox.set(10);
Integer value1 = integerBox.get();
public void set(T t) {
this.t = t; Box<String> strBox = new Box<>()
} strBox.set(“hello world”)
String value2 = strBox.get()
public T get() {
return t;
}
}
Stack data structure
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.
In Java, we can implement a generic stack using an array or a linked list.
Generics in Java allow you to create a stack that can hold elements of any type
(not just integers or strings.)
Generic stack using array (1)
public class ArrayStack<T> {
private T[] array;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.array = (T[]) new Object[capacity];
this.top = -1;
}
Array based stack (2)
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
Generic stack using array (3)
public void push(T item) {
if (isFull()) {
throw new IllegalStateException("Stack is full");
}
array[++top] = item;
}
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return array[top--];
}
}
A generic stack using linked lists (1)
public class LinkedStack<T> {
private Node<T> top;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}
public LinkedStack() {
this.top = null;
}
A generic stack using linked lists (2)
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
}
public T pop() {
if (top == null) {
throw new EmptyStackException();
}
T item = top.data;
top = top.next;
return item;
}
}
Exercise
Write a linked list implementation using generics with the following methods.
1. get(index): return value at index
2. find(value): find the index of value (or null if it does not exist.)
3. insert(value, index): insert value at index.
4. remove(index): remove indexed element from the list.
Binary Search Trees
A Binary Search Tree (BST) is a tree-based data structure where each node
contains a key (or value) and two child pointers: left and right.
The key values in a BST follow a specific ordering property:
● The key in any node is greater than or equal to all the keys in the left subtree.
● The key in any node is less than or equal to all the keys in the right subtree.
Example
Here's an example of a BST representing the values 5, 3, 7, 1, 4:
5
/ \
3 7
Create the BST and upload in FEELS:-
/ \
1 4 40, 10, 46, 43, 97, 34, 28, 44
BST implementation
In a typical implementation, a BST node contains three components:
● Key (or value): The data stored in the node.
● Left child: A pointer (or reference) to the left subtree.
● Right child: A pointer (or reference) to the right subtree.
Operations on a BST
1. Insertion: If the key is less than the current node's key, we go to the left child;
otherwise, we go to the right child. Continue this process until we reach a null
child, where we insert the new node.
2. Search: If the key is equal to the current node's key, we have found the node.
If the key is less than the current node's key, we go to the left child; otherwise,
we go to the right child. We continue this process until we find the key or
reach a null child, indicating that the key is not present.
Operations on a BST (2)
3. Deletion: Deleting a node from a BST can be more complex, as we need to
consider three cases:
● Leaf node: If the node to be deleted is a leaf node (no children), we
simply remove it.
● Node with one child: If the node has one child, we replace the node with
its child.
● Node with two children: we find the inorder successor (the smallest key in
the right subtree) or the inorder predecessor (the largest key in the left
subtree), replace the node's key with the successor/predecessor's key,
and then delete the successor/predecessor node.
BST definition
public class BinarySearchTree<T extends Comparable<T>> {
private Node<T> root;
private static class Node<T> {
T data;
Node<T> left;
Node<T> right;
Node(T data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public BinarySearchTree() {
this.root = null;
}
Node insertion
Insertion implementation
public void insert(T data) {
root = insertRecursive(root, data);
}
private Node<T> insertRecursive(Node<T> node, T data) {
if (node == null) {
return new Node<>(data);
}
int compareResult = data.compareTo(node.data);
if (compareResult < 0) {
node.left = insertRecursive(node.left, data);
} else if (compareResult > 0) {
node.right = insertRecursive(node.right, data);
}
return node;
}
Key Search
public boolean search(T data) {
return searchRecursive(root, data);
}
private boolean searchRecursive(Node<T> node, T data) {
if (node == null) {
return false;
}
int compareResult = data.compareTo(node.data);
if (compareResult < 0) {
return searchRecursive(node.left, data);
} else if (compareResult > 0) {
return searchRecursive(node.right, data);
} else {
return true;
}
}
Inorder traversal
In an in-order traversal, the nodes in the binary tree are visited in the following
order:
1. Traverse the left subtree by recursively calling the in-order traversal on the left
child.
2. Visit the current node (the root node of the current subtree).
3. Traverse the right subtree by recursively calling the in-order traversal on the
right child.
Inorder traversal implementation
public void inOrderTraversal() {
inOrderTraversalRecursive(root);
}
private void inOrderTraversalRecursive(Node<T> node) {
if (node != null) {
inOrderTraversalRecursive(node.left);
System.out.print(node.data + " ");
inOrderTraversalRecursive(node.right);
}
}
Exercises
1. Write code for BST node deletion
2. Write code for preorder traversal, which is defined as follows
a. Visit the current node (the root node of the current subtree).
b. Traverse the left subtree by recursively calling the pre-order traversal on the left child.
c. Traverse the right subtree by recursively calling the pre-order traversal on the right child.
3. Homework-: Refer B Tree and B+ Tree and make your own note for both
including implementation
