Datastructures

Basic Operations

  • Traversing
  • Searching
  • Insertion
  • Deletion
  • Sorting
  • Merging

Algorithm Analysis Efficiency

  1. Execution Time
  2. Space Required

Array

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.

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