Complete Overview of Data Structure

After a lot of research and studying the different books finally I am going to prepare this note for you in which I am going to include a short overview of the data structure and its syllabus.

 

It will be very helpful for all students to revise all the data structures basic concepts in one go 🙂

 

This Note covers the syllabus of data structure which is based on AICTE with a short description of each important topic from the perspective of your semester exams.

So Let’s start.. 

What is Data Structure?

In simple term we can define data structure as, Data Structure is a way of organizing the data elements in memory so that we can efficiently retrieve it and perform any operation efficiently.

Now, before moving forward on next topics lets have a eyes over the  syllabus of data structure which questions and answers you will find on this website on other page.

Syllabus Of Data Structure

Unit/Module 1 : Introduction to Data Structure

 

Basic Terminology, Elementary Data Organization, Built in Data Types in C.
Algorithm, Efficiency of an Algorithm, Time and Space Complexity,

 

Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space trade-off. Abstract Data Types (ADT)

Unit/Module 2 : Arrays and Linked List

 

Array:  Definition, Single and Multidimensional Arrays,

 

Representation of Arrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D,3-D and n-D Array, Application of arrays, Sparse Matrices and their representations.

 

Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two variables Polynomial. 

Unit/Module 3 : Searching And Sorting

 

Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary Search.
Concept of Hashing & Collision resolution Techniques used in Hashing. 

 

Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.

Unit/Module 4: Graphs and Trees

 

Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search and Breadth First
Search, Connected Component, Spanning Trees,

 

Minimum Cost Spanning Trees: Prim’s and Kruskal algorithm. Transitive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm.

Unit/Module 5 : Stacks and Queue

Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C,

 

Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Removal of recursion Problem solving using iteration and recursion with examples such as binary search, Fibonacci numbers, and Hanoi towers. Tradeoffs between iteration and recursion.


Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.

Now We have seen the definition of data structure. Let’s move on next topics 🙂

 

Data type:- It describes which type of value can be stored by a variable. suppose if a variable has int data type it means that that variable can only hold the integer values.

 

It is of two types:-

1). Primitive data type

2). non-primitive data type

 

For more detail, you may refer below URL.

 

Now let’s move on the next topics “Algorithm”

 

An algorithm is a finite steps solution of a problem in a human-readable format. Every algorithm has some space and time complexity which denotes how much an algorithm is efficient.

 

Five asymptotic notations are Big-Oh notation, Omega notation, Theta notation, little O and little omega to measure the efficiency. 

 

I hope you got a little bit idea of an Algorithm. 

 

Let’s jump on Unit 2 Array and Linked List.

 

An array is a collection of similar type of elements which is stored in contiguous memory locations. A here similar type of element means each element have the same data type.

 

We can denote it as

int arr[] ;

Means arr is an array in which we can only assign integer type of elements.

 

An array is Basically of two types:

1). One dimensional or single dimensional array

2). Multidimensional Array

 

Representation of an Array:

We can represent array in two ways 

 

1). Row Major Order

 

LOC (A [i, j]) = base_address + W [M (i) + j] Here,

base_address = address of the first element in the array.

W = Word size means a number of bytes occupied by each element of an Array.

N = Number of rows in the array.

M = Number of columns in the array.

 

2). Column Major Order

 

LOC (A [i, j]) = base_address + W [N (j) + (i)]

Here,

base_address = address of the first element in the array.

W = Word size means a number of bytes occupied by each element of an Array.

N = Number of rows in the array.

M = Number of columns in the array.

 

Linked List

Linked List is a linear and dynamic data structure. It stores elements at non-contiguous memory locations.

 

Linked List is of different types:

1). Singly Linked List

2). Doubly Linked List 

3). Circular Linked List

We have seen some basics of Array and Linked List ;

 

Let’s jump on Unit 3 Searching and Sorting

 

Searching: It is an operation to find a particular element in a list or in array.

Types of searching

  1. Linear Search
  2. Binary Search
  3. Hash Search
  4. Binary Tree Search

Sorting: It is also an operation on elements of an array or linked list to arrange it either in ascending or descending order.

 

Types Of Sorting

  1. Insertion Sort
  2. Bubble Sort
  3. Selection Sort
  4. Quick Sort
  5. Merge Sort
  6. Heap Sort
  7. Radix Sort

I think we can wrap up here. For more detail you can follow given link

 

Unit 4 is Graph and Tree

 

Graph : A Graph is a non-linear and abstract data structure which consist of nodes and edges. A single edge connects two Vertices in graph.

 

We Can Traverse the node of graph by using two algorithms

  1. BFS ( Breadth First Search)
  2. DFS (Depth First Search)

Tree : Tree is also a non-linear data structure that consists node which is connected using edge. But in tree all node are arrange as root node, parent node and child node in hierarchical manner.

 

Minimum cost spanning tree : It is a subset of tree and graph in which sum of the weight to traverse each node is minimum. A tree has many number of spanning tree but not all are minimum spanning tree.

 

There are some algorithm to identify minimum spanning tree.

  1. Prim’s Algorithm
  2. Kruskal’s Algorithm

The Last 5th unit is Stack and Queue

 

Stack: Stack is an abstract data type which follow the LIFO ( Last In First Out) Principle.

 

We can perform only two operation on stack

1). PUSH

2). POP

 

Stacks are used to evaluate post-fix expression.

 

Recursion : Recursion is a process in which one function calls it self again and again for a finite time to solve a given problem.

 

Queue: Queue is also a abstract data type which follow FIFO(First In First Out Principle).

 

2 Operations can be performed on Queue

1). enqueue

2). dequeue

 

Enqueue means put elements in queue and dequeue means remove it from queue.

 

For more details and semester question answers please follow the given link.