Mastering DSA in C & C++ • A complete guide up to 100+ algorithms (Recursion, Sorting, Hashing etc.) with common and advanced data structures (Array, Linked List, Stack, Queue, Trees, AVL, Heap, Graph etc.) implemented completely from scratch. Covers core programming concepts like Pointers, OOP, Structures, Memory Management etc.
AUTHOR: Mert Eldemir
SEARCH RESOURSES:
Abdul Bari |
CPlusPlus |
GeeksforGeeks |
NeetCodeIO |
LeetCode |
Wikipedia
Project divided into 3 topics. Here the table of headings and subheadings. Each topic contain code examples with explained comment lines and Readme files.
- Array Basics • Structures • Pointers • Reference
- Functions • Converting C to C++
- Scope Resolution • OOP
- Generics • Templates • Operator Overloading
- Array Representations • Array ADT • Strings
- Linked Lists • Stack • Queue
- Trees • Binary Search Tree • AVL Tree • 2-3 Tree • Red Black Tree • Heap
- Recursion • Sorting • Array
- Bitwise • Strings
- Linked List • Stack • Queue
- Binary Tree • Binary Search Tree • Heap
- Backtracking
Each section of this repository was created with genuine passion, thorough research, and dedicated implementation. I hope it proves helpful to others.
NOTE: Time and space complexity values are usually provided as comments near the algorithms. Unless otherwise specified (e.g., best, average, or worst case), you should assume that the given complexities refer to the worst-case scenario. Some of explanations in .md files are made by using AI for better understanding the topic.
Let's get started! 🚀
Essential concepts of C & C++ before diving into DSA. Arrays, Structures, OOP, Pointer and a lot more with explanation and example code.
-
Representation of Arrays in C & C++
-
Declaring and initializing dynamic and static arrays
Code: arrays.cpp
Structures in C++ are user defined data types which are used to store group of items of non-similar data types.
-
Understanging the concept of Structure in C++ / Manipulating members of the structures
-
Creating struct objects in Stack and heap.
Code: structures.cpp
Pointers are symbolic representations of addresses. They enable programs to simulate call-by-reference as well as to create and manipulate dynamic data structures. Iterating over elements in arrays or other data structures is one of the main use of pointers.
The address of the variable you’re working with is assigned to the pointer variable that points to the same data type (such as an int or string).
-
Difference between Heap and Stack / Allocating & Deallocating Memory on Heap
-
Creating and allocating memory on Heap and seeing difference between C style and C++ style
Code: pointers.cpp
Readme: Pointers.md
When a variable is declared as a reference, it becomes an alternative name for an existing variable. A variable can be declared as a reference by putting ‘&’ in the declaration.
-
Creating & Manipulating references to variables
-
Use cases of references in for each blocks
Code: reference.cpp
Readme: Reference.md
-
Creating and calling functions & Formal and Actual parameters
-
Parameter passing methods (by Value, Address, Reference)
-
Functions that using and returning pointers
-
Passing Arrays/Structures as parameters & Callback functions
Code: functions.cpp
Readme: Functions.md
-
Difference between writing C and C++ code
-
Rewriting structure based C code into OOP based C++ code
C Code: c-code.c
C++ Code: cpp-code.cpp
In programming, scope refers to the context within which a variable or function is accessible. C++ has several scopes, such as global scope, local scope, class scope, and namespace scope. When a variable or function is declared, it exists within a specific scope, and that scope defines where it can be accessed.
-
:: operator and Scope Resolution
-
Accessing Global Variables / Static Members / Namespaces
-
Defining Class Member Functions Outside the Class
Code: scope-resolution.cpp
Readme: ScopeResolution.md
Object-oriented programming – As the name suggests uses objects in programming. Object-oriented programming aims to implement real-world entities like inheritance, hiding, polymorphism, etc. in programming. The main aim of OOP is to bind together the data and the functions that operate on them so that no other part of the code can access this data except that function.
-
Classes and structs
-
Class Members / Definition of Memeber Functions / Classes defined with struct and union
-
Constructors & Member initialization in constructors
-
Pointers to classes
-
OOP Concepts (Encapsulation, Inheritance, Polymorphism, Abstraction etc.)
-
Runtime vs Compile Time Polymorphism
Code: oop.cpp, polymorphism.cpp
Readme: Oop.md
Generics is the idea to allow type (Integer, String, … etc and user-defined types) to be a parameter to methods, classes and interfaces. For example, classes like an array, map, etc, which can be used using generics very efficiently.
Before diving into Templates would be better to understand concept of Generics.
-
Generic Functions using Template / Generic Class using Template
-
Working with multi-type Generics
Code: generics.cpp
A template is a simple yet very powerful tool in C++. The simple idea is to pass the data type as a parameter so that we don’t need to write the same code for different data types.
-
Function Templates & Class Templates
Code: templates.cpp
Readme: Templates.md
Operator Overloading is a fundamental feature of C++ that allows developers to redefine the behavior of operators for user-defined types (classes and structs). This powerful mechanism enhances the expressiveness and readability of code, making user-defined types behave more like built-in types.
-
Operator overloading, use cases, examples
Code: OperatorOverloading.cpp
Readme: OperatorOverloading.md
Data structures in programming are ways to organize, store, and manage data efficiently for operations like searching, sorting, and modification. Examples include arrays, strings, linked lists, stacks, queues, trees, graphs etc. Each is designed for specific tasks to optimize performance.
-
Declaring & Initializing arrays on Stack and Heap
-
Dimensional Arrays (2D & 3D)
-
Row-Column Major formulas, Address Formulas for 1D, 2D, 3D and nD Arrays
Folder: Arrays-Representations
Address Formulas: Address-Formulas
The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index. These items can be anything from primitive types such as integers to more complex types like instances of classes.
-
Console program that create and manipulate with Array from scratch
-
Functions like Display, Append, Insert, Search, Get & Set, Max/Min, Reverse, Shift/Rotate
Code: Array.c
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
-
Characters & Character Arrays
-
Null-Termination & Mutability & Efficient Copying & Concatenation
-
std::string
Code: Strings.cpp
Readme: Strings.md
ASCII TABLE: ASCII-Table.png
Linked list is a linear data structure that allows the users to store data in non-contiguous memory locations. A linked list is defined as a collection of nodes where each node consists of two members which represents its value and a next pointer which stores the address for the next node.
-
Linked List, Nodes
-
Single & Double & Circular Linked Lists
Folder: Linked-Lists
Readme: LinkedLists.md
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed.
-
Stack implementation using std::vector<>
-
Stack implementation from scratch with manual memory management (on Heap)
A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of "First in, First out" (FIFO), where the first element added to the queue is the first one to be removed.
-
Queue implementation using array with circular two pointer approach
-
Queue implementation using Linked List
-
Deque (double-ended queue) implementation using Linked List
Tree data structure is a hierarchical structure that is used to represent and organize data in the form of parent-child relationship. The following are some real world situations which are naturally a tree.
The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.
-
General idea about trees; terminology, use cases, types etc.
-
Binary Tree implementation (number of trees using n-nodes).
-
N-ary Trees
A Binary Search Tree (or BST) is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
-
Create Binary Search Tree class from scratch
-
Undertand the main concepts and properties of BST (Catalan Number Formula, traversals, etc.)
-
Implement common methods such as search, insert, delete, successor etc.
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one.
The absolute difference between the heights of the left subtree and the right subtree for any node is known as the balance factor of the node. The balance factor for all nodes must be less than or equal to 1.
Every AVL tree is also a Binary Search Tree (Left subtree values Smaller and Right subtree values greater for every node), but every BST is not AVL Tree. The main advantage of an AVL Tree is, the time complexities of all operations (search, insert and delete, max, min, floor and ceiling) become O(Log n). This happens because height of an AVL tree is bounded by O(Log n). In case of a normal BST, the height can go up to O(n).
An AVL tree maintains its height by doing some extra work during insert and delete operations. It mainly uses rotations to maintain both BST properties and height balance.
-
Inserting & Removing nodes from AVL tree while taking care of balance factor and heights of each node
-
LL, LR, RR, RL rotations explained and implemented for unbalanced cases of the nodes
-
Visualizations for each functions with comment lines
In binary search trees we have seen the average-case time for operations like search/insert/delete is O(log N) and the worst-case time is O(N) where N is the number of nodes in the tree.
Like other Trees include AVL trees, Red Black Tree, B tree, 2-3 Tree is also a height balanced tree.
The time complexity of search/insert/delete is O(log N) .
A 2-3 tree is a B-tree of order 3.
-
implementation coming soon...
File: 2-3-Tree.cpp
Readme: 2-3-Tree.md
Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain balance, ensuring logarithmic time complexity for operations like insertion, deletion, and searching, regardless of the initial shape of the tree. Red Black Trees are self-balancing, using a simple color-coding scheme to adjust the tree after each modification.
The Red-Black Trees is less balanced compared to AVL trees, because AVL trees may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over the Red-Black Tree.
-
2 case of balancing: Recoloring & Rotation
-
Red and Black Node properties
-
Insert & Delete & Search methods with all case implementations
File: RedBlackTree.cpp
Readme: RedBlackTree.md
A Heap is a complete binary tree data structure that satisfies the heap property:
Max Heap: Every node should have the element greater or equal to it's all descendants. Min Heap: Every node should have the element less or equal to it's all descendants.
Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.
-
Max-Heap & Min-Heap Data Structure
-
Heap functions such as: MaxHeapify, extractMax, Parent, Left, Right, insert
-
Building and Sorting array using Heapify method
Code: Heap.cpp
Readme: Heap.md
Priority Queue using Binary Heap
Algorithm is a step-by-step procedure for solving a problem or accomplishing a task. In the context of data structures and algorithms, it is a set of well-defined instructions for performing a specific computational task. Algorithms are fundamental to Computer Science and play a very important role in designing efficient solutions for various problems.
Generalising Recursion
-
Behaviour of Recursion
-
Ascending & Descending Phases
-
CALLING time & RETURNING time
-
Local and Static variables in Recursion
Code: recursion.cpp
Types Of Recursion
-
Tail Recursion - Head Recursion - Tree Recursion - Indirect Recursion - Nested Recursion
Folder: Types-of-Recursion
Algorithms & Problems
Common algorithm problems using recursion vs iterative approach.
-
nCr Combination - Tower of Hanoi Problem - Factorial - Fibonacci - Power - Sum Of Natural Nums - Taylor Series
Algorithms: Recursion-Algorithms
A Sorting Algorithm is used to rearrange a given array or list of elements in an order. Selecting best sorting algoritms in a certain cases is crutial for system performans and stability.
-
Counting Sort - Bin / Bucket Sort
-
Radix Sort
-
Shell Sort
-
Folder: Sorting-Techniques
Time and Space Complexity Table: Sorting-Techniques
-
Find Duplicates - Find Max Min - Find Multiple Missing - Find Single Missing - Merge Sorted Arrays - Rotate Array - Pair Sum - removeDuplicatesFromSortedArray
Folder: Array-Algorithms
In C+, Bitwise Operators are the operators that are used to perform bit-level operations on the integers. While performing these operations, integers are considered as sequences of binary digits. These operators are useful for low-level programming, system programming, and optimizing performance.
-
AND, OR, XOR, NOT, Left Shift, Right Shift
-
hammingWeight - swapVariables - convertBinaryInLinkedListToInt (by using bitwise manipulations)
Folder: Bitwise-Operations
Readme: Bitwise.md
-
changingCase - countWordsAndVowels - findDuplicates - findDuplicatesBitwise - findStringLength - isPalindrome - reverseString - validateString - isAnagram
Folder: String-Algorithms
-
reverseLinkedList - intersectionOfLinkedLists - displayLinkedList - countNodes - findMaxMin - isSorted - removeDuplicates - mergeLinkedLists - midlleOfLinkedList - convertBinaryInLinkedListToInt
Folder: Linked-List-Algorithms
-
isValidParantheses - prefixToPostfix
Folder: Stack-Algorithms
-
implementQueueUsingStack
Folder: Queue-Algorithms
-
TraversalMethods - countNodesAndHeight - sumOfNodes - generateTreeFromTraversals - createTreeFromArray - catalanNumber - minMaxNodesFromHeight - countLeafAndNonleafNodes - invertBinaryTree - isBalancedBinaryTree - diameterOfBinaryTree - isSameTree - isSubtreeOfAnotherTree - binaryTreePaths - binaryTreeRightSideView
Folder: Binary-Tree-Algorithms
-
generateBSTFromOneTraversal - resursiveInsert - createBSTFromArray
Folder: Binary-Search-Tree-Algorithms
Also known as Priority Queues
-
kthLargestElementInStream
Folder: Heap-Algorithms
-
Depth First Search
-
Breadth First Search
Folder: BFS-DFS
Readme: BFS-DFC Readme
-
permutationString
Folder: Backtracking