Data Structures in Java
1. Array Implementation
Manual array operations.
public class ArrayOps{ public static int find(int[] a,int x){ for(int i=0;i<a.length;i++)
if(a[i]==x) return i; return -1; } }
Page 1 of 12
2. Singly Linked List
Simple linked list with insert and print.
class Node{ int val; Node next; Node(int v){val=v;} }
public class SinglyList{ Node head; void add(int v){ Node n=new Node(v); n.next=head; head
=n; } void print(){ for(Node p=head;p!=null;p=p.next) System.out.println(p.val); } public
static void main(String[] args){ SinglyList l=new SinglyList(); l.add(3); l.add(5); l.prin
t(); } }
Page 2 of 12
3. Stack using Array
Push, pop operations.
public class StackArr{ int[] arr; int top=-1; StackArr(int n){arr=new int[n];} void push(i
nt v){ arr[++top]=v; } int pop(){ return arr[top--]; } }
Page 3 of 12
4. Queue using Linked List
Enqueue and dequeue.
class QNode{ int v; QNode next; QNode(int v){this.v=v;} }
public class LinkedQueue{ QNode head, tail; void enqueue(int v){ QNode n=new QNode(v); if(
tail!=null) tail.next=n; tail=n; if(head==null) head=n; } int dequeue(){ int v=head.v; hea
d=head.next; if(head==null) tail=null; return v; } }
Page 4 of 12
5. Binary Tree - Traversal
Preorder, inorder, postorder.
class TNode{ int v; TNode left,right; TNode(int v){this.v=v;} }
public class BTree{ void inorder(TNode r){ if(r==null) return; inorder(r.left); System.out
.println(r.v); inorder(r.right); } }
Page 5 of 12
6. BST Insert & Search
Binary Search Tree basic ops.
public class BST{ class N{int v; N l,r; N(int v){this.v=v;} } N root; void insert(int v){
root=ins(root,v); } N ins(N n,int v){ if(n==null) return new N(v); if(v<n.v) n.l=ins(n.l,v
); else n.r=ins(n.r,v); return n; } boolean search(int v){ N t=root; while(t!=null){ if(t.
v==v) return true; t = v < t.v ? t.l : t.r; } return false; } }
Page 6 of 12
7. Heap - Min Heap
Using PriorityQueue as min-heap.
import java.util.*;
public class MinHeapDemo{ public static void main(String[] args){ PriorityQueue<Integer> p
q=new PriorityQueue<>(); pq.add(5); pq.add(2); System.out.println(pq.poll()); } }
Page 7 of 12
8. Hash Table Basics
HashMap put/get collision idea.
import java.util.*;
public class HashDemo{ public static void main(String[] args){ Map<String,Integer> m=new H
ashMap<>(); m.put("a",1); System.out.println(m.get("a")); } }
Page 8 of 12
9. Sorting - QuickSort
Implement QuickSort recursively.
public class QuickSort{ static void qs(int[] a,int l,int r){ if(l>=r) return; int p=a[(l+r
)/2]; int i=l,j=r; while(i<=j){ while(a[i]<p) i++; while(a[j]>p) j--; if(i<=j){ int t=a[i]
; a[i]=a[j]; a[j]=t; i++; j--; } } qs(a,l,j); qs(a,i,r); } public static void main(String[
] args){ int[] a={3,6,1,5}; qs(a,0,a.length-1); for(int v:a) System.out.println(v); } }
Page 9 of 12
10. Searching - Binary Search
Binary search on sorted array.
public class BinarySearch{ public static int bs(int[] a,int x){ int l=0,r=a.length-1; whil
e(l<=r){ int m=(l+r)/2; if(a[m]==x) return m; if(a[m]<x) l=m+1; else r=m-1; } return -1; }
}
Page 10 of 12
11. Graph - Adjacency List
Build adjacency list for graph.
import java.util.*;
public class GraphAdj{ public static void main(String[] args){ List<List<Integer>> g=new A
rrayList<>(); int n=3; for(int i=0;i<n;i++) g.add(new ArrayList<>());
g.get(0).add(1); g.get(1).add(2); System.out.println(g); } }
Page 11 of 12
12. Topological Sort
Kahn's algorithm outline.
import java.util.*;
public class Topo{ public static void main(String[] args){ /* build graph and indegree, us
e queue for nodes with indegree 0 */ } }
Page 12 of 12
