資料結構與演算法

(10%) Design and describe the implementation of a dynamic array-like container that can grow as elements are added, without requiring a fixed size to be declared at initialization. Your explanation should include:

• Memory Management: How do you allocate and deallocate memory for the underlying storage? What functions or mechanisms would you use to manage this memory dynamically?
• Capacity Expansion Strategy: When the container runs out of capacity as new elements are inserted, how do you decide to increase its size? Discuss the growth factor and the trade-offs it involves in terms of memory usage and performance.
• Indexing Operations: How can you ensure $O(1)$ random access to elements by index? What data structure or access method do you use to guarantee this?
• Insertion and Deletion Complexity: What is the expected time complexity for inserting and deleting elements at arbitrary positions, and how does this scale as the size of the container grows? Address the concept of amortized complexity and explain why it might differ from the worst-case scenario.