Data-Structures and Algorithms

Language: Java

Java melection is based on familiarity and object oriented nature. Although I could have choosen C++/Rust/Go. But I felt like choosing java the right option now. It's abstraction is on point for me.

Array

• Allocation is continous.
• If we have to store 5 numbers. The operating system will allocate 20 bytes of continous block of memory for storing the number.
  • Address = Base Address * (index * size of element)
• Faster access: O(1)
• Great cache locality due to continous memory. (Cache always take a page into l1/l2/l3 cache not a single elemt)
• Need to know the size upfront. (static by nature)
• Based on language. Like in Java, objects are stored in heap. Therefore, for String[] primitives, the data is continous with a pointer with a non-continous distrubution of storage.

LinkedList

• Implemented as: singly linked list, doubly linked list, and circular linked list.
• Access: O(n) -> need to traverse from head to key.
• Insertion:
  • Default: O(1) as linkedlist maintains the pointers
  • Middle: O(n)
• Deletion: Same as Insertion
• Space complexity: O(n) but it requires storing pointers for each data. That is a overhead compared to Arrays. This is the same reason database use B+-Tree.
• Specifics: Java have linkedlist implemented in it's collection framework. It implements as a default doubly linked list. It also implements the Deque interface.
• LinkedList is preferred over ArrayList due to array resizing issue. If we don't know the number of elements, we use linkedlist than arraylist.
• Used in graph algorithms. Other use cases comes from the Deque interface implementation.

Stack

• Stack is a linear data structure that follows LIFO.
• Stack can be implemented using dynamic array or list based approach.
• Supports: push(), pop(), peek()
• All actions are O(1)
• In Java, we have stack support from java.util.Stack, but it is old and synchronized. Modern standard is ArrayDeque. Also Deque in linkedlist.
• We only be interested in ArrayDeque implementation.
• Example: JVM => Every time a method is called in Java, a new "stack frame" is created containing all local variables. This is pushed to the thread's call stack. Also, when the method finishes, it is popped.
• Example 2: Compiler => Stack is used to parse brackets [{}] in program. Also we use it in backtracking.

Queue

• A Queue operates on the FIFO principle.
• Primary opeartions are enqueue and dequeue. But it leaves a problem of dead space considering we need to have O(1) lookup.
• Dead space problem is solved by Circular queue.
• For circular queue we use a modular for moving both the front and back pointer. Smoothing out the dead space problem.
• We have another important data structure in queue called Priority Queue. It doesn't follow strict FIFO. Instead, each element have priorities. The element with the highest priority is served first.
• Building a priority queue efficiently requires a Binary Heap mapped into a flat array.
• For any element at i:
  • Left child is: 2i + 1
  • Right child is: 2i + 2
  • Parent is at: Floor((i - 1)/2)
• Enqueue: O(log n)
• Dequeue: O(log n)
• Peek: O(1)