Arrays and Abstract Data Type in Data Structure

Abstract Data Types and Arrays:

Abstract Data Types (ADTs) classify data structures by defining a minimal expected interface along with a set of methods. This concept is similar to creating a blueprint before starting a project, whether it’s building a computer or constructing a building.

Array - ADT An array ADT holds the collection of given elements (can be int, float, custom) accessible by their index.

1. Minimal Required Functionality:
   An array has two basic functionalities:

   • get(i): Retrieves the element at index (i).
   • set(i, num): Assigns the value (num) to the element at index (i).

2. Operations:
   We can perform various operations on the array, but we'll focus on some basic ones:

   • Max(): Returns the maximum element in the array.
   • Min(): Returns the minimum element in the array.
   • Search(num): Searches for the element (num) in the array.
   • Insert(i, num): Inserts the value (num) at index (i).
   • Append(x): Adds the value (x) to the end of the array.

Static and Dynamic Arrays:

• Static Arrays: The size cannot be changed after creation.
• Dynamic Arrays: The size can be adjusted as needed.

Quick Quiz- Code the operations mentioned above in C language by creating array ADT. Hint: Use structures.

Memory Representations of Array:

• Elements in an array are stored in contiguous memory locations.

• Elements can be accessed using the base address in constant time, O(1).

• While the size of an array cannot be changed directly, it can be reallocated to a larger memory location. However, resizing an array is a costly operation.

Suppose we want to build an array as an abstract data type with our customized set of values and customized set of operations in a heap. Let’s name this customized array myArray.

Let our set of values which will represent our customized array include these parameters:

• total_size
• used_size
• base_address

And the operations include operators namely,

• max()
• get(i)
• set(i,num)
• add(another_array)

So, now when we are done creating a blueprint of the customized array. We can very easily code their implementation, but before that, let’s first learn what these values and operations, we have defined, do:

Understanding the ADT Above:

• total_size: This variable stores the total reserved size of the array in memory.

• used_size: This variable keeps track of the amount of memory currently being used.

• base_address: This is a pointer that stores the address of the first element of the array.

Let the illustration below serve as an example of the concepts discussed.

Here, the total_size returns 6, and the used_size returns 3.