--- title: "Static and dynamic data structures; array list" subject: "Data Structure and Algorithm" chapter: 3 key: "semester_4/data_structure_and_algorithm:static-dynamic-ds-array-list" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/static-dynamic-ds-array-list site: BCT Engineering --- # Static and dynamic data structures; array list Data Structure and Algorithm · Chapter 3: List - Asked in: 2069 Bhadra, 2+4 marks - Video: [Dynamic and Static Arrays](https://www.youtube.com/watch?v=PEnFFiQe1pM) — WilliamFiset - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/static-dynamic-ds-array-list - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-3 ## Question What do you mean by static and dynamic data structures? Explain array implementation of list with its limitations. ## Short answer Static data structures have fixed compile-time size and contiguous memory; dynamic structures change size at run time using allocation and pointers. Array list stores elements consecutively with a count n; limitations are fixed MAX causing overflow or wasted memory, O(n) shifting on insert/delete, contiguous block requirement, and costly resizing. ## Answer #### Static and dynamic data structures A **static data structure** has a fixed size decided at compile time. Memory is allocated once and cannot grow or shrink at run time. Example: an array `int a[100];`. A **dynamic data structure** can change its size during execution; memory is requested (`malloc`) and released (`free`) as needed. Examples: linked list, dynamic stack/queue, tree. | Static | Dynamic | |---|---| | Size fixed at compile time | Size changes at run time | | Memory may be wasted or insufficient | Memory used as needed | | Elements stored contiguously | Elements scattered, joined by pointers | | Fast direct access by index | Sequential access only | | Insertion/deletion needs shifting | Only pointers change | | Example: array | Example: linked list | #### Array implementation of a list The elements of the list are stored in consecutive locations of an array, and a variable `n` (or `last`) records how many elements are present. The i-th element is `list[i]`, so the order of elements is given by the physical order in memory. ```text list[] 10 20 30 40 _ _ MAX = 6 index 0 1 2 3 4 5 n = 4 ``` - **Insert at k**: if n = MAX report overflow; else shift `list[k..n-1]` one place right, put the item at `list[k]`, n = n + 1. - **Delete at k**: if n = 0 report underflow; else shift `list[k+1..n-1]` one place left, n = n - 1. ```c int insert(int list[], int *n, int k, int x) { if (*n == MAX) return 0; for (int i = *n - 1; i >= k; i--) list[i + 1] = list[i]; list[k] = x; (*n)++; return 1; } ``` #### Limitations 1. Size is fixed; the list cannot grow beyond MAX (overflow), and a big array wastes memory if only few items are stored. 2. Insertion and deletion in the middle need shifting of many elements: O(n) time. 3. The array must occupy one contiguous block, which may not be available. 4. Size cannot be changed at run time; resizing means allocating a new array and copying. 5. Elements of different types cannot be mixed, and deleted slots stay reserved. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. A static data structure is one whose size is: A. Fixed at compile time B. Changed at run time C. Decided by malloc D. Unlimited Answer: A. Memory is allocated once and cannot grow or shrink. (Key point: Static structure) 2. Which is a dynamic data structure? A. int a[100] B. Linked list C. Fixed array of structs D. Static matrix Answer: B. Linked lists use malloc/free to change size. (Key point: Dynamic example) 3. What happens when deleting at k in an array list? A. list[k+1..n-1] shift left and n decreases B. list[k..n-1] shift right C. Only n decreases D. A node is freed Answer: A. Later elements move left to fill the gap. (Key point: Delete in array list) 4. Which is a limitation of array lists? A. No random access B. Fixed size and shifting on insert/delete C. Extra pointers D. Cannot be traversed Answer: B. Fixed MAX causes overflow or wasted space, and shifting costs O(n). (Key point: Limitation) ## Related in Data Structure and Algorithm - [Array list; static or dynamic choice](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aarray-list-static-dynamic-reason) — Data Structure and Algorithm, chapter 3 - [Static vs dynamic implementation of list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astatic-vs-dynamic-list-example) — Data Structure and Algorithm, chapter 3, asked 2× - [Static vs dynamic implementation of stack](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-static-vs-dynamic) — Data Structure and Algorithm, chapter 2 - [Array implementation of list in C](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aarray-list-c-limitations) — Data Structure and Algorithm, chapter 3 - [Why choose static or dynamic list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Achoose-static-or-dynamic-list) — Data Structure and Algorithm, chapter 3 - [Dynamic implementation of queue](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adynamic-queue-linked-algorithm) — Data Structure and Algorithm, chapter 4 ## Related in other subjects - [Static and dynamic hazards and their elimination](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Astatic-dynamic-hazards) — Digital Logic, chapter 3, asked 2× - [Static and dynamic routing algorithms](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Astatic-dynamic-routing) — Telecommunications, chapter 8 - [Dynamic memory for object and object array](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Adynamic-memory-object-array) — Object Oriented Programming, chapter 3 - [Static vs dynamic mathematical model](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Astatic-vs-dynamic-math-model) — Simulation and Modeling, chapter 2, asked 3×