Data Structures and Algorithms

1. Data Structures

Data Structures and Algorithms are fundamental concepts in computer science and they're essential for creating efficient and effective software solutions. Data structures in Java are specialized formats for organizing and storing data. Some common examples include lists, maps, sets, trees, and queues.

• Lists allow ordered access and manipulation of data, often implemented with Array List or LinkedList.

• Maps store data as key-value pairs, where each key is unique and used to retrieve its corresponding value. Examples include HashMap and TreeMap.

• Sets are used to store unique elements, without duplicates. HashSet and Tree Set are examples of set data structures.

• Trees are hierarchical data structures, often used for sorting or organizing data in a specific order, with examples such as Binary Search Tree and Red-Black Tree.

• Queues are a data structure that allows adding elements at the back and removing them from the front in a FIFO (First-In, First-Out) order, with examples including LinkedList and Priority Queue.

1.1 Queue

In Java, the queue is an interface with implementations such as PriorityQueue (each item has a predefined priority), LinkedList (useful when adding or deleting nodes), ArrayDeque (Array Double-Ended Queue), and PriorityBlockingQueue (synchronized).

1.2 List

ArrayList (array with preset methods), LinkedList, Vector (legacy synchronized array list), and Stack are concrete classes that implement the List interface. Examples

1.3 Map

LinkedHashMap is similar to HashMap, except it stores the order, whereas HashTable is synchronized (many threads can use it), making it the slower form of HashMap.

1.4 Set

HashSet and LinkedHashSet are implementations of the set, which is a data structure interface that stores different values (a HashSet that has order).

HashMap vs HashSet

The Map interface is implemented by Hashmap. HashSet, on the other hand, is the set interface’s implementation. For its implementation, HashMap does not use HashSet or any other set. TheHashSet’s internal implementation is based on Hashmap. The HashSet stores solely values and not key-value pairs. The HashMap modifies the key’s value when a value with an already existing key is attempted to be added, however, the HashSet does not allow you to insert an already existing element.

1.6 Tree

A tree is a non-linear data structure that organizes data elements in terms of hierarchical relationships.

ArrayList Implementation

Definition list of Integers:

List<Integers> arrList = new ArrayList<>();

Insert an element:

arrList.add(num); arrList.add(i, num);

Delete an element at index i :

int removed = arrList.remove(i);

Set or update an element at index i :

int previousElementAtI = arrList.set(i, num);

Get an element at index i :

int num = arrList.get(i);

Get the size of the list:

int size = arrList.size();

Check for Empty:

boolean bool = arrList.isEmpty();

Check if there is an element:

boolean bool = arrList.contains(num);

Get the index of a certain value 'num':

int i = arrList.indexOf(num);

Cast to a primitive list, i.e. ArrayList -> int[] :

int[] primArr = arrList.toArray();

Sorting :

Collections.sort(arrList, (a, b) -> a-b); // Ascending Collections.sort(arrList, (a, b) -> b-a); // Descending

Set interface- HashSet implementation

Definition :

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

Insert an element num, return true if the set not already contain num:

boolean setDoesNotContainNum = set.add(num);

Delete an element num, return true if num was in set:

boolean WasInSet = set.remove(num);

Check for an element num:

boolean contains = set.contains(num);

Get the size of the set:

int size = set.size();

Check for Empty:

boolean isEmpty = set.isEmpty();

Remove all map values:

map.clear();

Map Interface: HashMap implementation

Definition:

Map<K, V> map = new HashMap<>();

Insert/Update an element with key k1 with value v1, return the previous element, if present, or null if not present:

T previousElement = map.put(k1, v1);

Create a counter for letters in a string:

Map<Character, Integer> freq = new HashMap<>();

for(char c: str.toCharArray()){

freq.put(c, freq.getOrDefault(c, 0) + 1);

}

Delete an element with key k1:

D deletedEl = map.remove(k1);

Get an element with key k1:

V el = map.get(k1);

Get the size of the map:

int size = map.size();

Check for Empty:

boolean isEmpty = map.isEmpty();

Check if there is a value with key k1:

boolean contains = map.containsKey(k1);

Remove all map values:

map.clear();

In graph problem, when building adjacecy list from an edge List:

Map<Integer, List<Integer>> graph = new HashMap<>();

for(int[] edge: edgeList){

graph.computeIfAbsent(edge[0], val -> new ArrayList<>()).add(edge[1]);

}

Queue Interface

LinkedList implementation (deque)

Definition

Queue<Integers> queue = new LinkedList<>();

Insert an element

queue.add(num);

Delete element (the head), and returns it, it returns null if the queue is empty

E head = queue.poll();

Retrieve but does not remove the head of the queue

E head = queue.peek();

Get the size of the list

int size = queue.size();

Check for Empty

boolean isEmpty = queue.isEmpty();

PriorityQueue implementation (priority queue / heap)

Definition

Queue<Integers> heap = new PiorityQueue<>();

Insert an element

heap.add(num);

Delete element (the head)

E head = heap.poll();

Retrieve but not remove the head of the priority queue

E head = heap.peek();

Get the size of the list

int size = heap.size();

Check for Empty

boolean isEmpty = heap.isEmpty();

Deque Interface

ArrayDeque implementation (stack)

Definition

Deque<Integer> stack = new ArrayDeque<>();

Insert an element

boolean changed = stack.add(num); // it returns true if this collection is changed boolean changed = stack.addLast(num); // it returns true if this collections is changed

Delete element (the last)

E lastElement = stack.pop();

Retrieve the last element but does not remove it

E lastElement = stack.peekLast();

Get the size of the list

int size = stack.size();

Check for Empty

boolean isEmpty = stack.isEmpty();

ArrayDeque implementation (deque)

Definition

Deque<Integer> deque = new ArrayDeque<>(); // preferred

Insert an element

boolean changed = stack.add(num); boolean changed = stack.addFirst(num);

Delete the first element

E firstElement = stack.poll(); E firstElement = stack.pollFirst();

Retrieve but not remove the first element

E firstElement = stack.peekFirst(); E firstElement = stack.peek();

Get the size of the list

int size = stack.size();

Check for Empty

boolean isEmpty = stack.isEmpty();