Data Structures - Definitions and Explanations
UNIT I
Array Operations (Insertion, Deletion, Merge, Search)
An array is a collection of elements stored at contiguous memory locations. Operations include
insertion (adding an element), deletion (removing an element), merging (combining arrays),
and searching (finding an element).
Linear Search
Linear search checks each element in sequence until the desired element is found or the list
ends. It is simple but inefficient for large datasets.
Binary Search
Binary search works on sorted arrays by repeatedly dividing the search interval in half, offering
a time complexity of O(log n).
Linear Search vs Binary Search
Linear search works on unsorted data and checks all elements, while binary search is faster
but requires sorted data.
Bubble Sort
Bubble sort repeatedly swaps adjacent elements if they are in the wrong order. It is easy to
understand but inefficient (O(n²)).
Selection Sort
Selection sort repeatedly finds the minimum element and places it at the beginning. It performs
well on small lists but poorly on large ones.
UNIT II
Sparse Matrix
A sparse matrix contains mostly zero values. It is efficiently stored using special data
structures that only store non-zero elements.
Polynomial Matrix
Polynomial matrices represent polynomial expressions in matrix form. They are useful for
mathematical computations and symbolic manipulations.
Single Linked List
A linked list consists of nodes where each node contains data and a reference to the next
node. In a single linked list, traversal is only forward.
Double Linked List
A doubly linked list has nodes that contain references to both the next and previous nodes,
allowing bidirectional traversal.
Circular Linked List
In a circular linked list, the last node points back to the first node, creating a circular structure
for continuous traversal.
UNIT III
Infix to Postfix
Converts expressions with operators between operands (A+B) into postfix (AB+). It simplifies
evaluation using stacks.
Infix to Prefix
Converts expressions like (A+B) to prefix form (+AB). Operators precede operands for easier
computation.
Evaluation of Postfix
Postfix expressions are evaluated using a stack by processing operands and operators in
left-to-right order.
Evaluation of Prefix
Prefix expressions are evaluated right-to-left using a stack, applying operators to the correct
operands.
Recursion
Recursion is a process where a function calls itself to solve smaller instances of a problem until
a base case is reached.
Stack and Queue (Theory & Program)
A stack follows LIFO (Last In First Out) principle, while a queue follows FIFO (First In First
Out). They are used in expression evaluation and process scheduling.
UNIT IV
Binary Tree Traversal (Inorder, Preorder, Postorder)
Traversal refers to visiting all nodes of a tree. Inorder (Left-Root-Right), Preorder
(Root-Left-Right), and Postorder (Left-Right-Root) are common methods.
Binary Search Tree (BST)
A BST is a binary tree where the left child has smaller and the right child has greater values
than the parent node, allowing efficient searching.
AVL Tree
An AVL tree is a self-balancing binary search tree where the height difference between left and
right subtrees of any node is at most 1.
Graph: BFS, DFS (Theory & Program)
Graphs consist of vertices and edges. BFS explores level by level, while DFS explores
depth-wise. Both use queues or stacks.
Graph Representation (Matrix, List, Linked List)
Graphs can be represented as adjacency matrices, adjacency lists, or linked lists depending
on space and access requirements.