Data Structures: Arrays, Linked Lists, Hashing

• Data structures are ways to organize and store data in a computer so that it can be accessed and used efficiently

Types of Data Structures

• Arrays are collections of elements of the same data type, stored in contiguous memory locations
• Linked lists are sequences of elements (nodes), where each element points to the next one
• Stacks are LIFO (Last In, First Out) structures where the last element added is the first one removed
• Queues are FIFO (First In, First Out) structures where the first element added is the first one removed
• Trees are hierarchical structures with a root node and child nodes, used for representing hierarchical relationships
• Graphs are collections of nodes (vertices) connected by edges, used for representing relationships between objects

Hashing

• Hashing is a technique used to map data of arbitrary size to fixed-size values using a hash function
• Hash functions take an input (key) and return a unique index that maps to a location within a hash table
• Hash tables (hash maps) are data structures that use hash functions to store and retrieve data efficiently
• Collision occurs when two different keys produce the same hash value
• Collision resolution techniques include separate chaining (linked lists) and open addressing (probing)

Forest

• A forest is a collection of one or more trees
• In a forest, each tree is a disjoint data structure
• Forests are used to implement data structures like disjoint sets

Functions

• A function is a block of organized, reusable code that performs a specific task
• Functions provide modularity and code reuse
• A function has a name, a list of parameters (input), and a return value (output)

Function Declaration

• The function declaration specifies the function's name, return type, and parameters
• return_type function_name(parameter_list);

Function Definition

• The function definition provides the actual implementation of the function
• It includes the function body, which contains the statements to be executed
• return_type function_name(parameter_list) { // statements; }

Recursion

• Recursion is a programming technique where a function calls itself in order to solve a problem
• Recursive functions break down a problem into smaller, self-similar subproblems
• Base case: A condition that terminates the recursive calls and returns a value directly
• Recursive step: The function calls itself with a modified input, moving towards the base case
• Without a proper base case, a recursive function can result in infinite loops

Parameter Passing

• Parameter passing is the mechanism used to pass values (arguments) to a function when it is called
• Pass by value: The value of the variable is copied into the function parameter
• Changes made to the parameter inside the function does not affect the original variable
• Pass by reference: The address of the variable is passed to the function
• Changes made to the parameter inside the function do affect the original variable
• Pass by address: The pointer of the variable is passed to the function
• Changes made to the parameter inside the function do affect the original variable