[go: up one dir, main page]
Scribd
Upload
67 views2 pages

Data Structures Unit Wise Notes

The document provides a comprehensive overview of data structures, organized into five units covering topics such as Abstract Data Types, Dictionaries, Search Trees, Graphs, and Pattern Matching. Each unit details key concepts, operations, and various implementations, including linked lists, hash tables, binary search trees, and sorting algorithms. It serves as a foundational guide for understanding the essential data structures and their applications in computer science.

Uploaded by

somanikita2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views2 pages

Data Structures Unit Wise Notes

The document provides a comprehensive overview of data structures, organized into five units covering topics such as Abstract Data Types, Dictionaries, Search Trees, Graphs, and Pattern Matching. Each unit details key concepts, operations, and various implementations, including linked lists, hash tables, binary search trees, and sorting algorithms. It serves as a foundational guide for understanding the essential data structures and their applications in computer science.

Uploaded by

somanikita2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structures - Unit-wise Brief Notes

UNIT-I: Introduction to Data Structures

- Abstract Data Types (ADTs): Logical models like List, Stack, Queue.
- Linear List: Sequence of elements.
- Singly Linked List: Nodes with data + next pointer.
- Operations: Insertion, Deletion, Searching.
- Stacks: LIFO (Last In First Out).
- Operations: Push, Pop, Peek.
- Applications: Expression evaluation, recursion, backtracking.
- Queues: FIFO (First In First Out).
- Operations: Enqueue, Dequeue.
- Types: Simple queue, Circular queue, Dequeue.
- Representations: Array and Linked list-based implementations.

UNIT-II: Dictionaries and Hash Tables

- Dictionaries: Key-value pairs.


- Implemented using linear list or skip list.
- Operations: Insert, Delete, Search.
- Hash Tables:
- Hash Functions: Map keys to table indices.
- Collision Resolution:
- Separate Chaining
- Open Addressing: Linear, Quadratic, Double Hashing
- Rehashing: Resizing and reapplying the hash.
- Extendible Hashing: Dynamic hashing using directory structure.

UNIT-III: Search Trees

- Binary Search Tree (BST):


- Properties: Left < Root < Right
- Operations: Search, Insert, Delete
- AVL Tree:
- Self-balancing BST
- Balance Factor: Height(left) - Height(right)
- Rotations: LL, RR, LR, RL
- Red-Black Tree: BST with color rules for balance.
- Splay Tree: Self-adjusting tree.
- Important Operations: Insert, Delete, Search

UNIT-IV: Graphs and Sorting

- Graph Representations:
- Adjacency Matrix
- Adjacency List
- Graph Traversals:
- DFS (Depth First Search)
- BFS (Breadth First Search)
- Sorting Algorithms:
- Heap Sort: Using binary heap
- Merge Sort: Divide and conquer approach
- External Sorting: Sorting large files (too big for memory)

UNIT-V: Pattern Matching and Tries

- Pattern Matching Algorithms:


- Brute Force: Naive approach
- Boyer-Moore: Skips unnecessary comparisons
- Knuth-Morris-Pratt (KMP): Uses prefix table to avoid rechecking
- Tries (Prefix Trees):
- Standard Trie: For storing words
- Compressed Trie: Compresses single child chains
- Suffix Trie: Stores all suffixes of a string for pattern search

You might also like