What is
array?
-->
Often, we have to deal with groups of objects of same type such as names of persons, instrument readings in an experiment, roll numbers of students, and so on. These groups can be conveniently represented as elements of arrays. An array is defined as a sequence of objects of the same data type. All the elements of an array are either of type int (whole numbers), or all of them are of type char, or all of them are of floating decimal point type, etc. An array cannot have a mixture of different data types as its elements. Also, array elements cannot be functions; however, they may be pointers to functions. In computer memory, array elements are stored in a sequence of adjacent memory blocks. Since all the elements of an array are of same data type, the memory blocks allocated to elements of an array are also of same size. Each element of an array occupies one block of memory. The size of memory blocks allocated depends on the data type.
Here's a youtube video to understand the concept of Array : Intro into Arrays
In this post, we are going to look at the C++ implementation of Array meaning , we will write the code for several functions to manipulate an Array. By successfully understanding these functions , we will know how an array works.
Each Computer Science student must do an obligatory course on Data Structures. During this course , the students come across the implementation of many data structures. Arrays list implementation usually comes in the beginning of the course. So this is one of the easier data structures to both understand and implement.
We are going to complete 6 tasks to create a complete code to manipulate an array list. This code will be helpful in teaching you guys to manually make your own code for data structures. Such codes are needed in the future in situations where custom made array list codes are needed. After the 6 tasks (mentioned below), I will show you an example to implement this code to solve a problem.
The 6 tasks are:
Task 1: Add getLength function. Add a new function
getLength to the list. This function will return the
current length, i.e., the number of items, of the list.
Task 2: Add insertItemAt function. Add a new function
insertItemAt to the list. This function will insert
a new item at a given position. The prototype of the function is as follows: int insertItemAt(int pos, int
item). The function will insert the given
at the given position .
You have to do this by shifting only one
item of the existing list. Note that the
pos value can be larger or equal to
length variable. In such a
case, you should not insert anything in the list. You may also require allocating new memory similar to
insertItem function if list is already full.
Task 3: Add shrink feature to the list. The current implementation expands its memory when it is full.
This is done in the insert function. When it finds that the
length variable has reached the value of
listMaxSize,
it allocates a new memory whose size is double the existing memory. Your job is to add
shrink feature to the list. This feature will allow the list to
shrink its memory whenever the
length variable has reached to half of the current size. In that case, you will reallocate a new memory whose
size will be half the current size.
However, if the current size of the list is LIST_INIT_SIZE, then you will
not need to shrink the memory. Write a function
shrink that will shrink the list appropriately.
Task 4: Add deleteLast function. Add a new function
deleteLast to the list. This function will behave
similar to existing
deleteItem function except that it will delete the last item of the list. You will not
need to move any other items. So, this function will not have any input parameter. You must call the
shrink function after deletion. You will also require adding
shrink function calls inside
deleteItem and
deleteItemAt functions.
Task 5: Add clear function. Add a new function
clear to the list. This function will delete all items from
the list and will de-allocate its memory. When a new item will be inserted next, the list must be
allocated a new memory of size LIST_INIT_SIZE again. You must write required codes in the
insertItem function to enable this.
Task 6: Add deleteAll function. Add a new function
deleteAll to the list. This function will delete all
items from the list, but will not de-allocate its memory. However, it will shrink its memory to LIST_INIT_SIZE if the list is currently consuming a memory whose size is larger than LIST_INIT_SIZE.
Before I head on to the solution, I want you guys to think about the tasks and write codes solving them. This will increase your capability to think about problem solving. I will write blog posts describing the solution in near future.
Don't forget to share and follow my blog-posts...... See you guys next time. :)
