Basics to know before practising DSA [Java]

These notes contain basic details such as how to declare, initiate, access(add/remove), iterate arrays, set, list, map, queue, stack

Arrays

stores values of the same data type. The address of elements stored consecutively in memory
length is fixed. inserting or deleting an element in middle is not easy

Declaration:

int[] nums = {1,2,4} //initializing with values
int[] nums = new int[10] //initializing with size. 0 will be initialized in all indexes if we declare without variables

Accessing an element:

Array index starts from 0..length-1
int[] nums = {1,2,4}
nums[0] — 1
nums[1] — 2
nums[2] — 4

Built-in methods to use in Arrays

Sorting an element — Arrays. sort(nums);

Finding the size of array — array_name.length

Filling array element with some values -

Arrays. fill(nums, -1) -> this will assign all values in the array as -1

Iterating Arrays

Let us consider we loop the elements in an integer array, we can do it like below

1. For loop:

for (i = 0; i < nums.length; i++) {

System.out.print(nums[i]); // accessing each element of array

}

2. For each loop

for (int i : nums) {

System.out.print(i);

}

Strings

Strings are nothing but a sequence of character values. They will be is written inside “ ”.

Declaration

Strins s = “Welcome”; // string literal

String s=new String(“Welcome”); // string object

The strings created like this are not mutable. If we want to add or delete anything from this string, we need to use StringBuilder or String Buffer class only

Built-in methods:

length of a string — length()

seeing character at some position — charAt()

if a string contains particular substring — contains()

Converting string to char array — toCharArray()

taking substrings — substring()

Replacing in string — replace()

Replacing first occurence — replaceFirst()

joining two strings — string1. concat(string2)

getting index of a character — string.indexOf(character)

removes beginnind and ending space in string — trim()

converting lower and capital letters inside string — toUpperCase() and toLowerCase()

StringBuilder:

StringBuilder is mutable.

Declaration:

StringBuilder string = new StringBuilder(“Welcome”);

Built in methods used in String Builder:

All string built in methods can be used here as well

string. append(“strings”) — to append to a string

string. insert(startIndex,”string”) — to insert a string from particular index

string. delete(startIndex, endIndex) — deleted string from the start to given end index

string. reverse() — to reverse the array

Iterating String:

For each loop:

for (Char c : string.toCharArray()){

{

System.out.println(c);

}

For loop:

for(int i = 0; i < string.length();i++)

{

System. out. println(string.charAt(i));

}

List:

size is dynamic

They store in the order we provide and they can have duplicates

Declaration

List<Data type> varName = new ArrayList<>();

List<Data type> varName = new LinkedList<>();

1. ArrayList

List<String> a1 = new ArrayList();
a1. add(“Zara”);
a1. add(“Mahnaz”);
a1. add(“Ayan”);
System. out. println(“ ArrayList Elements”);
System.out.print(“\t” + a1);

Output

ArrayList Elements
[Zara, Mahnaz, Ayan]

2. Linked List

List<String> l1 = new LinkedList<>();
l1. add(“Zara”);
l1. add(“Mahnaz”);
l1. add(“Ayan”);
System. out. println();
System. out. println(“ LinkedList Elements”);
System.out.print(“\t” + l1);

output:
LinkedList Elements
[Zara, Mahnaz, Ayan]

Built in methods in List-
add(value), add(index, value),

remove(value),

get(key),

contains(value) returns true or false
isEmpty() return true or false,
clear(),
size() returns int
removeLast()
removeFirst()

Difference between Array List & Linked List:

Array List stores values sequentially, so if we add or remove a value it needs more time to shift its elements and adjust

LinkedList stores randomly in memory and links by pointers. inserting and deleting takes less time here

Set:

Set can’t have duplicates

Types of Set

HashSet — stores values in random order and it is unsorted

LinekedHashset — stores in order we give
Treeset — stores in asc order

When to use Set

1. When we want to find union/intersection/difference in two sets of data, we can use sets.

2. Whenever we want to find a missing or a duplicate element we can first about Sets

Declaration and initialisation:

Set<Integer> set = new HashSet<>();

set.add(5);

set.add(18);

Build in methods -

add(value) — returns t/f,
remove(value),
contains(value) — returns t/f,
isEmpty() return true or false,
clear(),
size() returns int

Union — set1. addAll(set2);

Intersection — set1. retainAll(set2);

Difference between sets — set1. removeAll(set2);

Maps:

stores unique key, value pair

Types of Map

Hash Map — stores in random order and the key won’t be sorted
Linked Hash Map — stores in order we provide
Tree Map — stores in key’s ascending order

When to use the map

Whenever we want to count the frequency of something, we can use Map

Whenever we want to group something and count them, we can use Map

Declaration and Initialization

Map<String,String> m1 = new HashMap();
m1. put(“Zara”, “8”);
m1. put(“Mahnaz”, “31”);
m1. put(“Ayan”, “12”);
m1. get(“Zara”);

Methods:
-put(key,value), get(key)
-containsKey(key) — returns true or false
-containsValue(value) — returns true or false
-isEmpty() — returns True or false
-size() returns int
-values() returns list of values
-keys() returns list of keys
-putIfAbsent(key,new value)
-getOrDefault(existing,inititalize value)
-ceilingKey(key) -> gives greater element to the key
-lowerKey or floorkey(key) -> gives smaller element to the key

Iterating hash map

for(int value : map. values()){

}

for(int key : map. keys()){

}

for(Map.Entry<String,String> entry : map.entrySet()){
System.out.println(“Key = “ + entry.getKey() +
“, Value = “ + entry . getValue());
}

Stack:

Stack stores elements of the same data type.

We can insert, and remove elements in the stack in the Last In First Out policy (LIFO)

Declaration

Stack<Type> variable_name = new Stack<>();

Stack<Integer> stack = new Stack<>();

Methods used in Stack:

stack_name . push() — insert element into a stack

stack_name . peek() — checks the topmost element in the stack

stack_name . pop() — removes the topmost element in the stack

stack_name . size() — returns the number of elements in stack

stack_name . empty() — returns true / false. if stack is empty, it returns true. if stack is not empty it retuns false

stack_name . clear() — clears the stack

stack_name . contains(value) — returns true if the value we check is there in stack or else it returns false
stack_name . remove(index) — removes the value in given index

stack_name . search(value) — searches the value in stack and returns us the index of the value if present.

Iterating stack:

We can go through the stack elements in two ways.

1. Popping the elements

We can pop the stack elements one by one and go through all the elements.

2. For each loop

We can go through the stack by a for loop as below

for(String s : stack_name)

{

//Stack will be iterated from bottom to top direction in this way

}

How to identify if that problem can be solved using a stack

1. when we want to evaluate brackets, and expressions in a certain order we can use stacks.

2. When we wanted to use backspace characters in the keyboard or in any similar situations, we can use stacks

3. When we want to delete or remove the last elements we can use the stack.

4. When we want to backtrack to something and then again move forward direction multiple times we can use the stack.

5. We can use stack to find some peak elements (assuming the value plotted something like a graph) we can use stacks

Queue: (Interface and not class)

FIFO policy
1. Queue<Integer> ll = new LinkedList<Integer>(); //stores in order we insert
2. Queue<Integer> pQueue = new PriorityQueue<Integer>(); //it stores in Asc order. This can also be used as Min heap

2. Queue<Integer> pQueue = new PriorityQueue<Integer>((a,b) -> b-a); //it stores in desc order. This can also be used as max heap

methods:
offer(element) used to initialize the queue
add(element),

remove(element) /poll() returns top element
peek()/element() returns the top element that will be polled