Basic Data Structures in C

Basic Data Structures

• C provides fundamental data structures for organizing and manipulating data.
• These structures help in efficient storage, retrieval, and manipulation of information.
• Common basic data structures in C include arrays, structs, and pointers.
• Arrays are used to store a collection of elements of the same data type, accessed using an index.
• Structs allow grouping of variables of different data types under a single name.
• Pointers hold memory addresses, enabling indirect referencing and dynamic memory allocation.

Arrays

• Arrays are contiguous blocks of memory.
• Elements are stored sequentially.
• Accessing elements is achieved using an index, making it fast to retrieve an element at a known position.
• Size of an array is fixed at compile time.
• Example: int numbers[5] = {1, 2, 3, 4, 5}; defines an array 'numbers' with 5 integer elements.

Structs

• Structs group together variables of potentially different data types.
• Offer a way to bundle related data.
• Structs enhance code organization and reusability.
• Example: struct student {char name[50]; int age; float gpa; }; defines a struct named 'student', containing name, age, and gpa.

Pointers

• Pointers store memory addresses.
• Used to manipulate data indirectly.
• Allow dynamic memory allocation.
• Can be used to pass parameters that can be modified by the function.
• Example: int *ptr; ptr = &age; assigns the address of variable age to the pointer ptr.

Dynamic Memory Allocation

• malloc(), calloc(), and realloc() are functions for dynamic memory management.
• Enables allocating memory during runtime.
• Crucial for handling data whose size isn't known beforehand.
• malloc() allocates memory and returns a pointer.
• calloc() initializes memory to 0 after allocation.
• realloc() changes the size of previously allocated memory.
• Example: int *arr = (int*) malloc(5 * sizeof(int)); allocates memory for 5 integers.
• Important to free() allocated memory to prevent memory leaks.

Linked Lists

• Linked lists are dynamic data structures.
• Each element (node) in the list contains: The data and a pointer to the next node.
• Concatenated elements form a series.
• Support insertion and deletion of elements at any position without requiring shifting to other elements.
• Easier to insert or delete elements in a list than in an array.

Stacks

• Stacks are last-in, first-out (LIFO) data structures.
• Elements are added and removed from the top of the stack.
• Common in function calls, expression evaluation, backtracking algorithms.
• Functions like push (add to top) and pop (remove from top) operate on a stack.

Queues

• Queues are first-in, first-out (FIFO) data structures.
• Elements are added at the rear (enqueue) and removed from the front (dequeue).
• Used in tasks where things need to be processed in the order they arrive.
• Implemented using arrays or linked lists.

Trees

• Trees are hierarchical data structures.
• Each node can have multiple children.
• Root node is the top of the hierarchy.
• Used for representing hierarchical data, like file systems or organizational charts.

Graphs

• Graphs consist of nodes (vertices) and edges connecting them.
• Represent relationships between objects.
• Commonly used in social networks, road maps, and other networking scenarios.
• Can be directed or undirected.

Hash Tables

• Hash tables use hashing to store key-value pairs.
• Hashing converts keys into indices for faster retrieval.
• Used for fast lookups but performance depends on the hash function quality.
• Can handle collisions effectively to maintain efficient lookups if necessary, potentially by using chaining
• Hash table structure often involves arrays or linked lists.