> 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.
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://amartyushov.gitbook.io/tech/computer-science/general-notes.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.