DSA Reviewer.docx

**Data Structure --** is a way of collecting and organizing elements or items of data. **Algorithm** -- is a finite set of instructions or procedures, written in order to solve a certain predefined task in programming algorithm. **List --** is a collection of an ordered sequence of items. It might...

**Data Structure --** is a way of collecting and organizing elements or items of data. **Algorithm** -- is a finite set of instructions or procedures, written in order to solve a certain predefined task in programming algorithm. **List --** is a collection of an ordered sequence of items. It might have properties for example, **being sorted or unsorted , having duplicate or being unique values** **Pointers --** use to store addresses of a variable. **Head** -- First node **Null** -- Last node **Time Complexity** -- it is a way to signify the amount of time needed by the program to run to completion **Space Complexity** -- it is the amount of memory space necessary by the algorithm, during the course of its execution. **Instruction Space --** space required to store the executable version of the program. **Data Space** -- space required to store all the constant and variable value **Environmental Space** -- space necessary to store the environment information needed to restart the suspended function. **Linear data structure --** Elements are connected and accessed in sequential order by means of logically or sequence memory locations. Example : stacks, queues, and link list **Non- Linear data structure --** Data items are not arranged in sequential order. **Primitive data structures --** A data structure that cannot be decomposed to other data structure **Non -- Primitive data structure --** it is more complicated data structure and is derived from one or more primitive data structure. A **LinkedList** is a linear data structure where elements are stored in nodes. Each node contains two main parts: 1\. **Data**: The value or content of the node. 2.**Pointer**: A reference or pointer to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node points to the next one, forming a chain-like structure. Types of Linked Lists 1\. **Singly Linked List**: Each node points to the next node and the last node points to null. 2\. **Doubly Linked List**: Each node has two pointers, one to the next node and one to the previous node. 3\. **Circular Linked List:** The last node points back to the first node, forming a circle. Basic Structure of a Singly Linked List **\[Data \| Next\] -\> \[Data \| Next\] -\> \[Data \| Next\] -\> NULL** Linked List vs. Array Memory Allocation: Linked lists use dynamic memory allocation, so their size can grow or shrink at runtime. Insertions and Deletions: Inserting or deleting elements in a linked list is more efficient than in arrays because it only requires changing pointers rather than shifting elements. **Stack** -- is a data structure that can hold many elements. LIFO (Last in, First Out). **Basic Concepts of Stack** 1\. **Push**: Add an element to the top of the stack. 2\. **Pop**: Remove and return the top element from the stack. 3\. **Peek**: View the top element without removing it. 4\. **isEmpty**: Check if the stack is empty. 5.**isFull**: Check if the stack is full 6\. **Size**: Get the number of elements currently in the stack. **Queues** -- is a linear data structure that follow the FIFO (First in, First Out). **Key Terms:** **Enqueue --** Adding an element to the back of the queue. **Dequeue --** Removing an element from the front of the queue. **Front --** The position of the first element in the queue. **Rear --** The position of the last element in the queue. **Empty --** Indicates whether the queue has no elements. **Full --** Indicates whether the queue has reached its capacity. **Types of Queues** **Simple Queue** -- A basic linear queue with FIFO order. **Circular Queue** -- A queue that connects the last position back to the first position making it circular. **Priority Queue --** Elements are removed based on priority rather than the order they were added. **Double Ended Queue(Deque) --** Elements can be added or removed from both the front and the back. **Basic Operations** **Enqueue** -- Insert an element at the rear **Dequeue** -- Remove an element from the front **Peek/Front** -- View the element without removing it **IsEmpty** -- Check if the queue is empty. **isFull** -- Check if the queue is full