/DSA

Data structures and Algorithms

Primary LanguageC++

Data Structures and Algorithms in C++

This repository contains implementations of various data structures and algorithms in C++. It's a collection of solutions to common problems encountered in competitive programming and coding interviews.

Table of Contents

Data Structures

1. Array

  • Dynamic Array: Implementation of a resizable array.
  • Matrix Operations: Basic matrix operations like addition, multiplication, etc.

2. Linked List

  • Singly Linked List: Implementation with operations like insertion, deletion, and traversal.
  • Doubly Linked List: Implementation with bidirectional traversal and modification operations.

3. Stack

  • Stack: Implementation of stack data structure with push, pop, and peek operations.
  • Expression Evaluation: Evaluate infix expressions using stacks.

4. Queue

  • Queue: Implementation of queue with enqueue, dequeue, and peek operations.
  • Circular Queue: Circular implementation of queue for efficient memory usage.

5. Binary Tree

  • Binary Search Tree: Implementation of BST with insertion, deletion, and searching.
  • Tree Traversal: Depth-first and breadth-first traversal algorithms.

6. Heap

  • Min-Heap and Max-Heap: Implementation of binary heaps.
  • Heap Sort: Sorting algorithm using heap data structure.

7. Hash Table

  • Hash Map: Implementation of a hash map using chaining for collision resolution.
  • Open Addressing: Hash map implementation using linear probing.

Algorithms

1. Sorting Algorithms

  • Bubble Sort: Simple sorting algorithm with O(n^2) complexity.
  • Merge Sort: Efficient sorting algorithm with O(n log n) complexity.
  • Quick Sort: Sorting algorithm with O(n log n) average case complexity.

2. Searching Algorithms

  • Binary Search: Search algorithm for sorted arrays.
  • Depth-First Search (DFS): Graph traversal algorithm.
  • Breadth-First Search (BFS): Graph traversal algorithm.

3. Graph Algorithms

  • Dijkstra's Algorithm: Shortest path algorithm for graphs with non-negative weights.
  • Kruskal's Algorithm: Minimum spanning tree algorithm using the union-find data structure.

4. Dynamic Programming

  • Fibonacci Sequence: Memoization and tabulation methods.
  • Knapsack Problem: Solution using dynamic programming approach.

Contributing

Contributions are welcome! If you have a new algorithm or data structure implementation, please feel free to open an issue or a pull request.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

  • Inspired by the need for structured implementations of DSA for learning and reference purposes.
  • Thanks to all contributors who have helped improve this repository.