Selecting and Manipulating Data Structures

# Selecting and Manipulating Data Structures ## Objectifs et prérequis This chapter aims to equip Lower Sixth students with the ability to select, implement, and manipulate appropriate data structures for solving computational problems. Students will learn to differentiate between primitive and composite data types, understand memory allocation principles, and apply repetition structures to process arrays, records, linked lists, and hash tables. By the end of this chapter, students will be able to analyze problem requirements, choose optimal data structures, and write correct, efficient code to store, retrieve, and modify data. **Prerequisites**: - Proficiency in basic programming constructs (variables, assignment, input/output, selection structures). - Understanding of algorithms and pseudocode. - Familiarity with primitive data types (integer, real, boolean, character) from prior study. - Ability to trace simple programs and identify variables and their types. --- ## I. Integration Activity The integration activity serves as a contextual bridge to motivate the study of data structures. It presents a real-world scenario where inefficient data handling leads to performance or correctness issues, prompting the need for structured data management. > **To retain**: Data structures are not merely syntactic conveniences; they are essential for organizing data in ways that align with the operations required by an algorithm. **Scenario**: A school administration system needs to store student records (name, age, grade, subjects). Initially, the programmer uses separate variables for each student: `name1`, `age1`, `grade1`, `subject1`, `name2`, `age2`, etc. As the number of students grows, managing these variables becomes unwieldy. Adding a new student requires declaring new variables; searching for a student by name requires checking each pair of variables sequentially; updating a grade requires knowing the exact variable names. This approach lacks scalability and maintainability. **Activity Task**: Students are asked to: 1. List the problems with the current approach (scalability, readability, maintainability). 2. Propose a better way to group related data for each student. 3. Suggest how to store multiple such grouped items for efficient access. 4. Predict what operations will be needed (add student, find student by name, update grade, list all students). **Resolution**: The activity leads students to recognize the need for: - A way to group related attributes (name, age, grade, subjects) into a single unit → **Record**. - A way to store multiple such units in an ordered collection → **Array** or **List**. - The need for repetition to process each unit → **Loops**. This activity naturally transitions into the study of primitive types as building blocks, then records, then arrays, and finally more complex structures like linked lists and hash tables. **Corrected Exercise**: *Problem*: A program stores the heights of 10 students in variables `h1` to `h10`. Write pseudocode to find the tallest student using only these variables. *Solution*: ``` maxHeight ← h1 IF h2 > maxHeight THEN maxHeight ← h2 IF h3 > maxHeight THEN maxHeight ← h3 ... IF h10 > maxHeight THEN maxHeight ← h10 OUTPUT maxHeight ``` *Critique*: This approach is tedious, error-prone, and not scalable. For 100 students, 100 lines are needed. *Improved Approach*: Use an array `height[1..10]` and a loop: ``` maxHeight ← height[1] FOR i FROM 2 TO 10 IF height[i] > maxHeight THEN maxHeight ← height[i] END IF END FOR OUTPUT maxHeight ``` This demonstrates why arrays and loops are essential. --- ## II. Primitive Data Types Primitive data types are the basic building blocks of data in a programming language. They are predefined by the language and represent single values. Their size and format are determined by the language implementation and the underlying hardware. **Definition**: A primitive data type is a basic type provided by a programming language, representing a single value, and not composed of other types. **Common Primitive Types**: - **Integer (`int`)**: Whole numbers (positive, negative, zero). Size: typically 2 or 4 bytes. Range: e.g., -32,768 to 32,767 (16-bit) or -2,147,483,648 to 2,147,483,647 (32-bit). - **Real / Float (`float`, `double`)**: Numbers with fractional parts. `float`: ~6-7 decimal digits precision, 4 bytes. `double`: ~15 decimal digits precision, 8 bytes. - **Boolean (`bool`)**: Logical values: `true` or `false`. Typically 1 byte. - **Character (`char`)**: Single alphanumeric or symbol. Usually 1 byte (ASCII or UTF-8 encoding). **Properties**: - **Size**: Fixed memory footprint (in bytes). - **Range**: Minimum and maximum values representable. - **Precision**: For reals, the number of significant digits. - **Default Value**: Often zero for numerics, `false` for boolean, `'\0'` or space for char (language-dependent). - **Operations**: Arithmetic (+, -, *, /, %), relational (<, >, ==, !=), logical (&&, ||, !) for booleans. **Examples**: - `int age = 16;` → stores the integer 16. - `float gpa = 3.75;` → stores the real number 3.75. - `bool isPassed = true;` → stores the boolean value true. - `char grade = 'A';` → stores the character 'A'. **Memory Allocation**: Each primitive variable occupies a fixed, contiguous block of memory. The compiler allocates space based on the type. For example, an `int` might occupy 4 bytes at address 1000–1003. **Corrected Exercise 1**: *Problem*: Determine the memory size and range for a 16-bit signed integer. *Solution*: - Size: 16 bits = 2 bytes. - Range: $-2^{15}$ to $2^{15} - 1$ = $-32768$ to $32767$. *Verification*: $2^{15} = 32768$, so negative range: -32768 to -1 (32768 values), zero and positive: 0 to 32767 (32768 values), total 65536 = $2^{16}$ values. **Corrected Exercise 2**: *Problem*: A program uses `float` to represent currency. Why is this problematic? Give an example. *Solution*: Floating-point types cannot represent all decimal fractions exactly due to binary representation. For example, 0.1 in decimal is a repeating fraction in binary. *Example*: ``` float price = 0.10; float total = 0.0; FOR i FROM 1 TO 10 total ← total + price END FOR OUTPUT total ``` *Expected*: 1.00 *Actual*: Often 0.999999 or 1.000001 due to rounding errors. *Better*: Use integers representing cents (e.g., 10 for $0.10) or a dedicated decimal type if available. **Corrected Exercise 3**: *Problem*: Write a pseudocode function that takes a `char` input and returns `true` if it is an uppercase letter, `false` otherwise. *Solution*: ``` FUNCTION isUpper(c: char) RETURNS bool IF c >= 'A' AND c <= 'Z' THEN RETURN true ELSE RETURN false END IF END FUNCTION ``` *Explanation*: Relies on ASCII ordering where 'A' to 'Z' are consecutive. --- ## III. Arrays An array is a collection of elements of the same primitive or composite data type, stored in contiguous memory locations, and accessed using an index. **Definition**: An array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key, stored in contiguous memory. **Properties**: - **Homogeneous**: All elements are of the same type. - **Indexed**: Elements accessed via integer indices (usually starting at 0 or 1). - **Contiguous Storage**: Elements stored sequentially in memory. - **Fixed Size**: Size is declared at creation and cannot be changed (in static arrays). - **Direct Access**: Access to any element is $O(1)$ time. **Declaration and Initialization (Pseudocode)**: ``` TYPE arrayName[SIZE] // e.g., INT scores[5] REAL temperatures[12] CHAR grades[30] ``` Initialization: ``` INT scores[5] ← [85, 90, 78, 92, 88] // or element-wise: scores[0] ← 85 scores[1] ← 90 ... ``` **Memory Layout**: For an array `A[0..n-1]` of type `T` with size `s` bytes per element: - Address of `A[i]` = Base Address + $i \times s$ - Example: `int scores[5]` (4 bytes/element), base address 2000: - `scores[0]` at 2000–2003 - `scores[1]` at 2004–2007 - `scores[4]` at 2016–2019 **Operations**: - **Traversal**: Visit each element once (using a loop). - **Search**: Find an element with a given value (linear search). - **Insertion**: Add an element at a position (requires shifting). - **Deletion**: Remove an element (requires shifting). - **Update**: Modify the value at an index. **Corrected Exercise 1**: *Problem*: Declare an array to store the monthly rainfall (in mm) for a year. Initialize it with sample data: [120, 95, 110, 80, 70, 60, 50, 55, 90, 130, 160, 140]. Find the month with the highest rainfall. *Solution*: ``` REAL rainfall[12] ← [120, 95, 110, 80, 70, 60, 50, 55, 90, 130, 160, 140] INT maxIndex ← 0 FOR i FROM 1 TO 11 IF rainfall[i] > rainfall[maxIndex] THEN maxIndex ← i END IF END FOR OUTPUT "Month ", maxIndex + 1, " has the highest rainfall: ", rainfall[maxIndex], " mm" // Output: Month 11 has the highest rainfall: 160 mm ``` **Corrected Exercise 2**: *Problem*: Given array `A[0..4] ← [3, 7, 2, 9, 5]`, write pseudocode to reverse the array in place. *Solution*: ``` INT left ← 0 INT right ← 4 WHILE left < right INT temp ← A[left] A[left] ← A[right] A[right] ← temp left ← left + 1 right ← right - 1 END WHILE // Result: A ← [5, 9, 2, 7, 3] ``` **Corrected Exercise 3**: *Problem*: Why is inserting an element at the beginning of an array inefficient? *Solution*: Inserting at index 0 requires shifting all existing elements one position to the right to make space. For an array of size $n$, this takes $O(n)$ time. *Example*: Insert `X` at start of `[A, B, C, D]`: 1. Shift D to index 4 → `[A, B, C, D, D]` 2. Shift C to index 3 → `[A, B, C, C, D]` 3. Shift B to index 2 → `[A, B, B, C, D]` 4. Shift A to index 1 → `[A, A, B, C, D]` 5. Set index 0 to X → `[X, A, B, C, D]` This is inefficient compared to linked lists for frequent front insertions. --- ## IV. Records A record (also called a struct or structure) is a composite data type that groups together related data items of potentially different types under a single name. **Definition**: A record is a user-defined data type that combines one or more fields, each of which can be of a different data type, into a single unit. **Properties**: - **Heterogeneous**: Fields can be of different types (int, float, char, etc.). - **Named Access**: Fields accessed by name, not index. - **Encapsulation**: Related data is bundled logically. - **Memory Layout**: Fields stored contiguously; padding may be added for alignment. - **Fixed Structure**: Number and types of fields fixed at definition. **Declaration (Pseudocode)**: ``` TYPE StudentRecord STRING name INT age REAL gpa CHAR grade END TYPE ``` Usage: ``` VAR student1: StudentRecord student1.name ← "Alice" student1.age ← 16 student1.gpa ← 3.8 student1.grade ← 'A' ``` **Memory Allocation**: The total size is the sum of the sizes of its fields, possibly increased by padding to meet alignment requirements (e.g., aligning integers on 4-byte boundaries). *Example*: - `name`: STRING (assume 20 bytes for simplicity) - `age`: INT (4 bytes) - `gpa`: REAL (4 bytes) - `grade`: CHAR (1 byte) - Raw sum: 20 + 4 + 4 + 1 = 29 bytes - With padding (to align next field on 4-byte boundary after `grade`): 3 bytes padding → total 32 bytes. **Operations**: - **Creation**: Declare a variable of the record type. - **Field Access**: Use dot notation: `record.fieldName`. - **Assignment**: Copy values between records of same type (field-by-field). - **Comparison**: Compare corresponding fields (often requires explicit code). **Corrected Exercise 1**: *Problem*: Define a record type for a book in a library: title (string, max 50 chars), author (string, max 30 chars), year published (int), ISBN (string, 13 chars), available (boolean). *Solution*: ``` TYPE BookRecord STRING title[50] STRING author[30] INT year STRING isbn[13] BOOL available END TYPE ``` **Corrected Exercise 2**: *Problem*: Given the `StudentRecord` type above, write pseudocode to input data for one student and print their details if GPA > 3.5. *Solution*: ``` VAR s: StudentRecord INPUT s.name INPUT s.age INPUT s.gpa INPUT s.grade IF s.gpa > 3.5 THEN OUTPUT "Name: ", s.name OUTPUT "Age: ", s.age OUTPUT "GPA: ", s.gpa OUTPUT "Grade: ", s.grade END IF ``` **Corrected Exercise 3**: *Problem*: Compare arrays and records. When would you use each? *Solution*: | Feature | Array | Record | |---------|-------|--------| | Homogeneity | Homogeneous (same type) | Heterogeneous (different types) | | Access | By index (numeric) | By field name | | Use Case | List of similar items (e.g., scores, temperatures) | Group related attributes of an entity (e.g., student, book) | | Memory | Contiguous, uniform elements | Contiguous, possibly padded fields | *Use an array* when you need a collection of identical data types accessed by position. *Use a record* when you need to represent a single entity with multiple distinct attributes. --- ## V. Data Types, Memory Allocation and Data Structures This lesson synthesizes how primitive types, arrays, and records relate to memory and the broader concept of data structures. **Definition**: A data structure is a particular way of organizing data in a computer so that it can be used efficiently. It encompasses the data values, the relationships between them, and the functions or operations that can be applied to the data. **Hierarchy**: - **Primitive Types**: Basic, indivisible units (int, float, bool, char). - **Composite Types**: Built from primitives: - **Arrays**: Homogeneous collections. - **Records**: Heterogeneous groupings. - **Abstract Data Types (ADTs)**: Logical descriptions of data and operations (e.g., List, Stack, Queue), independent of implementation. - **Implementations**: Concrete realizations using arrays, records, pointers (e.g., Array-based List, Linked List). **Memory Allocation Principles**: - **Static Allocation**: Memory size fixed at compile time (e.g., global variables, static arrays). - **Dynamic Allocation**: Memory allocated at runtime (e.g., using `new` or `malloc`). Essential for data structures whose size changes (like linked lists). - **Stack vs Heap**: - **Stack**: For static/local variables; LIFO; fast; limited size. - **Heap**: For dynamic allocation; managed manually (or via garbage collector); larger; slower access. *Primitive variables and record fields are often stack-allocated if local; arrays can be stack or heap; linked list nodes are heap-allocated.* **Relationship**: Data structures are built by combining primitive types and using mechanisms like arrays (for contiguous storage) or pointers/references (for non-contiguous, linked structures). The choice affects time and space complexity of operations. > **To retain**: The efficiency of an algorithm depends not only on its logic but also on the underlying data structure used to store and access data. **Corrected Exercise 1**: *Problem*: Explain why a programmer might choose to implement a list using an array versus using linked nodes. *Solution*: - **Array-based List**: - Pros: $O(1)$ access by index, cache-friendly (contiguous), simple. - Cons: Fixed size (or costly resizing), $O(n)$ insertion/deletion at front/middle. - Best for: When size is known and stable, and random access is frequent. - **Linked List**: - Pros: Dynamic size, $O(1)$ insertion/deletion at known position (with pointer), no wasted space from pre-allocation. - Cons: $O(n)$ access by index, extra memory for pointers, poor cache locality. - Best for: Frequent insertions/deletions, unknown or varying size, sequential access dominant. **Corrected Exercise 2**: *Problem*: Calculate the memory required for an array of 100 `StudentRecord` instances, assuming each record uses 32 bytes (as previously estimated with padding). *Solution*: Total memory = Number of elements × Size per element = 100 × 32 bytes = 3200 bytes = 3.125 KB *Note*: This assumes no additional overhead for the array itself (just the elements). **Corrected Exercise 3**: *Problem*: Distinguish between static and dynamic data structures with examples. *Solution*: | Characteristic | Static Data Structure | Dynamic Data Structure | |----------------|------------------------|-------------------------| | Size | Fixed at compile/runtime creation | Can grow/shrink during execution | | Memory Allocation | Usually static (stack/global) | Usually dynamic (heap) | | Example | Array of fixed size 100 | Linked List, Dynamic Array (e.g., ArrayList) | | Flexibility | Low | High | *Example Static*: `int scores[50];` *Example Dynamic*: A linked list where nodes are added/removed as needed. --- ## VI. Linked Lists A linked list is a linear data structure where elements are not stored in contiguous memory locations; instead, each element (node) contains a data field and a reference (pointer) to the next node in the sequence. **Definition**: A linked list is a sequence of nodes where each node stores data and a reference to the next node. The first node is accessed via a head pointer; the last node points to null. **Properties**: - **Dynamic Size**: Can grow and shrink during execution. - **Non-contiguous Storage**: Nodes can be scattered in memory. - **Sequential Access**: To access the $i$-th node, must traverse from head through $i-1$ nodes → $O(n)$ time. - **Efficient Insertion/Deletion**: At known position (given pointer to node), $O(1)$ time. - **Extra Overhead**: Each node requires storage for a pointer (typically 4 or 8 bytes). - **Types**: Singly linked (next pointer only), doubly linked (prev and next), circular. **Node Structure (Pseudocode)**: ``` TYPE ListNode DATA data LISTNode next END TYPE ``` *DATA* can be a primitive type or a record. **Operations**: - **Traversal**: Start at head, follow `next` pointers until null. - **Search**: Traverse and compare data. - **Insertion**: - At head: Create new node, set its `next` to current head, update head. - After a given node: Create new node, set its `next` to given node’s `next`, set given node’s `next` to new node. - At tail: Traverse to last node, then insert after it (or maintain tail pointer). - **Deletion**: - At head: Set head to head→next. - After a given node: Set given node’s `next` to given node→next→next. - Requires finding the node beforehand (O(n) search unless pointer known). **Memory Allocation**: Each node is dynamically allocated (e.g., on the heap). For a list of $n$ nodes: - Memory = $n \times (size(data) + size(pointer))$ - Example: `int data` (4 bytes), pointer (4 bytes on 32-bit system) → 8 bytes/node. For 100 nodes: 800 bytes. **Corrected Exercise 1**: *Problem*: Write pseudocode to insert a new node with value `val` at the head of a singly linked list. Assume `head` points to the first node (or null if empty). *Solution*: ``` FUNCTION insertAtHead(head: ListNode, val: DATA) RETURNS ListNode VAR newNode: ListNode newNode.data ← val newNode.next ← head RETURN newNode END FUNCTION // Usage: head ← insertAtHead(head, 5) ``` **Corrected Exercise 2**: *Problem*: Write pseudocode to delete the first node containing a specific value `target` from a singly linked list. Return the new head. *Solution*: ``` FUNCTION deleteNode(head: ListNode, target: DATA) RETURNS ListNode IF head IS NULL THEN RETURN NULL END IF IF head.data = target THEN VAR temp ← head head ← head.next // In languages with manual memory: free(temp) RETURN head END IF VAR current ← head WHILE current.next IS NOT NULL AND current.next.data ≠ target current ← current.next END WHILE IF current.next IS NOT NULL THEN VAR temp ← current.next current.next ← current.next.next // free(temp) END IF RETURN head END FUNCTION ``` **Corrected Exercise 3**: *Problem*: Compare linked lists and arrays for the operation of inserting an element at the beginning. *Solution*: | Operation | Array | Linked List | |-----------|-------|-------------| | Insert at beginning | $O(n)$ (shift all elements) | $O(1)$ (create node, update head) | | Access by index | $O(1)$ | $O(n)$ (traverse) | | Memory overhead | None (just data) | Pointer per node | | Size flexibility | Fixed (static) or costly resize | Dynamic | *Conclusion*: Linked lists are superior for frequent insertions/deletions at the head; arrays are better for frequent random access. **Corrected Exercise 4**: *Problem*: A linked list stores integers: 10 → 20 → 30 → NULL. Show the state after inserting 5 at the head. *Solution*: - Initial: `head` → [10| →] → [20| →] → [30| →] → NULL - After insertAtHead(5): - New node: [5| →] - Set new node’s `next` to old head → [5| →] → [10| →] → [20| →] → [30| →] → NULL - Update `head` to point to new node. - Final: `head` → [5| →] → [10| →] → [20| →] → [30| →] → NULL --- ## VII. Hash Tables A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. **Definition**: A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index (hash code) into an array of buckets, where the value associated with the key is stored. **Properties**: - **Key-Value Storage**: Each entry consists of a key and a value. - **Hash Function**: Maps keys to array indices. Ideal: uniform distribution, fast computation. - **Collision**: When two different keys hash to the same index. - **Collision Resolution**: - **Chaining**: Each bucket holds a linked list (or dynamic array) of entries hashing to that index. - **Open Addressing**: Probe for another slot in the array (linear, quadratic, double hashing). - **Average Case Complexity**: $O(1)$ for search, insert, delete (assuming good hash function and low load factor). - **Worst Case**: $O(n)$ (if all keys collide). - **Load Factor ($\lambda$)**: $\lambda = \frac{\text{number of entries}}{\text{number of buckets}}$. Should be kept < 0.7–0.8 for chaining to maintain efficiency. **Hash Function Example**: For string keys, a simple hash: sum of ASCII values modulo table size. *Better*: Polynomial rolling hash (e.g., used in Java’s String hashCode). For integers: often `key % tableSize` (if tableSize is prime, helps distribution). **Operations**: - **Insert(key, value)**: 1. Compute index = hash(key) % tableSize 2. Insert (key, value) into bucket at index (using chaining or open addressing). - **Search(key)**: 1. Compute index = hash(key) % tableSize 2. Search bucket at index for key. - **Delete(key)**: Similar to search, then remove entry. **Corrected Exercise 1**: *Problem*: A hash table has 10 buckets. Use the hash function $h(k) = k \mod 10$ to insert the keys: 12, 22, 32, 42. Use chaining to resolve collisions. Show the final state. *Solution*: - $h(12) = 12 \mod 10 = 2$ → Bucket 2: [12] - $h(22) = 22 \mod 10 = 2$ → Bucket 2: [12, 22] - $h(32) = 32 \mod 10 = 2$ → Bucket 2: [12, 22, 32] - $h(42) = 42 \mod 10 = 2$ → Bucket 2: [12, 22, 32, 42] - All other buckets (0,1,3,4,5,6,7,8,9) are empty. *State*: Bucket 0: [] Bucket 1: [] Bucket 2: [12 → 22 → 32 → 42 → NULL] Bucket 3: [] ... Bucket 9: [] **Corrected Exercise 2**: *Problem*: Why is it important for the table size in a hash table to be a prime number when using the hash function $h(k) = k \mod m$? *Solution*: If $m$ is not prime and shares factors with common patterns in keys (e.g., keys are multiples of 2, and $m$ is even), then many keys will hash to the same subset of buckets, increasing collisions. *Example*: Keys = {2, 4, 6, 8, 10, ...}, $m = 10$ (even): - All keys hash to 0, 2, 4, 6, 8 → only 5 buckets used. If $m = 11$ (prime): - $2 \mod 11 = 2$, $4 \mod 11 = 4$, $6 \mod 11 = 6$, $8 \mod 11 = 8$, $10 \mod 11 = 10$ → spread out. Using a prime reduces the chance of systematic collisions due to common factors. **Corrected Exercise 3**: *Problem*: Calculate the load factor for a hash table with 15 buckets containing 9 entries. Is this acceptable for chaining? *Solution*: $\lambda = \frac{9}{15} = 0.6$ Since 0.6 < 0.7, this is acceptable and should maintain good $O(1)$ average performance for chaining. **Corrected Exercise 4**: *Problem*: What happens to performance if the hash function is poor (e.g., always returns 0)? *Solution*: All keys hash to bucket 0. - With chaining: Bucket 0 becomes a linked list of all $n$ entries. - Search, insert, delete require traversing this list → $O(n)$ time. - Performance degrades to that of a linked list, defeating the purpose of the hash table. *Conclusion*: A good hash function is essential for maintaining $O(1)$ average case performance. --- ## VIII. Using Repetition Structures to process arrays and lists Repetition structures (loops) are fundamental for traversing and processing data stored in arrays and linked lists. The choice of loop type (for, while) depends on the data structure and the task. **Definition**: Repetition structures (loops) allow a block of code to be executed multiple times, typically to traverse data structures, perform calculations, or process collections. **Processing Arrays**: - **Known Size**: Use a `for` loop with index from 0 to size-1 (or 1 to size). - **Access**: Direct via index: `array[i]`. - **Common Patterns**: - **Traversal**: Process each element once. - **Search**: Linear search (check each element until match or end). - **Filtering**: Create new array with elements meeting condition. - **Aggregation**: Sum, average, min, max. - **Efficiency**: $O(n)$ for full traversal; $O(1)$ per element access. **Processing Linked Lists**: - **No Indexing**: Must traverse via pointers. - **Loop Type**: `while` loop is natural (continue until null pointer). - **Access**: Sequential only; to get $i$-th element, must traverse $i$ nodes. - **Common Patterns**: - **Traversal**: Start at head, follow `next` until null. - **Search**: Traverse and compare data. - **Insertion/Deletion**: Often requires traversal to find position (except head). - **Efficiency**: $O(n)$ for traversal/search; $O(1)$ for insertion/deletion at known position. **Corrected Exercise 1**: *Problem*: Write pseudocode to calculate the average of all elements in an integer array `marks[0..n-1]`. *Solution*: ``` REAL sum ← 0 FOR i FROM 0 TO n-1 sum ← sum + marks[i] END FOR REAL average ← sum / n OUTPUT average ``` **Corrected Exercise 2**: *Problem*: Write pseudocode to count how many times a specific value `x` appears in a singly linked list. *Solution*: ``` INT count ← 0 VAR current ← head WHILE current IS NOT NULL IF current.data = x THEN count ← count + 1 END IF current ← current.next END WHILE OUTPUT count ``` **Corrected Exercise 3**: *Problem*: Write pseudocode to create a new array containing only the even numbers from an input array `nums[0..n-1]`. *Solution*: ``` INT evenCount ← 0 // First pass: count evens FOR i FROM 0 TO n-1 IF nums[i] MOD 2 = 0 THEN evenCount ← evenCount + 1 END IF END FOR INT evens[evenCount] INT index ← 0 // Second pass: copy evens FOR i FROM 0 TO n-1 IF nums[i] MOD 2 = 0 THEN evens[index] ← nums[i] index ← index + 1 END IF END FOR OUTPUT evens ``` **Corrected Exercise 4**: *Problem*: Compare the use of `for` and `while` loops for processing an array versus a linked list. *Solution*: | Data Structure | Preferred Loop | Reason | |----------------|----------------|--------| | Array | `for` loop | Index-based access is natural; number of iterations known. | | Linked List | `while` loop | Access is pointer-based; continue until null; number of nodes unknown beforehand. | *Example Array*: `FOR i ← 0 TO LENGTH(arr)-1` *Example Linked List*: `WHILE node ≠ NULL` *Using `for` on a list* is awkward without indexing; *using `while` on an array* is possible but less idiomatic (would require manual index management). --- ## Synthèse du chapitre - **Primitive Data Types** are the atomic building blocks (int, float, bool, char) with fixed size and range. - **Arrays** provide homogeneous, contiguous storage with $O(1)$ indexed access but fixed size and costly insertions/deletions. - **Records** group heterogeneous fields under a single name, enabling logical organization of complex entities. - **Data Structures** encompass the organization and management of data; choice impacts efficiency (time/space). - **Linked Lists** offer dynamic size and $O(1)$ insertion/deletion at known positions but $O(n)$ access; built via nodes and pointers. - **Hash Tables** provide $O(1)$ average-case key-value storage via hashing, requiring good hash functions and collision resolution (chaining/open addressing). - **Repetition Structures** (loops) are essential for processing: `for` loops suit arrays (indexed), `while` suits linked lists (pointer traversal). - **Selection Criteria**: Choose based on required operations (access, search, insert, delete), size stability, and memory constraints. --- ## Glossaire - **Array**: A homogeneous collection of elements stored in contiguous memory, accessed by index. - **Boolean**: A primitive data type representing logical values: true or false. - **Data Structure**: A way of organizing and storing data to enable efficient access and modification. - **Hash Table**: A data structure that maps keys to values using a hash function for efficient lookup. - **Linked List**: A linear data structure where each element (node) contains data and a reference to the next node. - **Primitive Data Type**: A basic data type provided by a language, not composed of other types (e.g., int, char). - **Record**: A composite data type that groups related fields of potentially different types under a single name. - **Repetition Structure**: A programming construct (loop) that executes a block of code multiple times (e.g., for, while). --- *End of Chapter*