A comprehensive collection of Data Structures and Algorithms implementations in Python. This repository contains well-documented code for various data structure operations and algorithms.
Implementation of fundamental searching techniques with both iterative and recursive approaches.
- Linear Search
- Iterative implementation
- Recursive implementation
- Binary Search
- Iterative implementation
- Recursive implementation
- Time Complexity: - O(n) for Linear Search - O(log n) for Binary Search
Different implementations of List Abstract Data Type.
- Array-based List
- Dynamic array implementation
- Basic operations (append, insert, remove)
- Linked List
- Singly linked list implementation
- Node-based structure
- Basic operations
Stack data structure with array-based implementation.
- Stack Operations
- Push operation
- Pop operation
- Peek operation
- isEmpty check
- Size tracking
Queue data structure with array-based implementation.
- Queue Operations
- Enqueue operation
- Dequeue operation
- Front element access
- Basic queue utilities
Expression conversion using stack data structure.
- Expression Converter
- Operator precedence handling
- Stack-based conversion
- Expression evaluation
Advanced queue implementation with circular array structure.
- Circular Queue
- Efficient space utilization
- Circular array operations
- Full/Empty state handling
- Python 3.x
- Git (for cloning the repository)
- Clone the repository: git clone https://github.com/yourusername/advanced-data-structures-lab.git cd advanced-data-structures-lab
- Navigate to specific experiment directory: cd experiments/01_searching
- Run the Python file: python searching_algorithms.py
Each implementation includes:
- Detailed comments explaining the algorithm
- Time and space complexity analysis
- Example usage in the main section
- Test cases demonstrating functionality
Each module contains a test section in the if __name__ == "__main__": block. Run the files directly to see the test outputs.
Example output for Searching Algorithms: python
- Test Array: [1, 3, 5, 7, 9, 11, 13, 15, 17]
- Searching for: 7
- Iterative: 3
- Recursive: 3
- Iterative: 3
- Recursive: 3
| Algorithm/Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Linear Search | O(n) | O(n) | O(1) |
| Binary Search | O(log n) | O(log n) | O(1) |
| Stack Operations | O(1) | O(1) | O(n) |
| Queue Operations | O(1) | O(1) | O(n) |
| Circular Queue | O(1) | O(1) | O(n) |
| List Operations | O(1)/O(n) | O(n) | O(n) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Access | O(1) | O(1) | O(1) |
| Search | O(n) | O(n) | O(1) |
| Binary Search (sorted) | O(log n) | O(log n) | O(1) |
| Insertion (at end) | O(1) | O(1) | O(1) |
| Insertion (at start) | O(n) | O(n) | O(1) |
| Deletion (at end) | O(1) | O(1) | O(1) |
| Deletion (at start) | O(n) | O(n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Stack Push | O(1) | O(1) | O(1) |
| Stack Pop | O(1) | O(1) | O(1) |
| Stack Peek | O(1) | O(1) | O(1) |
| Queue Enqueue | O(1) | O(1) | O(1) |
| Queue Dequeue | O(1) | O(1) | O(1) |
| Queue Peek | O(1) | O(1) | O(1) |
| Circular Queue All Ops | O(1) | O(1) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Access | O(n) | O(n) | O(1) |
| Search | O(n) | O(n) | O(1) |
| Insertion (at start) | O(1) | O(1) | O(1) |
| Insertion (at end)* | O(1) | O(1) | O(1) |
| Insertion (at middle) | O(n) | O(n) | O(1) |
| Deletion (at start) | O(1) | O(1) | O(1) |
| Deletion (at end) | O(n) | O(n) | O(1) |
| Deletion (at middle) | O(n) | O(n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Insertion | O(1) | O(n) | O(n) |
| Deletion | O(1) | O(n) | O(1) |
| Search | O(1) | O(n) | O(1) |
| Access | O(1) | O(n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Access | O(log n) | O(n) | O(1) |
| Search | O(log n) | O(n) | O(1) |
| Insertion | O(log n) | O(n) | O(1) |
| Deletion | O(log n) | O(n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Access | O(log n) | O(log n) | O(1) |
| Search | O(log n) | O(log n) | O(1) |
| Insertion | O(log n) | O(log n) | O(1) |
| Deletion | O(log n) | O(log n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Build Heap | O(n) | O(n) | O(n) |
| Insert | O(log n) | O(log n) | O(1) |
| Delete | O(log n) | O(log n) | O(1) |
| Get Min/Max | O(1) | O(1) | O(1) |
| Heapify | O(log n) | O(log n) | O(1) |
| Operation | Average Case | Worst Case | Space Complexity |
|---|---|---|---|
| Add Vertex | O(1) | O(1) | O(1) |
| Add Edge | O(1) | O(1) | O(1) |
| Remove Vertex | O(V + E) | O(V + E) | O(1) |
| Remove Edge | O(E) | O(E) | O(1) |
| DFS | O(V + E) | O(V + E) | O(V) |
| BFS | O(V + E) | O(V + E) | O(V) |
- V = number of vertices
- E = number of edges
- n = number of elements
- *For Linked List: O(1) insertion at end assumes we maintain a tail pointer
- Worst case for Hash Table operations occurs when there are many collisions
- BST operations' worst case occurs with an unbalanced tree
- Space complexity often refers to extra space needed beyond input storage
Contributions are welcome! Please feel free to submit a Pull Request.
- Fork the repository
- Create your feature branch (
git checkout -b feature/AmazingFeature) - Commit your changes (
git commit -m 'Add some AmazingFeature') - Push to the branch (
git push origin feature/AmazingFeature) - Open a Pull Request
- Thanks to all contributors who have helped with the implementations
- Special thanks to the Computer Science department for the guidance
- References to standard algorithms and data structures textbooks
⭐️ Star this repository if you find it helpful!