- What is a Data Structure & Types of Data Structures
- What is an Algorithm & It's Characteristics
- Asymptotic Notations
- What is Space Complexity
- Array in Data Structure
- Algorithm for Insertion in Array
- Sparse Matrix
- Introduction to a Linked List
- Algorithm to Insert a Node at the End of the Linked list
- Algorithm to Insert a Node at the Front of the Linked List
- Algorithm to Delete a Node from Linked list
- Circular Linked List
- Algorithm to Insert a Node in the Circular Linked list
- Algorithm to Delete a Node from the Circular Linked list
- Doubly Linked List
- Algorithm to Insert a Node at the End of the Doubly Linked list
- Algorithm to Delete a Node from the Doubly Linked List
- Stack Data Structure
- Algorithm to convert Infix to Postfix
- Queue Data Structure
- Circular Queue in Data Structure
What is a Data Structure & Types of Data Structures
Definition:
Is a way to store and organise data in memory so that it can be used very efficiently?
Types of Data Structures:
• Primitive data structure
• Non-primitive data structure
Primitive data structure:
A primitive data structure can hold a single value.
Example:
1. int
2. char
3. float
4. double
5. pointer
Non-primitive data structure:
1. Linear data structure
2. Non-linear data structure
Linear data structure
The arrangement of data in a sequential manner is known as a linear data structure.
Example:
1. Arrays
2. Linked list
3. Stacks
4. Queues
Non-linear data structure
When one element is connected to one or more than one element known as a non-linear data structure. In non-linear data structures, the elements are arranged randomly.
Example:
• Trees
• Graphs
Classification:
• Static data structure: The size is allocated at the compile time. Means maximum fixed size
• Dynamic data structure: The size is allocated at the run time. Means size is flexible (We can create size as per our requirement)
Data structures operations:
• Searching: Searching an element in a data structure.
• Sorting: Sort the elements either in an ascending or descending order.
• Insertion: Inserting the new element in a data structure.
• Updation: Replacing the element with another element.
• Deletion: Deleting the element from the data structure.
• Merge: Combining the two sorted records into single sorted record.
• Traversing: Accessing each record exactly once.
Applications of Data Structure:
Arrays:
• Storing data in a tabular format
• Online ticket booking system-Multidimensional array
• Storing list of data elements belonging to same data type
• Storage of binary tree elements of fixed count
Stack:
• UNDO and REDO operations in a text editor
• Infix to postfix conversion
• Infix to prefix conversion
• Evaluation of postfix expression
• Recursion
• Reversal of a string
• Tower of Hanoi problem
• Function calls management
• Evaluation of arithmetic expressions
• Syntax checking of expressions in a programming environment
• Parenthesis matching
• Backtracking.
• Used in depth first search.
• Operating System functions
Queue:
• It is used in breadth first search
• Job scheduler operations of OS like: print buffer queue, keyboard buffer queue
• Job scheduling
• CPU scheduling
• Disk Scheduling
• Priority queues: Used in file downloading operations in a browser, Data transfer between peripheral devices and CPU
Linked List:
• Dynamic memory allocation
• Polynomial implementation for mathematical operations
• Circular linked list is used to implement OS
• Application functions that require round robin execution of tasks.
• Doubly linked list is used in the implementation of forward and backward buttons
• Prevent collision in a hash map
• Used to represent various states of a game
• UNDO or REDO function
Trees
• In computer systems, directory and file systems
• Implementation of navigation structure of a website
• Huffman coding
• Decision making in gaming applications
• For storing data keys for DBMS for indexing
• Hash trees
• Spanning trees
• path-finding algorithms
Graphs
• Travelling applications
• Mapping applications
• Resource utilization and availability in an organization
• Shortest path from Point one point to another point
• Neural network
• Ecommerce applications to present user preferences
• Routes in global positioning systems.
• Back or Forward button in browsers