Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structures and Algorithms (Data Structures (Linked List: (Single…
Data Structures and Algorithms
Data Structures
Linked List:
Single Linked List
Doubly Linked List
Circular List
Stack:
Last in First out Structures.
Only be accessed at the end element
Operation
:
clear(): Clear the stack.
isEmpty(): Check to see if the stack is empty.
push(el) / offer(el); Put the element el on the top of the stack.
pop(): Take the top most element from the stack.
topEl() / peek: Return the topmost element in the stack without removing it
Exception: EmptyStackException
Good case: poping and pushing are executed in constant time O(1).
Worst case: When the stack is full -> create a new stack and copy -> O(n) time to finish.
Algorithms
Delimitter matching
Queue
: First in First out Structures.
Can be accessed at both ends
One for adding and one for removing
Priority Queue:
Can be assigned to anable a particular process without affecting ovarall system operation.
FIFO rule is broken in these situations.
In preority queues, elements are dequeued according to their priority and their current queue position
Operations:
Java
add(T el): Insert element el in this priority.
NullPointerException if el is null
ClassCastException if the order used by this priority queue cannot be applied to el.
clear(): Remove all the elements from this priority queue.
Comparator<? super T> comparator()
: Return a comparator to be used to order elements of this priority queue or null if elements are ordered with the method compareTo().
contains(Object el): Return true if element el is in this priority queue.
offer(T el): Insert element el in this priority.
NullPointerException if el is null.
ClassCastException if the order used by this priority queue cannot be applied to el.
Operations:
clear(): Clear the queue.
isEmpty(): Check to see if the queue is empty.
enqueue(el): Put the element el at the end of the queue.
dequeue(): Take the first element from the queue.
firstEl() / font() / peek(): Return the first element in the queue without removing it.
Exception: EmptyQueueException
Tree
Tree is an abstract model of a hierarchical structure
A tree consists of nodes with a parent-child relation
Applications: Organization charts, File systems, Programming environments
Internal node
: Node with at least one child
External(leaf) node
: Node without children
Sub tree
: A node with its descendants
Level(depth) max = height
Binary Tree
A tree which each node has at most 2 children
Proper/Full binary tree
: Every node other than the leaves has 2 children
Complete binary tree
: All non-terminal nodes have both their children, and all leaves are at the same level
Implementing
Arrays (Can't predict the size of the array)
Linked List
Traversal
:
Breadth-first traversal
is visiting each node starting from the lowest(or highest) level and moving down(or up) level by level, visiting nodes on each level from left to right(or from right to left)
Pre order
: Root -> left -> right
In order
: Left -> root -> right
Post order
: Left -> right -> root
Binary search tree(BST)
Is a node based binary tree data structure which has the following properties:
The left node
value < node value
The right node
value > node value
--> left < node < right
Both left and right must be binary search trees
--> Each node value has a distinct value
Operation Delete
: 3 cases
The node is a leaf
The node has 1 child
The node has 2 children --->
Deletetion by Merging
Bring the rightmost node of the left subtree or the leftmost node of the right subtree to be the root of that 2 subtrees. Then put it in the deleted node.
Deletion by Copying
If the node has 2 children, the cases can be reduced to
The node is a leaf
The node has only one non-empty child
--> Solution: Replace the key being deleted with its immediate predecessor(or successor)
Balanced Binary Tree
Height-balanced
: If for every internal node p of T, the heights of the children of p differ by at most 1
Perfectly-balanced
: If it is height-balanced and all leaves are to be found on 1 level or 2 levels
AVL Trees O(log n)
: is a height-balanced binary search tree
Multiway Tree
Ordered tree
Tree traversal
Is the process of visiting each node in the tree exactly one time.
Pre-order traversal
A node is visited before its descendants
Post-order travelsal
A node is visited after its descendants
Breadth-first traversal
A node is visited first, then all it's children, then all its grandchildren,....
Graph
DIijkstra's Algorithm
Complexity: O(|V|2)
Floy's Algorithm
Complexity: O(|V|3)
Travel
Breadth First
Depth First
Algorithms
Recursion
Sorting
Selection Sort
Best: O(n2)
Avarage: O(n2)
Worst: O(n2)
Space worst: O(1)
Insertion Sort
Best: O(n)
Average: O(n2)
Worst: O(n2)
Space worst: O(1)
Quick Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n2)
Space worst: O(1)
Merge Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n2)
Space worst: O(n)
Heap Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n log(n))
Space worst: O(1)
Bubble Sort
Best O(n)
Average: O(n2)
Worst: O(n2)
Space worst: O(1)
Hashing
Data compression
Operation