Codingcheff: DSA Short Notes

Time complexity refers to the amount of time an algorithm takes to complete as a function of the input size.

Space complexity is the amount of memory space required by an algorithm concerning the input size.

Data structure is a way of organizing and storing data to perform operations efficiently.

Array vs. Linked List:

Arrays are contiguous memory locations, while linked lists use pointers.
Arrays are preferable when direct access is needed, and linked lists are suitable for dynamic size and frequent insertions/deletions

Recursion is a programming technique where a function calls itself.

Tree Terminology:

a. Root: The topmost node.
b. Leaf: A node with no children.
c. Parent: A node with children.
d. Child: A node connected to a parent

Big O notation helps compare algorithms and predict their behavior with large inputs.

Abstract Data Type is a high-level description of a set of operations without specifying the implementation.

Stack vs. Queue:

Stack follows Last In First Out (LIFO), while Queue follows First In First Out (FIFO).
Stack is suitable for function call tracking, and Queue is used in task scheduling

Pointers store the memory address of variables. In data structures, they facilitate dynamic memory allocation and efficient traversal.

Tree Traversal:

Pre-order: Root, Left, Right
In-order: Left, Root, Right

Dynamic memory allocation in C involves using functions like malloc() to request memory during program execution. The process typically consists of the following steps: allocation, checking for all allocation success, Usage, deallocation

Hash tables are crucial data structures that provide efficient data retrieval and storage.

A doubly-linked list is a linked list in which each node contains a data element and two pointers, one pointing to the next node (next pointer) and another pointing to the previous node (prev pointer).

Breadth-First Search (BFS):

Traversal Order: Level-wise, exploring all neighbors at the current level before moving to the next level.
Memory Usage: More memory-intensive due to the need to store all nodes at the current level.
Implementation: Typically implemented using a queue.

Depth-First Search (DFS):

Traversal Order: Goes as deep as possible before backtracking.
Memory Usage: Less memory-intensive as it explores as far as possible along each branch before backtracking.
Implementation: Typically implemented using recursion or a stack.

Hashing is a technique that maps data to a fixed-size array called a hash table.

Linear Search when the data is unordered, or the dataset is small.

Binary Search when dealing with large, sorted datasets, as it offers faster search times. find the middle element.

Heap is a specialized tree-based data structure that satisfies the heap property.

DATA STRUCTURE data structure is a way of organizing and storing data in a computer's memory in order to perform efficient operations on that data.

Major Operations : searching, sorting, insertion, updation, deletion

Advantages of Data structures :

Efficiency : makes the programs efficient in term of time and space .

Reusability: multiple client programs can use the data structure.

Abstraction: client does not worry about the implementation part.

Linear data structure

data elements are stored in a linear or sequential order, that is, data is stored in consecutive memory locations.

Non-linear data structure

data represented by a hierarchical order. Examples of non-linear data structure include graphs, trees etc

Arrays are one of the most basic and widely used data structures in C. An array is a collection of elements of the same data type stored in contiguous memory locations

SYNTAX: data_type array_name[size] = {element1, element2, ..., elementN};

Arrays are useful because of sorting, searching, process multiple values quickly

Basic operations:

Traversal - print elements of an array

Insertion - add elements at particular index

Deletion - delete an element at particular index

Search - search an element of given index

update - update an element at particular index