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
=> inserting N elements takes
O(N)
=>O(1)
on averageeven 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
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
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
Hash table
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.
Last updated