Array
Explore how arrays function as fundamental data structures by leveraging contiguous memory allocation to provide constant time access for insertions and retrievals. Understand the calculations behind element addressing and the space-time trade-offs involved in using arrays, including insights into dynamic arrays used in scripting languages.
We'll cover the following...
In this section of the course, we'll consider various data-structures and understand how different operations on them can be analyzed for complexity. We'll also digress into general discussions around trade-offs of space and time, so as to cultivate the readers' thought process for reasoning about complexity.
We'll start with the most basic data-structure - the Array. Almost all languages allow users to create arrays. Insert or retrieval operations on an array are well-known to be constant or O(1) operations. But what makes these operations constant time operations?
Contiguous memory allocation is the key to an array's constant time retrieval/insert of an element given the index. Any language platform that you code in would request the underlying operating system to allocate a contiguous block ...