--- title: "Contiguous list merits and static implementation" subject: "Data Structure and Algorithm" chapter: 3 key: "semester_4/data_structure_and_algorithm:contiguous-list-merits-demerits" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/contiguous-list-merits-demerits site: BCT Engineering --- # Contiguous list merits and static implementation Data Structure and Algorithm · Chapter 3: List - Asked in: 2069 Poush, 2+4 marks - Video: [Data Structures: Arrays vs Linked Lists](https://www.youtube.com/watch?v=lC-yYCOnN8Q) — mycodeschool - 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/contiguous-list-merits-demerits - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-3 ## Question Discuss merits and demerits of contiguous list. Explain static implementation of list. ## Short answer Contiguous list merits are O(1) random access, simplicity, no pointer overhead, and good cache behaviour. Demerits are fixed size, O(n) shifting on insert/delete, need for a contiguous block, and costly resizing. Static implementation declares a fixed array with n counting used elements; insert shifts right, delete shifts left, checking overflow and underflow. ## Answer A **contiguous list** stores its elements in adjacent memory locations (an array plus a count of used positions). #### Merits - **Direct (random) access**: the i-th element is found in O(1) using its index, address = base + i × size. - **Simple**: easy to declare, understand and program. - **No extra memory for pointers**: only data is stored, so each element needs less memory than a linked node. - **Fast traversal and searching/sorting support**: good cache behaviour; binary search is possible on a sorted array. - Suitable when the maximum size is known and few insertions/deletions occur. #### Demerits - **Fixed size**: overflow if the list grows beyond MAX; memory wasted if it stays small. - **Slow insertion and deletion**: elements must be shifted, O(n). - **Needs a contiguous block** of memory. - Resizing at run time is costly (allocate new array, copy all). - Deleted positions are not reused automatically unless shifting is done. #### Static implementation of a list In static implementation, the array is declared with a fixed size at compile time and `n` counts the elements in use. ```text #define MAX 100 int list[MAX]; int n = 0; element: list[0] ... list[n-1] used list[n] ... list[MAX-1] free ``` Algorithm to insert item X at position K (0 ≤ K ≤ n): 1. If n == MAX, print "overflow" and stop. 2. For i = n-1 down to K: `list[i+1] = list[i]`. 3. `list[K] = X`; n = n + 1. Algorithm to delete the element at position K: 1. If n == 0 or K ≥ n, print "underflow/invalid" and stop. 2. For i = K to n-2: `list[i] = list[i+1]`. 3. n = n - 1. Traversal runs i from 0 to n-1. Memory for the whole array exists from the start of the program until it ends, which is why it is called static. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why can the i-th element of a contiguous list be accessed in O(1)? A. Its address is computed as base + i x size B. The list is traversed from the head i times C. A binary search is done on the indices D. A hash table maps i to the element Answer: A. Elements sit in adjacent memory, so the address comes from a formula with no traversal. (Key point: Direct access) 2. Why are insertion and deletion slow in a contiguous list? A. Every element needs its pointers updated B. Elements must be shifted, taking O(n) C. The whole array must be sorted again D. Memory must be freed for each element Answer: B. Positions are adjacent, so making or closing a gap needs shifting of later elements. (Key point: Slow insertion) 3. What happens when a statically sized list is full and one more item is inserted? A. Underflow B. A memory leak C. Overflow D. The array grows automatically Answer: C. A fixed array cannot hold more than MAX items, so insertion gives overflow. (Key point: Fixed size) 4. In static implementation of a list, when is the array's memory allocated? A. Only when an item is inserted B. At run time using malloc for each item C. When the list becomes full D. At compile time, existing for the whole run of the program Answer: D. The array has a fixed size declared in advance and exists throughout the program, hence 'static'. (Key point: Static implementation) ## Related in Data Structure and Algorithm - [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 - [Linked stack overcoming array demerits](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-linked-overcome-array-demerits) — Data Structure and Algorithm, chapter 4 - [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 - [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 and dynamic data structures; array list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astatic-dynamic-ds-array-list) — Data Structure and Algorithm, chapter 3 ## Related in other subjects - [Types of static relays; merits and demerits](https://www.bctengineer.com/question.md?key=semester_6%2Fswitchgear_and_protection%3Astatic-relay-types-merits) — Switchgear and Protection, chapter 8, asked 2× - [Forward vs reverse engineering merits and demerits](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aforward-reverse-engineering-merits) — Object Oriented Analysis and Design, chapter 4, asked 3× - [Cofferdam types, uses, merits and demerits](https://www.bctengineer.com/question.md?key=semester_5%2Ffoundation_engineering%3Acofferdam-types-merits) — Foundation Engineering, chapter 5, asked 7× - [Incineration: merits and demerits](https://www.bctengineer.com/question.md?key=semester_6%2Fsanitary_engineering%3Asolid-waste-incineration) — Sanitary Engineering, chapter 10, asked 7×