Data Structures in C

Cheatsheet Content

### Introduction to Data Structures - **Definition:** A data structure is a particular way of organizing data in a computer so that it can be used efficiently. - **Why use them?** Efficient data storage, retrieval, and processing. - **Types:** Linear (Arrays, Linked Lists, Stacks, Queues) and Non-linear (Trees, Graphs). ### Arrays - **Definition:** A collection of items stored at contiguous memory locations. - **Declaration:** `dataType arrayName[arraySize];` - Example: `int arr[10];` - **Initialization:** `int arr[] = {10, 20, 30};` - **Accessing Elements:** `arrayName[index];` (0-indexed) - **Advantages:** Fast access (random access). - **Disadvantages:** Fixed size, insertion/deletion can be slow. ### Linked Lists - **Definition:** A linear collection of data elements called nodes, where each node points to the next node. - **Node Structure:** ```c struct Node { int data; struct Node* next; }; ``` - **Types:** - **Singly Linked List:** Nodes point to the next node. - **Doubly Linked List:** Nodes point to both previous and next nodes. - **Circular Linked List:** Last node points back to the first node. - **Operations:** - **Insertion:** At beginning, end, or specific position. - **Deletion:** At beginning, end, or specific position. - **Traversal:** Iterating through the list. - **Advantages:** Dynamic size, easy insertion/deletion. - **Disadvantages:** No random access, more memory usage per element (for pointers). ### Stacks - **Definition:** A linear data structure that follows the LIFO (Last In, First Out) principle. - **Operations:** - **`push(item)`:** Adds an item to the top of the stack. - **`pop()`:** Removes and returns the item from the top of the stack. - **`peek()`:** Returns the top item without removing it. - **`isEmpty()`:** Checks if the stack is empty. - **`isFull()`:** Checks if the stack is full (for array-based implementation). - **Implementations:** Array-based or Linked List-based. - **Applications:** Function calls, expression evaluation, undo/redo features. ### Queues - **Definition:** A linear data structure that follows the FIFO (First In, First Out) principle. - **Operations:** - **`enqueue(item)`:** Adds an item to the rear of the queue. - **`dequeue()`:** Removes and returns the item from the front of the queue. - **`front()`:** Returns the front item without removing it. - **`rear()`:** Returns the rear item without removing it. - **`isEmpty()`:** Checks if the queue is empty. - **`isFull()`:** Checks if the queue is full (for array-based implementation). - **Implementations:** Array-based or Linked List-based. - **Applications:** CPU scheduling, printer queues, breadth-first search. ### Trees - **Definition:** A non-linear data structure consisting of nodes in a hierarchical structure. - **Terminology:** Root, Parent, Child, Sibling, Leaf, Edge, Path, Height, Depth. - **Binary Tree:** Each node has at most two children (left and right). - **Binary Search Tree (BST):** For every node, all nodes in the left subtree are smaller, and all nodes in the right subtree are larger. - **Operations (BST):** - **`insert(key)`:** Adds a new node while maintaining BST property. - **`search(key)`:** Finds a node with a specific key. - **`delete(key)`:** Removes a node. - **Traversal:** - **Inorder:** Left -> Root -> Right (sorted output for BST) - **Preorder:** Root -> Left -> Right - **Postorder:** Left -> Right -> Root - **Applications:** File systems, databases, syntax parsing. ### Graphs - **Definition:** A non-linear data structure consisting of a finite set of vertices (nodes) and a set of edges connecting these vertices. - **Terminology:** Vertex, Edge, Degree, Path, Cycle, Connected Graph, Directed/Undirected. - **Representations:** - **Adjacency Matrix:** A 2D array where `matrix[i][j] = 1` if an edge exists between `i` and `j`, else `0`. - **Adjacency List:** An array of linked lists, where `adjList[i]` contains all vertices adjacent to vertex `i`. - **Traversal Algorithms:** - **Breadth-First Search (BFS):** Explores neighbor nodes level by level (uses a queue). - **Depth-First Search (DFS):** Explores as far as possible along each branch before backtracking (uses a stack or recursion). - **Applications:** Social networks, GPS navigation, network routing.