0% found this document useful (0 votes)
236 views4 pages

Dsa Cheat Sheet

The document provides an overview of various data structures and algorithms, including Arrays, Linked Lists, Stacks, Queues, HashMaps, Binary Trees, and more, detailing their definitions and key methods. It also covers sorting algorithms, search algorithms, recursion, dynamic programming, greedy algorithms, and backtracking techniques. Each section outlines the fundamental operations associated with these structures and algorithms, emphasizing their applications in computing.

Uploaded by

n1shikaa3173
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
0% found this document useful (0 votes)
236 views4 pages

Dsa Cheat Sheet

The document provides an overview of various data structures and algorithms, including Arrays, Linked Lists, Stacks, Queues, HashMaps, Binary Trees, and more, detailing their definitions and key methods. It also covers sorting algorithms, search algorithms, recursion, dynamic programming, greedy algorithms, and backtracking techniques. Each section outlines the fundamental operations associated with these structures and algorithms, emphasizing their applications in computing.

Uploaded by

n1shikaa3173
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/ 4

1.

Array

• Definition: A collection of items stored at contiguous memory locations.

• Methods:

o Insert: Add element at a specific index.

o Delete: Remove element at a specific index.

o Search: Find an element by its index or value (Linear or Binary Search).

o Traversal: Access each element of the array sequentially.

2. Linked List

• Definition: A linear data structure where each element is a separate object (Node) linked
using pointers.

• Methods:

o Insert at Beginning/End: Add a node at the start/end of the list.

o Insert at Position: Add a node at a specific position.

o Delete: Remove a node from the list.

o Search: Find a node by its value.

o Traversal: Traverse from head to the end of the list.

3. Stack

• Definition: A linear data structure following the LIFO (Last In First Out) principle.

• Methods:

o Push: Add an element to the top of the stack.

o Pop: Remove and return the top element of the stack.

o Peek: Retrieve the top element without removing it.

o isEmpty: Check if the stack is empty.

o isFull: Check if the stack is full (for fixed-size stack).

4. Queue

• Definition: A linear data structure following the FIFO (First In First Out) principle.

• Methods:

o Enqueue: Add an element to the rear of the queue.

o Dequeue: Remove and return the front element.

o Peek: Retrieve the front element without removing it.

o isEmpty: Check if the queue is empty.


o isFull: Check if the queue is full (for fixed-size queue).

5. HashMap / Hash Table

• Definition: A data structure that maps keys to values for efficient lookup.

• Methods:

o Put (Insert): Insert a key-value pair into the hash table.

o Get (Search): Retrieve the value associated with a key.

o Remove: Delete the key-value pair from the table.

o ContainsKey: Check if a key exists in the table.

6. Binary Tree

• Definition: A tree data structure in which each node has at most two children (left and right).

• Methods:

o Insert: Add a node in the tree.

o Delete: Remove a node from the tree.

o Search: Find a node in the tree.

o Traversal: Visit nodes in a particular order:

▪ InOrder (Left, Root, Right)

▪ PreOrder (Root, Left, Right)

▪ PostOrder (Left, Right, Root)

7. Binary Search Tree (BST)

• Definition: A special form of binary tree where left children are smaller, and right children
are larger than the parent node.

• Methods:

o Insert: Add a node while maintaining the BST property.

o Delete: Remove a node while maintaining the BST property.

o Search: Find a node based on its value.

o Min/Max: Find the minimum/maximum value node.

o InOrder Traversal: Get elements in sorted order.

8. Heap

• Definition: A complete binary tree where each node follows the heap property (min-heap or
max-heap).

• Methods:

o Insert: Add a new element while maintaining the heap property.


o Delete: Remove the root element (for priority queues).

o Heapify: Convert an array into a heap.

o Extract Min/Max: Remove the minimum/maximum element (root).

9. Graph

• Definition: A collection of nodes (vertices) and edges connecting them.

• Methods:

o Add Edge: Add an edge between two nodes.

o Remove Edge: Remove an edge between two nodes.

o Search (DFS/BFS): Traverse the graph using Depth-First Search or Breadth-First


Search.

o Shortest Path: Find the shortest path between two vertices (Dijkstra’s Algorithm,
Bellman-Ford, etc.).

10. Sorting Algorithms

• Bubble Sort: Repeatedly swap adjacent elements if they are in the wrong order.

• Selection Sort: Repeatedly select the smallest element and move it to the correct position.

• Insertion Sort: Build the sorted array one element at a time by inserting elements into their
correct position.

• Merge Sort: Divide the array into halves, sort each half, and merge them back.

• Quick Sort: Select a pivot, partition the array, and recursively sort the subarrays.

• Heap Sort: Convert the array into a heap, then repeatedly extract the minimum/maximum
element.

11. Search Algorithms

• Linear Search: Sequentially check each element until the target is found.

• Binary Search: Efficiently search a sorted array by dividing the search interval in half.

• Depth First Search (DFS): Explore each branch of a graph as deeply as possible before
backtracking.

• Breadth First Search (BFS): Explore the neighbor nodes at the present depth level before
moving on to nodes at the next depth level.

12. Recursion

• Definition: A function that calls itself to solve a smaller instance of the problem.

• Common Patterns:

o Base Case: Condition under which recursion stops.

o Recursive Case: Condition under which the function calls itself.


o Divide & Conquer: Solve the problem by breaking it into subproblems (e.g., merge
sort, quick sort).

13. Dynamic Programming

• Definition: An optimization technique used to avoid recalculating results by storing them.

• Methods:

o Memoization: Store results of subproblems to avoid recomputation.

o Tabulation: Use a table to store intermediate results and solve the problem bottom-
up.

14. Greedy Algorithm

• Definition: A problem-solving technique where you pick the locally optimal choice at each
step with the hope of finding a global optimum.

• Examples: Dijkstra’s Algorithm, Kruskal’s Algorithm for Minimum Spanning Tree.

15. Backtracking

• Definition: A recursive technique used to solve problems by trying out different possibilities
and undoing (backtracking) when a solution fails.

• Example: Solving puzzles like Sudoku, N-Queens Problem.

You might also like