# Data Structures A data structure is a specific way of organizing and storing data in a computer so that it can be accessed and modified efficiently. They provide a framework for managing data and impact the performance of operations like *insertion*, *deletion*, and *retrieval*. Data structures are generally categorized into: 1. **Primitive Data Structures:** Basic types like integers and floats. 2. **Non-Primitive Data Structures:** Complex structures like Arrays, Lists, and Trees. * **Linear:** Data elements are arranged sequentially (e.g., Arrays, Stacks). * **Non-Linear:** Data elements are attached hierarchically or in a network (e.g., Trees, Graphs). ### 2.1.1 Arrays An array is the simplest data structure, storing elements of the *same size* in *contiguous memory locations*. Each location is identified by an index. - **Characteristics:** - Elements are stored sequentially in memory. - Fast access to elements using an index. - Efficient memory usage as no extra metadata is required per element. - **Limitations:** - **Fixed Size:** The size must be declared at the start (Static). - **Costly Resizing:** Changing the size often requires creating a new, larger array and copying all elements. - **Homogeneous:** Can only store elements of the same data type. - **Types of Arrays:** - **One-Dimensional (1-D) Array:** A single list of elements accessible by a single index. - **Two-Dimensional (2-D) Array:** Also known as a *matrix* or *table*, where elements are stored in rows and columns. An element is accessed using two indexes (row and column). ### 2.1.2 Linked Lists A linear data structure where elements (called *nodes*) are connected using *pointers*. Each node contains data and a reference (memory address) to the next node. - **Characteristics:** - **Dynamic Size:** Can grow or shrink as needed. - **Efficient Insertion/Deletion:** Nodes can be easily added or removed without reallocating the entire structure. - **Heterogeneous:** Can store different types of data. - **Types of Linked Lists:** - **Singly Linked List:** Each node contains data and a pointer to the *next* node. Traversal is unidirectional. The last node points to `NULL`. - **Doubly Linked List:** Each node contains data, a pointer to the *next* node, and a pointer to the *previous* node. This allows for bidirectional traversal. - **Circular Linked List:** The last node's pointer links back to the first node, forming a loop. Traversal can continue indefinitely. Can be either singly or doubly linked. ### 2.1.3 Stacks A linear data structure that follows the **LIFO (Last-In, First-Out)** principle. The most recently added element is the first one to be removed. Operations occur only at the *top* of the stack. - **Basic Operations:** - **Push:** Add an element to the top. - **Pop:** Remove the element from the top. - **Top:** Return the top element without removing it. - **IsEmpty:** Check if the stack is empty. - **IsFull:** Check if the stack is full. ### 2.1.4 Queues A linear data structure that follows the **FIFO (First-In, First-Out)** principle. The first element added is the first one to be removed. Operations occur at both ends: insertion at the *rear* and deletion from the *front*. - **Basic Operations:** - **Enqueue:** Add an element to the rear of the queue. - **Dequeue:** Remove an element from the front of the queue. - **Front:** Return the front element without removing it. - **IsEmpty:** Check if the queue is empty. - **IsFull:** Check if the queue is full. ### 2.1.5 Graphs A non-linear data structure consisting of *nodes* (called **vertices**) connected by **edges**. Graphs are used to model complex relationships and networks. - **Basic Operations:** - **Add Vertex:** Add a new node. - **Add Edge:** Create a connection between two nodes. - **Remove Vertex/Edge:** Delete a node or an edge. - **Traversal:** Visit all nodes in a specific order. - **Types of Graphs:** - **Connected Graph:** A graph where there is at least one path between every pair of vertices. - **Directed Graph:** A graph where edges have a direction, indicating a one-way relationship. ### 2.1.6 Trees A hierarchical data structure consisting of nodes connected by edges. It represents a parent-child relationship. - **Terminology:** - **Root:** The topmost node. - **Parent:** A node that has one or more child nodes. - **Child:** A node that has a parent node. - **Leaf:** A node with no children. - **Edge:** The link between a parent and a child. #### Tree Traversal The process of visiting all the nodes in a tree in a systematic way. - **In-Order Traversal:** (Left, Root, Right) 1. Traverse the left subtree. 2. Visit the root node. 3. Traverse the right subtree. - *Example Order:* 4 -> 2 -> 5 -> 1 -> 3 -> 6 - *Use Case:* Visits nodes in ascending order in a Binary Search Tree (BST). - **Pre-Order Traversal:** (Root, Left, Right) 1. Visit the root node. 2. Traverse the left subtree. 3. Traverse the right subtree. - *Example Order:* 1 -> 2 -> 4 -> 5 -> 3 -> 6 - *Use Case:* Useful for creating a copy of the tree. - **Post-Order Traversal:** (Left, Right, Root) 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit the root node. - *Example Order:* 4 -> 5 -> 2 -> 6 -> 3 -> 1 - *Use Case:* Useful for deleting nodes from a tree. ## Possible Questions/Answers - **Q:** What is a data structure? **A:** A method for organizing and storing data to allow for efficient access and modification in computer programs. - **Q:** What is the main difference between an Array and a Linked List? **A:** An array has a fixed size and stores elements in contiguous memory, allowing fast indexed access. A linked list has a dynamic size and stores elements non-contiguously using pointers, making insertions and deletions more efficient. - **Q:** Differentiate between a Stack and a Queue. **A:** A Stack operates on a **LIFO (Last-In, First-Out)** principle, where the last element added is the first to be removed. A Queue operates on a **FIFO (First-In, First-Out)** principle, where the first element added is the first to be removed. - **Q:** What is a leaf node in a tree? **A:** A node in a tree that has no children. ## Summary - Data structures are fundamental for organizing data efficiently in programming. - **Linear Structures** like Arrays, Linked Lists, Stacks, and Queues store data sequentially. - **Non-Linear Structures** like Trees and Graphs represent hierarchical or network relationships. - The choice of data structure depends on the specific requirements of the application, such as the need for fast access, dynamic sizing, or efficient insertion/deletion. | Data Structure | Principle | Key Feature | Common Use Case | | :--- | :--- | :--- | :--- | | **Array** | N/A | Fixed size, contiguous memory, fast indexed access | Storing a collection of fixed-size elements | | **Linked List** | N/A | Dynamic size, efficient insertion/deletion | Implementing stacks, queues, dynamic lists | | **Stack** | LIFO | Operations at one end (top) | Function call management, undo features | | **Queue** | FIFO | Operations at two ends (front/rear) | Task scheduling, print job management | | **Tree** | Hierarchical | Root, parent-child nodes | File systems, database indexing, HTML DOM | | **Graph** | Network | Vertices and edges | Social networks, mapping, network routing | Mastery of data structures is crucial for developing efficient algorithms and is a cornerstone of **computational thinking**, aiding in problem decomposition and algorithmic design. For further evaluation of these structures, see .