> For the complete documentation index, see [llms.txt](https://amartyushov.gitbook.io/tech/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://amartyushov.gitbook.io/tech/computer-science/general-notes.md).
# Data structures
## Power of 2
## Linear data structures
* Ordered data and order matters
* Logical start and end
* Sequential order with previous + next pointers
* Representatives
* Arrays
* Linked Lists
* Queues
* Stacks
## List
**Ordered** Can contain duplicate objects.
### Resizable array
Which is ArrayList in Java.
* :white\_check\_mark: Access is `O(1)` (**list.get(index)**)
* If (full & appendElement) => :white\_check\_mark: double the size. It takes `O(n)` .
* :white\_check\_mark: Amortized insertion time is still `O(1)`
* to insert **N** elements to array with size **N** you need:
* final capacity increase: n/2 elements to copy
* previous capacity increase: n/4 elements to copy
* previous capacity increase: n/8 elements to copy
* ...
* second capacity increase: 2 elements to copy
* first capacity increase: 1 elements to copy
* in total you have total number of copies $$n/2 + n/4 + n/8 + .. + 2 + 1 < N$$
* \=> inserting N elements takes `O(N)` => `O(1)` on average
* even though some insertions take `O(N)` in worst case
* push - add the element ( O(1))
* pop - take an element from the stack ( O(1))
* peek - returns the item from the top of the stack without removing it
* peek - returns the item from the top of the stack without removing it
LIFO (Last in, first out)
## Stack
Implement Stack using LinkedList
Time: O(1)
Space: O(n)
**Dynamic memory allocation**: The size of the stack can be increased or decreased dynamically by adding or removing nodes from the linked list, without the need to allocate a fixed amount of memory for the stack upfront (which will be the case when we implement Stack using Array).
```java
public class StackByLinkedList {
private static class Node {
int data;
public Node next;
}
Node top;
/**
* Initially: 1 <- 2 <- 3 (top pointer)
* After push: 1 <- 2 <- 3 <- new_value (top pointer)
*/
public Node push(int value) {
Node temp = new Node();
if (temp == null) {
System.out.println("Heap is full. Inserting an element would lead to stack overflow");
}
temp.data = value;
temp.next = top;
top = temp;
return temp;
}
public boolean isEmpty() {
return top == null;
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} else {
return top.data;
}
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} else {
int temp = top.data;
top = top.next;
return temp;
}
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty");
return;
}
Node current = top;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
public static void main(String[] args)
{
StackByLinkedList theStack = new StackByLinkedList();
theStack.push(11);
theStack.push(22);
theStack.push(33);
theStack.push(44);
theStack.display();
System.out.printf("\nTop element is %d\n", theStack.peek());
theStack.pop();
theStack.pop();
theStack.display();
System.out.printf("\nTop element is %d\n", theStack.peek());
}
}
```
## Queue
FIFO (first in first out)
* *Dequeue* - taking an element from the head
* *Enqueue* - adding element to the tail
* *Peek* - looking at head element, but not touching it
### **Deque (double-ended queue)**
## Non-linear data structures
## Heap
[MEDIUM](https://medium.com/swlh/data-structures-heaps-b039868a521b) [HACKERRANK](https://www.youtube.com/watch?v=t0Cq6tVNRBA) [MAXHEAP](https://www.youtube.com/watch?v=WCm3TqScBM8)
* This is a complete (each level is filled up before another level is added and the levels are filled from left to right) binary tree based data structure.
* Heaps are **not** sorted. There is no particular relationship between nodes at any level
* Height of a tree with N nodes is O(logN)
### When heap is useful
Heaps are used when the **highest or lowest order/priority element needs to be removed**. They allow quick access to this item in O(1) time. One use of a heap is to implement a priority queue.
Binary heaps are usually **implemented using arrays**, which save overhead cost of storing pointers to child nodes.
### Cons of Using Heaps
Heaps only provide easy access to the smallest/greatest item. Finding other items in the heap takes O(n) time because the heap is not ordered. We must iterate through all the nodes.
#### Indexes computation
* It’s parent is at the *floor* (i-1)/2 index.
* floor - округление до целого в меньшую сторону (2.7 -> 2, -2.7 -> -3)
* It’s left child is at 2 \* i + 1 index.
* It’s right child is at 2 \* i + 2 index.
### Insertion
until it finds a parent node that is smaller than it (Worst case is **O(logN)**)
### Deletion
The worst case scenario is that we have to traverse the entire tree. The cost of this is **O(logN)**.
### From array to Min Heap
The worst case time complexity will be **O(n)**.
#### Building Max neap from arrays using Williams method [LINK](https://www.youtube.com/watch?v=EQzqHWtsKq4)
### Java Min Heap implementation
```java
public class MinHeap {
private int capacity = 10;
private int size = 0;
int[] items = new int[capacity];
private int getLeftChildIndex(int parentIndex) {return 2 * parentIndex + 1;}
private int getRightChildIndex(int parentIndex) {return 2 * parentIndex + 2;}
private int getParentIndex(int childIndex) {return (childIndex-1) / 2;}
private boolean hasLeftChild(int index) {return getLeftChildIndex(index) < size;}
private boolean hasRightChild(int index) {return getRightChildIndex(index) < size;}
private boolean hasParent(int index) {return getParentIndex(index) >= 0;}
private int leftChild(int index) { return items[getLeftChildIndex(index)];}
private int rightChild(int index) { return items[getRightChildIndex(index)];}
private int parent(int index) { return items[getParentIndex(index)];}
private void swap(int indexOne, int indexTwo) {
int temp = items[indexOne];
items[indexOne] = items[indexTwo];
items[indexTwo] = temp;
}
private void ensureExtraCapacity() {
if (size == capacity) {
items = Arrays.copyOf(items, capacity * 2);
capacity *= 2;
}
}
public int peek() {
if (size == 0) throw new IllegalStateException();
return items[0];
}
//extract min element
public int poll() {
if (size == 0) throw new IllegalStateException();
int item = items[0];
items[0] = items[size-1];
size--;
heapifyDown();
return item;
}
public void add(int item) {
ensureExtraCapacity();
items[size] = item;
size++;
heapifyUp();
}
private void heapifyUp() {
int index = size - 1;
while (hasParent(index) && parent(index) > items[index]) {
swap(getParentIndex(index), index);
index = getParentIndex(index);
}
}
private void heapifyDown() {
int index = 0;
while (hasLeftChild(index)) { // if no left child => definitely no right child
int smallerChildIndex = getLeftChildIndex(index); // assume left is smaller
if (hasRightChild(index) && rightChild(index) < leftChild(index)) { // if right is smaller
smallerChildIndex = getRightChildIndex(index);
}
if (items[index] < items[smallerChildIndex]) {
break;
} else {
swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
```
## Hash table
[YOUTUBE](https://www.youtube.com/watch?v=KyUTuwz_b7Q)
```
class HashTable {
LinkedList[] data;
boolean put(String key, Person value) {
int hashCode = getHashCode(key);
int index = convertToIndex(hashCode); // e.g. hashCode % data.size()
// find proper linkedList for insertion
LinkedList list = data[index];
list.insert(key, value);
}
}
```
`key` => `hashCode` => `index`
#### Runtime
Worst case for *look up* is `O(N)`, when there are a lot of collisions and you have just on LinkedList of all elements. For good implementations without collisions *look up* is `O(1)` .
#### HashTable vs HashMap
### Resolve collisions
Collision when two keys after defining of index (hashCode () % mod) point to the same index.
#### Linear probing
#### Quadratic probing
#### Double hashing
#### Chaining
## TreeMap
Key-Value data structure, where keys are stored in ascending order.
Internal implementation of TreeMap has nothing to do with HashMap. TreeMap is built on red-black tree.