Friday, September 1, 2017

Data Structures: Dynamic Array implementation in C++ (Part 1)

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. :)

No comments:

Post a Comment

Interview Questions at Enosis(Part 3)

In Part 2 , I have discussed 3 coding problems out of 6. Here we will talk about the next 3 coding problems. Problem 4: Write a function...