Data Structures in Depth

A data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific task. Data structures provide a means to manage large amounts of data efficiently. Efficient data structures are key to designing efficient algorithms.  Data structures can be used to organize the storage and retrieval of information stored in both main memory and secondary memory.

Data structures serve as the basis for ADT. The ADT  (Abstract Data Types) defines the logical form of the data type. Data structures are based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer. 

The array and record data structures are based on computing the addresses of data items with arithmetic operations. The linked data structures are based on storing addresses of data items within the structure itself. The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure.

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. Each node contains: data, and a  link to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.

Following topics are covered as part of hands-on / Live coding videos :

Linked Lists (LL) Implementation / Coding:

• Concept of link

• Creating a Linked List (LL)

• Appending a node to LL

• Display of LL

• Length of LL (count)

• Reversing of LL

• Sorting

• Adding node at Start of LL

• Inserting node in between of LL

• Deleting a node

• Creating a Double LL

• Appending a node to Double LL

• Display of Double LL

• Length of Double LL (count)

• Reversing of Double LL

• Inserting a node in between a Double LL

• Rotate Double LL

• Count Pairs with criteria for a Double LL

• Questions

• Circular LL overview (access pointers)

• Creating a Circular LL

• Adding node at Start Circular LL (approach 1)

• Traversal / Display Circular LL (approach 1)

• Inserting node in between a Circular LL (approach 1)

• Deleting a node

• Adding node at End Circular LL (approach 2)

• Traversal / Display Circular LL (approach 2)

• Circular LL - Queue (Adding Node)

• Circular LL - Queue (Removing Node)

• Questions

Stacks (Implementation / Coding):

• Stack overview

• Stack with Array

• Expressions

• Evaluation of Postfix expression

• Infix to Post fix

• Evaluation of Prefix overview. infix to prefix overview

• Application: Finding next big element

• Stack using Linked List

• Reversing Stack with Linked List

• Questions

Queues (Implementation / Coding) :

• Queue Overview

• Queue using Array

• Priority Queue with Array

• Queue using Linked List

• Priority Queue using Double Linked List

• Questions

Recursion

• Recursion Overview, Phases, Types

• Recursive Functions

• Linked List operations using Recursion

• Questions

Trees

• Binary Trees

• Tree Traversals

  • Inorder

  • preorder

  • postorder

• Binary Search Trees (BST)

• BST - Insertion

• BST - Insertion & Traversals

• Traversals Explained

• BST - Search

  • Search operations

• BST Deletion

  • Deletion cases

• Binary Tree to BST conversion

• Identify a Tree to be BST

• Identify zero, one child nodes of BST

• Questions

Sorting

• Selection Sort

• Selection Sort Analysis

• Bubble Sort

• Bubble Sort Analysis

• Insertion Sort

• Insertion Sort Analysis

• Quick Sort

• Quick Sort Analysis

• Quick Sort, Merge Sort Discussion

• Questions

Threaded Binary Trees

• Need for Threaded Binary Tree (TBT)

• Threaded Binary Tree Overview

• One way Structure, Traversal

• Two way Structure, Traversal

• Insert functionality

• Traversal functionality

• Delete functionality

  
  

AVL Trees

• Need for AVL Trees

• AVL Tree Overview

• Tree Rotations (Left, Right)

• Insert cases, Application of Insert cases

• Insert Functionality code, Demo

• Functions Code - LeftRight rotations, RightLeft rotations,

• Delete Functionality, Rotations needed for Delete

Graphs

• Graphs

• Graph Types

  • Adjacency Matrix, Adjacency List

• Traversals

  • BFS (Breadth First Search)

  • BFS Algorithm

  • DFS (Depth First Search)

  • DFS Algorithm

• Spanning tree

• Dijkstra Shortest path Algorithm

• Minimum Spanning tree

• Prim's algorithm

• Kruskal   algorithm

Hashing, Collision Resolution

• Hashing

• Hash Functions

• Collision Resolution

• Open Addressing (Closed Hashing)

• Probing

  • Linear, Quadratic, Double hashing

• Load factor of Hash Table

• Deletion

• Separate Chaining (Open Hashing)

• Cuckoo Hashing

Lexicographic Order (Lexical Order)

• Overview

• Previous Permutation

• Next Permutation