# Datastructures

## Basic Operations

- Traversing
- Searching
- Insertion
- Deletion
- Sorting
- Merging

## Algorithm Analysis Efficiency

- Execution Time
- Space Required

## Array

Array is a container which can hold a

fix number of itemsand these items should be of thesame type

Most data structures make use of arraysto 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.

## Linked list

A linked list is a sequence of data structures, which are connected together via links.

### Important Terms

**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**AVL Rotations**- Left rotation
- Right rotation
- Left-Right rotation
- Right-Left rotation

## Tree Traversal

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