A Quick Guide on DSA and Competitive Coding in Java
Data Structures and Algorithms (DSA) are the building blocks of efficient and optimized software solutions, especially in the realm of competitive coding. In this quick guide, we’ll explore key concepts of DSA using Java, a versatile and widely used programming language.
Table of Content
- Arrays In Java:
- Strings In Java:
- Stack in Java:
- Queue in Java:
- Linked-List in Java:
- Hash Table in java:
- Maps In Java:
- Set In Java
- Heap in Java:
Arrays In Java:
Arrays are used to store multiple values in a single variable using a contiguous blocks of memory instead of declaring separate variables for each value.
Java
import java.io.*; class GFG { public static void main (String[] args) { int [] arr = new int []{ 1 , 2 , 3 , 4 , 5 }; } } |
Java provides 3 inbuilt data structures to store collections of elements
- Arrays
- Vectors
- Array List
Let us see the common operations performed on these data structures.
ARRAYS:
Operations |
Syntax |
---|---|
Declaring and Initializing an array of size N |
dataType[] myArray = new int[N]; |
Accessing Element at index i |
dataType value = myArray[i]; |
Array Length |
int length = myArray.length; |
Iterating Through an Array |
for (int i = 0; i < myArray.length; i++) { myArray[i]; } |
Sorting Arrays |
Arrays.sort(myArray); |
Binary Searching on Arrays for element X |
dataType index = Arrays.binarySearch(myArray, X); |
Comparing Arrays |
boolean areEqual = Arrays.equals(myArray1, myArray2); |
Array to String |
String arrayString = Arrays.toString(myArray); |
Operations |
Syntax |
---|---|
Package Import |
import java.util.Vector; |
Declaration and Initialization |
Vector<dataType> myVector = new Vector<>(); |
Insert Element X |
myVector.add(X); |
Insert Element X at index i |
myVector.add(i, X); |
Accessing Element at index i |
dataType value = myVector.get(i); |
Updating value at index i to X |
myVector.set(i, X); |
Removing Element at index i |
myVector.remove(i); |
Vector Size |
int size = myVector.size(); |
Checking if Vector is Empty |
boolean isEmpty = myVector.isEmpty(); |
Find the first index of a element X in vector |
int index = myVector.indexOf(X); |
Iterating Through a Vector |
for (int i = 0; i < myVector.size(); i++) { myVector.get(i); } |
Clearing the Vector |
myVector.clear(); |
Checking if Vector Contains Element X |
boolean containsElement = myVector.contains(X); |
Create a shallow copy of the Vector |
Vector<Integer> copyVector = (Vector<Integer>) myVector.clone(); |
Operation |
Syntax |
---|---|
Declaring |
ArrayList<dataType> arrayList = new ArrayList<>(); |
Accessing Element at index (i) |
int element = arrayList.get(i); |
Adding new Element (X) to the list |
arrayList.add(X); |
Updating Element at index (i) to X |
arrayList.set(i, X); |
Removing Element at index (i) |
arrayList.remove(i); |
Remove Element (X) from the list |
arrayList.remove(Integer.valueOf(X)); |
Size |
int size = arrayList.size(); |
Checking If an Element Exists |
boolean exists = arrayList.contains(3); |
Sorting in ascending order |
Collections.sort(arrayList); |
Strings In Java:
Strings are the type of objects that can store the character of values and in Java, every character is stored in 16 bits i,e using UTF 16-bit encoding. A string acts the same as an array of characters in Java.
Java
p
rovides 3 classes that are used to work with sequences of characters.
- String
- String Builder
- String Buffer
String vs String Builder vs String Buffer:
String Classes in Java |
When to use ? |
---|---|
String |
If you need an immutable sequence of characters and do not require frequent modifications, use |
String Builder |
If you need a mutable sequence of characters and the code is single-threaded, use |
String Buffer |
If you need a mutable sequence of characters and the code is multi-threaded, use |
Let us see the list of operations performed on these String classes one by one.
String:
Operations |
Syntax |
---|---|
Creating a String |
String str = “Hello, World!”; |
Length |
int length = str.length(); |
Concatenation of String X with String Y |
String newStr = X.concat(Y); |
Substring from index i to j |
String subStr = str.substring(i, j); |
Get character at index i |
char ch = str.charAt(i); |
Searching substring S in the string |
int indexOfWorld = str.indexOf(S); |
Replacing substring S to R |
String replacedStr2 = str.replace(S, R); |
Converting Case |
String upperCaseStr = str.toUpperCase(); |
Trimming Spaces |
String trimmedStr = str.trim(); |
Checking if string X and Y are equal |
boolean isEqual = str.equals(“Hello, World!”); |
Case Insensetive Checking if string X and Y are equal |
boolean isEqualIgnoreCase = X.equalsIgnoreCase(Y); |
Operations |
Syntax |
---|---|
Declaring string of N characters |
StringBuilder stringName = new StringBuilder(N); |
Accessing the character at index i |
char ithChar = stringBuilder.charAt(i); |
Appending character/string S at the end |
stringName.append(S) |
Inserting characters/strings at index i |
stringName.insert(i, S); |
Deleting Characters from index i to index j |
stringName.delete(i, j); |
Replacing Characters from index i to index j with S |
stringName.replace(i, j, S); |
Reverse the string |
stringName.reverse() |
Get length of the string |
int size= stringName.length() |
Operations |
Syntax |
---|---|
Creating a String Buffer |
StringBuffer buffer = new StringBuffer(“Hello, World!”); |
Append X to the string |
buffer.append(X); |
Insert String S at index i |
buffer.insert(i, X); |
Delete Characters from index i to j |
buffer.delete(7, 12); |
Delete Character at index i |
buffer.deleteCharAt(i); |
Replacing Characters from index i to j with X |
buffer.replace(i, j, X); |
Length |
int length = buffer.length(); |
Converting the |
String result = buffer.toString(); |
Reverse |
buffer.reverse(); |
Stack in Java:
- The
Stack
class in Java extends theVector
class, which is a dynamic array-like data structure. - Common stack operations are supported, such as push, pop, peek, and isEmpty.
Below is the list of operations performed on a Stack,
Operations |
Syntax |
---|---|
Import package |
import java.util.Stack; |
Declaring a Stack |
Stack<String> stack = new Stack<>(); |
push() |
stack.push(2); |
pop() |
int poppedElement = stack.pop(); |
peek() |
int topElement = stack.peek(); |
isEmpty() |
boolean isEmpty = stack.isEmpty(); |
size() |
int size = stack.size(); |
search() |
int position = stack.search(2); |
Queue in Java:
- A queue is a First-In-First-Out (FIFO) data structure used to manage elements in a way that the first element added is the first one to be removed.
- The
Queue
interface can be implemented usingLinkedList
orArrayDeque
.In Java, the Java Collections Framework provides several types of queues that can be used based on different requirements. Here are some commonly used queue types in Java:
- Linked List Queue
- Priority Queue
- Array Deque
- Blocking Queue
- Concurrent Linked Queue
- Linked Blocking Queue
- Array Blocking Queue
Linked List Based Queue
Operations |
Syntax |
---|---|
Import package |
import java.util.Queue; |
Declaring a Queue |
Queue<String> queue = new LinkedList<>(); |
Enqueue X into the queue |
queue.add(X); |
Dequeue |
int removedElement = queue.remove(); |
Peek |
int frontElement = queue.peek(); |
isEmpty |
boolean isEmpty = queue.isEmpty(); |
Size |
int size = queue.size(); |
Clear |
queue.clear(); |
- A priority queue stores elements with associated priorities, and elements with higher priorities are dequeued first.
- The ordering can be based on natural ordering or defined using a comparator.
- It’s typically implemented using a binary heap or another data structure that maintains the priority order.
Below is the list of operations performed on a Priority Queue,
Operations |
Syntax |
---|---|
Package import |
import java.util.PriorityQueue; |
Declaring |
PriorityQueue<DataType> myPriorityQueue = new PriorityQueue<>(); |
Adding Element X |
myPriorityQueue.add(X); |
Removing Element |
DataType highestPriority = myPriorityQueue.poll(); |
Peeking at the Head |
DataType highestPriority = myPriorityQueue.peek(); |
Size of PriorityQueue |
int size = myPriorityQueue.size(); |
Checking if PriorityQueue is Empty |
boolean isEmpty = myPriorityQueue.isEmpty(); |
Clearing the PriorityQueue |
myPriorityQueue.clear(); |
Converting PriorityQueue to Array |
DataType[] array = myPriorityQueue.toArray(new DataType[0]); |
Custom Comparator |
PriorityQueue<DataType> customPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder()); |
Operations |
Syntax |
---|---|
Declaring |
ArrayDeque<String> deque = new ArrayDeque<>(); |
Insert X at Front |
deque.addFirst(X); |
Insert X at End |
deque.addFirst(X); |
Delete from Front |
deque.removeFirst(); |
Delete from End |
deque.removeLast(); |
Peek Front element |
dataType frontElement = deque.peekFirst(); |
Peek End element |
dataType endElement = deque.peekLast(); |
Size |
int dequeSize = deque.size(); |
Checking if Empty |
boolean isEmpty = deque.isEmpty(); |
Linked-List in Java:
Java’s LinkedList
class is a versatile and commonly used data structure that implements the List
and Deque
interfaces while extending the AbstractSequentialList. Below is the list of operations performed on a java linked list,
Operations |
Syntax |
---|---|
Declaration |
LinkedList<DataType> myLinkedList = new LinkedList<>(); |
Inserting X at Head |
myLinkedList.addFirst(X); |
Removing from Head |
myLinkedList.removeFirst(); |
Inserting X at Tail |
myLinkedList.addLast(X); |
Removing from Tail |
myLinkedList.removeLast(); |
Inserting Element X |
myLinkedList.add(X); |
Inserting Element X at index i |
myLinkedList.add(i, X); |
Removing Element X |
myLinkedList.remove(X); |
Removing Element at index i |
myLinkedList.remove(i); |
Getting Element at index i |
DataType value = myLinkedList.get(i) |
Setting Element at index i to X |
myLinkedList.set(i, X); |
Checking for Existence of element X |
boolean containsX = myLinkedList.contains(X); |
Size of LinkedList |
int size = myLinkedList.size(); |
Conversion to Array |
DataType[] array = myLinkedList.toArray(new DataType[0]); |
Hash Table in java:
In Java, a Hashtable
is a legacy class that is part of the Java Collections Framework and implements the Map
interface. It provides a way to store key-value pairs, where each key must be unique. Here are the key operations performed on a Java Hashtable
:
Operations |
Syntax |
---|---|
Declaring |
Hashtable<String, Integer> hashtable = new Hashtable<>(); |
Inserting Key-Value Pair {K, V} |
hashtable.put(K, V); |
Removing Key= k |
hashtable.remove(k); |
Getting a Value by Key = k |
dataType value = hashtable.get(k); |
Checking if Key=k Exists |
boolean containsKey = hashtable.containsKey(k); |
Checking if a Value=v Exists |
boolean containsValue = hashtable.containsValue(v); |
Getting All Keys |
Enumeration<dataType> keys = hashtable.keys(); |
Getting All Values |
Enumeration<dataType> values = hashtable.elements(); |
Size |
int size = hashtable.size(); |
Checking if Empty |
boolean isEmpty = hashtable.isEmpty(); |
Maps In Java
In Java, maps are part of the Java Collections Framework and are used to store key-value pairs. The primary interface for maps is the
Map
interface. There are several implementations of theMap
interface in Java, each with its own characteristics. Here are some common.
- HashMap: O(1) time complexity for basic operations.
- TreeMap: O(log N) time complexity for basic operations.
- LinkedListMap : O(1) time complexity for basic operations.
Let us see the basic operations performed in these.
HashMap:
Operations |
Syntax |
---|---|
Import package |
import java.util.HashMap; |
Declaring a Java Hash-Map having Key data type as K and Value data type as V |
HashMap<K, V> hashMap = new HashMap<>(); |
put the key value pair {k,v} |
hashMap.put(k, v); |
get the value of Key = k |
int value = hashMap.get(k); |
remove key = k from the map |
hashMap.remove(k); |
containsKey |
boolean containsKey = hashMap.containsKey(“two”); |
containsValue |
boolean containsValue = hashMap.containsValue(2); |
Getting all the Keys |
Set<String> keys = hashMap.keySet(); |
Getting all the Values |
Collection<Integer> values = hashMap.values(); |
size |
int size = hashMap.size(); |
clear |
hashMap.clear(); |
isEmpty |
boolean isEmpty = hashMap.isEmpty(); |
A TreeMap
in Java is a sorted map implementation based on a red-black tree. It is part of the Java Collections Framework and implements the NavigableMap
interface. Below is the list of operations performed on a java Tree-Map:
Operations |
Syntax |
---|---|
Declaring a Java Tree-Map having Key data type as K and Value data type as V |
TreeMap<K, V> myTreeMap = new TreeMap<>(); |
Inserting a key-value pair {k,v} |
myTreeMap.put(k, v); |
Remove element with key=k |
myTreeMap.remove(k); |
getting value for key=k |
DataType value = myTreeMap.get(k); |
Checking Existence for key=k |
boolean containsKey = myTreeMap.containsKey(k); |
Checking Existence for value=v |
boolean containsValue = myTreeMap.containsValue(v); |
Size of TreeMap |
int size = myTreeMap.size(); |
Clearing the TreeMap |
myTreeMap.clear(); |
Navigating Keys |
String firstKey = myTreeMap.firstKey(); |
Operations |
Syntax |
---|---|
Declaring |
LinkedHashMap<Key dataType, Value dataType> linkedHashMap = new LinkedHashMap<>(); |
Inserting Key-Value {K, V} |
linkedHashMap.put(K, V); |
Accessing Value for Key=k |
dataType value = linkedHashMap.get(“Two”); |
Removing key=k |
linkedHashMap.remove(k); |
Checking if a Key=k Exists |
boolean containsKey = linkedHashMap.containsKey(“Three”); |
Checking if a Value=v Exists |
boolean containsValue = linkedHashMap.containsValue(v); |
Size |
int size = linkedHashMap.size(); |
Clearing the Map |
linkedHashMap.clear(); |
Set In Java
In Java, a
Set
is a part of the Java Collections Framework and is an interface that extends theCollection
interface. It represents a collection of unique elements, meaning that no duplicate elements are allowed. TheSet
interface is implemented by several classes in Java among them the most common ones are:
- HashSet
- TreeSet
- HashSet internally uses HashMap to store it’s elements.
- Whenever you create a HashSet object, one HashMap object associated with it is also created.
Below is the list of operations performed on a Hash-Set,
Operations |
Syntax |
---|---|
Package import |
import java.util.HashSet; |
Declaring |
HashSet<DataType> mySet= new HashSet<>(); |
Adding Element X |
mySet.add(X); |
Removing Element X |
mySet.remove(X); |
Checking whether X exists or not |
boolean containsX = mySet.contains(X); |
Size of HashSet |
int size = mySet.size(); |
Clearing the HashSet |
mySet.clear(); |
Checking if HashSet is Empty |
boolean isEmpty = mySet.isEmpty(); |
Converting HashSet to Array |
dataType[] array = mySet.toArray(new dataType[0]); |
In Java, a TreeSet is a part of the Java Collections Framework and implements the Set interface. It is a NavigableSet based on a TreeMap. The elements in a TreeSet are sorted in their natural order or according to a specified comparator at the time of creation.
Below is the list of operations performed on a java Tree-Set:
Operations |
Syntax |
---|---|
Declaration |
TreeSet<DataType> treeSet = new TreeSet<>(); |
Inserting Element X |
treeSet.add(X); |
Remove Element X |
treeSet.remove(X); |
Retrieving Subsets Less than X |
SortedSet<String> headSet = treeSet.headSet(X); |
Retrieving Subsets greater than or equal to X |
SortedSet<String> tailSet = treeSet.tailSet(X); |
Retrieving Subsets between X (inclusive) and Y (inclusive) |
SortedSet<String> subSet = treeSet.subSet(X, Y); |
Size |
int size = treeSet.size(); |
Heap in Java:
In computer science, a heap is a specific tree-based data structure that satisfies the heap property.
- A heap can be of two types: a max-heap or a min-heap. In a max-heap, the value of each node is greater than or equal to the values of its children, and in a min-heap, the value of each node is less than or equal to the values of its children.
- Heaps are often used in algorithms for implementing priority queues, heap sort, and various other applications where efficiently finding and removing the maximum or minimum element is required.
- In Java, the
PriorityQueue
class is an example of a priority queue based on a min-heap.
Mastering DSA is crucial for excelling in competitive coding, and Java’s versatility makes it an excellent choice for implementing these algorithms. Regular practice, understanding algorithmic paradigms, and implementing them in Java will not only enhance your problem-solving skills but also make you a proficient competitive coder. Happy coding!
Contact Us