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.

✅ Access is O(1) (list.get(index))
If (full & appendElement) => ✅ double the size. It takes O(n) .
✅ 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).

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 HACKERRANK MAXHEAP

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

Java Min Heap implementation

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

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) .