All The Data Structures Revisit For CS1332

Arrays
ArrayList(backed by array)
LinkedList: single linkedlist, doubly linkedlist, circlular singly linkedlists
Stack: sll-backed stack, array-backed stack, ddl-backed stack
queue: sll-backed queue, array-backed queue
deque: dll-backed deque, array-backed deque
Tree: trees, binary tree(heaps, bst), AVL trees,2-4 trees, B trees (and read-black tree)
binary heaps: (min heap, max heap)()
map: hashmap(hash family: hashmap, hashset, hashtable, concurrentHashmap)
skiplist
sorting algorithm: bubble, insertion, selection, cocktail shaker(pro bubble sort) (merge sort, LSD radix, quicik sort(quick select))
pattern matching algorithm: Boyer-Moore and KMP, Rabin-Karp
Graph: (BFS and GFS)
shortest path: dijkstra algorithm
MST algorithm: Prim, Kruskal
dynamic programming: LCS

there are few concepts I;m not familiar with:
ws1:
public/private:

ws2:
iterator and iterable:
iterable is an abstract api which needs to be implemented by child class.


comparator and comparable:
both are interfaces and can be used to sort clooection elements.
the difference is: comparable has one method compareTo() and comparator has two methods equals and compare.
followings are the example:

doubly linkedlist:

circular singly linkedlist:

we can add node to the front or back for CSL in O(1) and we can also remove a node from front in O(1), but we can’t remove a back node in O(1). thinking about why.
add to front in O(1): we add this new node so it becomes head.next. and we switch the value of head node and head.next node. it’s really trick.
add to the end in O(1): first, we add to the front in O(1), and then, just move head reference to head.next, so the node you recently added will be last node instead of first node
remove the front in O(1): has a simlar idea, we reserve head.next.value. and we remove the node of head.next, which can be done by head.next= head.next.next. and we set the value of head with preserved head.next.value.

ws3:
pay attention: all operation that seems can’t be done in O(1) time, but actually can be done in O(1), might be following way:

how does tree categorized?
based on the shape and order:


ws4:
BST:

pay attention, the sentence: binary search tree did not contains anything with balance, so the tree might end up with a unbalanced tree which will effect its effective.

question: why do we have to do pointer reinforcement technique instead of look ahead technique?

bst add method:

if we don’t find a match, then we go all the way done, that why everytime we add sth, we added it to the bottom of the tree. and there are always exist a right position for new node to add.

bst remove method:

Heap:
it is heap that need every node be as left as possible
heap can be implemented in array, pq
heap add method:

ws5:
heap remove method:

build heap:
pay attention: we don;t use add to construct a heap, which will cost nlogn
but we can use a method to make the cost n.

hashmap:

ws6

ws7
skiplist:
why do we want to have such thing as skiplist? because, we have linkedlist, which each a node have a pointer to later. have doubly linkedlist, which have pointer to previous and next node. now, why don’t we invent a data structure that have pointer to left right up and down? so this is skiplist.
another reason why we have skiplist. we know that if we want to search a element in linkedlist, then we have to tranverse. but is there a faster way to search? yes we do, we prmote the node with some kind of possibilities.

AVL trees:
avl tree is self balanced version bst.
how can it maintain balanced? becasue AVL node stores the data, left child, right child, height and balanced factor. and balanced factor = left child hight - right child height.
when will we meet the unbalanced situation? when we add or remove. and what do we do the keep balance?

//please use several line of words to describle the process of add or remove in avl?

ws8:
2-4 tree and b tree
they are both fat three, which can will low the height of the tree thus the efficient will be guaranteed.
2-4node, it’s a node can have 2 to 4 children and 1 to 3 data values, and a node with m data values must have m+1 children. and other properties:

the order prperty and the shape property is:

the promotion, transfer, fusion:
promotion happens in add method


transfer and fusion happens in remove
there are few cases when remove:
remove leaf with >1 values

remove leaf with only one values, and it has other siblings(fusion happens)


remove from an internal node with a child with > 1 values.(tamsfer happends)

and a summary about remvoing:

ws9:
remove a node of 2-4 tree can be done in many ways.
Sorting:

ws10:
three sorting often confuse with each other:
insertion, selection, quicksort.
insertion means we insert a unordered one to a ordered subarray
selection means each time we select the first smallest, the second smallest…(what is the different between selection and bubble sort?)

quick sort in the unstable(in average time complexity) version of merge sort
merge sort:
quicksort:
LSD radix is like counting sort, it uses space trade off time.
K-select(quick select)
problem: what is the point of K-select?

ws11:

ws12:

ws13:
how are we gonna solve a shortest path problem?
1 using bfs: this can be used in unweighted graphs. all unweighted grraph can be seen as weight 1 for each edges.
2 dijkstra: greedy + bfs

why dijkstra has efficient of O(V+E)logV?
logV because each time we have to poll a vertice in pq. and V+E comes from we tramverse every vertices and edges roughly once.

ws14:
mst is like a bridge between tree and graph
kruskal for mst:

ws15:
prim for mst:

dp: LCS
couldn’t be more familiar about this.