Algorithm Analysis Efficiency
- Execution Time
- Space Required
Array is a container which can hold a fix number of items and these items should be of the same type
Most data structures make use of arrays to implement their algorithms.
- Element Each item stored in an array is called an element.
- Index Each location of an element in an array has a numerical index, which is used to identify the element.
A linked list is a sequence of data structures, which are connected together via links.
- Link Each link of a linked list can store a data called an element.
- Next Each link of a linked list contains a link to the next link called Next.
- LinkedList A Linked List contains the connection link to the first link called First.
Types of Linked List
- Simple Linked List Item navigation is forward only.
- Doubly Linked List Items can be navigated forward and backward.
- Circular Linked List Last item contains link of the first element as next and the first element has a link to the last element as previous.
Graph, Tree and varients
- Graph: Contains Vertices and Edges
- Tree: Minimally Connected Graphy without Loops and Circuts
- Binarry Tree: It is a Tree where Each node can have a max of 2 Children
- Binarry Search Tree: It is a Binarry tree where
LeftNode < ParentNode < RightNode
AVL Tree: self-balancing binary search tree.
the heights of the two child subtrees of any node differ by at most one
if at any time they differ by more than one
- Left rotation
- Right rotation
- Left-Right rotation
- Right-Left rotation
Visiting all Nodes
- In Order
- Left -> Root -> Right
- Sorted List in Ascending Order
- Pre Order
- Root -> Left -> Right
- Copy/Creation Order
- Post Order
- Left -> Right -> Root
- Delition Order