data-structures-and-algorithms-in-swift

These are the summary of my learnings from an udemy course: "Data Structures & Algo in swift"

Time Complexity:

1. Constant Time
2. Linear Time
3. Quadratic Time
4. Logarithmic Time - Binary Search
5. Quasilinear Time

Node:

• Root
• Child -> left child & right child
• Leaf

Linked List

• Elements are connected to each other by reference called Nodes

• 1st node in the linked list is called Head

• Last node is called Tail node

  Operations: - push - append - insert - pop - removeLast - remove

Stack (LIFO)

• Push
• Pop

Queue (FIFO)

• Peek
• Enqueue
• Dequeue

Recursion

• Base case - which stops the recursion.
• Recursive case

Trees:

• Depth First Traversal
• Level Order Traversal
• Search
• Binary Tree (can have max of: 2 Children only - left & right)
  • In order Traversal -> leftChild -> Node -> RightChild
  • Post order Traversal -> leftChild -> RightChild -> Node
  • Pre order Traversal -> Node -> leftChild -> rightChild
• Binary Search Tree

Linear Search

• O(n)

Binary Search

• Sorted array
• Middle index - left or right
• Best Time: O(1)
• Worst Time: O(log n)

Bubble Sort

• Unsorted
• Best Time: O(n) (if already sorted)
• Worst Time: O(n^2)

Selection Sort

• Swap the minimum element in the array with current index
• Move to next index and repeat step 1
• Best Time: O(n^2)
• Worst Time: O(n^2)

Insertion Sort

• Unsorted
• Best Time: O(n)
• Worst Time: O(n^2)

Graph:

Consist of

• Vertices / Vertex
• Edges / Edge

Types of Graphs:

• Weighted graphs
• Directed graphs
• Undirected graphs (bi-directional)

Adjacency List

• Most commonly/widely used way to create and represent a graph