Array data structure

Array Data Structure in C/C++

Array Data Structure in C/C++

Array Data Structure in C/C++

Implementation and source code of an Array data structure in C using structs and CPP using classes (object oriented approach).
As you probably know an array is a data structure which holds a collection of elements, each of the same type.

Each element can be accessed by it’s index. Indexes start from zero. In C/C++ we have arrays for basic data types like int, float, char, but what if we want an array of more complex data like objects or structs? We can create our own data structure:

#include<iostream>
using namespace std;

#define NULL 0

template<class Data>
class Array {
private:
    Data* myArray;
    int arraySize;
public:
    /* the constructor */
    Array(int size) {
        myArray = new Data[size];
        arraySize = size;
    }

    /* the destructor */
    ~Array() {
    if (myArray != NULL) {
        delete[] myArray;
    }
        myArray = NULL;
    }
}

In the constructor we create a new array of size specified as an argument and also store the size in the member variable arraySize. In the destructor we check if the array is not null (this means zero) and if not we delete[] the memory allocated to it. Then we assign NULL to it, so we avoid possible problems caused by dangling pointers.

The insert function

This inserts an element at a specified position, enlarging (resizing) the array if necessary (position > array size).
How this works is simple.

Quick example:
We have this array[1, 2, 3, 4]. It has 4 elements, and it’s index starts from zero like this:

array[0] is 1;
array[1] is 2;
array[2] is 3;
array[3] is 4;

We want to insert value 18 on position 4, so array[4] will be 18. But this means that the array should now have 5 elements instead of 4. In this case 4 is greater or equal to the above array’s size (which is 4), so we must resize it to allow 5 elements instead. We now have two arrays like this:

array[1, 2, 3, 4] and newArray[ , , , , ] (this one is currently empty. Note it has room for 5 elements.)

Now we copy into newArray all elements of the first array.

newArray[0] = array[0];
...
newArray[3] = array[3];

The arrays look like this now:
array[1, 2, 3, 4] and newArray[1, 2, 3, 4, ] <- we still have room for one more element!

We stop at 3 because that is the index of the last element we can copy. The original array has no other elements so there is nothing to copy anymore. Then, in the last position of the new array we copy the element we want to insert. So newArray[4] = 18;
In the last stage we have:

array[1, 2, 3, 4] and newArray[1, 2, 3, 4, 18];

On line 16 we free the space of the original array and on line 18 we make the variable point to the memory location of the new, 5 elements array.
Something like this:

array = newArray[1, 2, 3, 4, 18]

Lastly, we increment that member variable arraySize so it holds the correct, increased value, which is 5 in this case.

Otherwise, if we wanted to insert 18 on position 2 for example, which is not greater or equal than the array size then we go at the position of the last element of the array (array[4-1]) and copy in it the value stored at array[(4-1)-1], meaning array[3] = array[2] and so on, thus shifting the array to the right, replacing the old element.

array[1, 2, 3, 4]
array[0] is 1;
array[1] is 2;
array[2] is 3'
array[3] is 4;

Algorithm:
1. Starting at the last element (is always arraySize - 1) which is array[3], while this index 3 is greater than the position we want to insert the new element:
2. array[3] is 3 (array[3-1]  array[2])
3. We decrement the index by one.
4. The index is now 2 which is no longer greater than the position (2) so we stop the shifting.
5. We assign array[position] the element we want to insert.

array[2] = 18; ->; array[1, 2, 18, 4]

So in a nutshell: if we want to insert an element in a position that exceeds the boundaries of the array, then we simply increase it’s size to make room for it. If the position doesn’t exceed the array’s boundaries then we shift the elements to the right, to make room for the new one. (yes, last element is lost).

void insert(Data element, int position) {
    int i;
    if (position >= arraySize) {
        Data* newArray = new Data[position + 1];
        if (newArray == NULL) {
            return;
        }

	for (i = 0; i < arraySize; i++) {
            newArray[i] = myArray[i];
	}

	newArray[position] = element;

	if (myArray != NULL) {
	    delete[] myArray;
	}
	myArray = newArray;
        arraySize = position + 1;
    } else {
        for (i = arraySize - 1; i > position; i--) {
	    myArray[i] = myArray[i - 1];
	}
	myArray[position] = element;
    }
}

But what if we want to simply replace an element in the array without losing the last one (no shifting)?
Answer: we overload the [] operator. It returns a reference (the ampersand) because we must also modify the value if necessary. With this you can use the array class as a normal array!

Data& operator[] (int position) {
    return myArray[position];
}

You might also want to overload the conversion operator so you can use this class in functions which accept regular array pointer

operator Data* () {
    return myArray;
}
Resizing the array

Resizing an array means either increasing it’s size to allow storage of more elements or decrease it’s size, losing some elements.

As you’ve seen above, messing with the size of an array usually means creating another one of that size, copy whatever is to copy in it, free the memory of the old one and make the old one’s variable point to the new memory location.

So first thing we allocate space for a new array of size whatever the argument newSize is.

Through line 7 to 12 we check if the programmer wants a decrease or an increase in size. Obviously if the newSize is less than the current size of the array this means the array size will decrease and that the current array is larger than the new one (created at line 2) and vice versa.

Then, starting at the first element, while not going past the size of min array we copy into newArray[position] the value of myArray[position] (which is the old, original array).

At line 19 we overwrite the values of the original array to zero because, although we free it’s memory this doesn’t mean the values stored will be cleared. So we might find our old stuff there (or someone else’s) and that’s why we make it zero.

On line 23 we set the member variable arraySize have the new, updated value and finally on lines 25 – 28 we free the memory of the old array and make it’s variable point to the new location.

void resize(int newSize) {
    Data* newArray = new Data[newSize];
    if (newArray == NULL) {
        return;
    }

    int min;
    if (newSize < arraySize) {
        min = newSize;
    } else {
	min = arraySize;
    }

    int i;
    for (i = 0; i < min; i++) {
	newArray[i] = myArray[i];
    }

    for (i = 0; i < arraySize; i++) {
	myArray[i] = 0;
    }

    arraySize = newSize;

    if (myArray != NULL) {
	delete[] myArray;
    }
    myArray = newArray;
}
Removing elements from array

First let’s talk about removing elements and resizing. This what most people look for, let’s say we have this array:

array[1, 2, 3, 4, 5]

And I want to remove the element on position 1 so the array will look like this:

array[1, 3, 4, 5]

First thing is create a new array the size of the old one minus one (because we will remove one element, right?).

Second step is iterating through the array, starting with the first element and while not exceeding the last one

If the current position of is past the position we want to remove we copy in the new array at position the value of the old array at position + 1 (shifting left just like the Delete key does with text).

Else we just copy in the new array[position] the value of old array[position].

Third step is freeing the memory of the old array, make it point to the new memory location and update the member value arraySize so it has the correct value.

Quick example:

array[1, 2, 3, 4, 5]
I want to remove position 2 (array[2] which is 3) so the array will be array[1, 2, 4, 5]

1. create newArray[ , , , ] = 2
        is not
    else
       newArray[0] = array[0] -> newArray[1, , , ]
    i++;
    __________
    now i = 1;
    if i >= 2
        is not
    else
        newArray[1] = array[1] -> newArray[1, 2, , ]
    i++;
    __________
    now i = 2   
    if i >= 2  newArray[1, 2, 4, ]
    else
        not the case
    i++;
    __________
    now i = 3
    if i >= 2  newArray[1, 2, 4, 5]
    else
        not the case
    i++;
    __________
    now i = 4, no longer less than arraySize - 1 -> the algorithm finishes.
void removeByResizing(int position) {
    Data* newArray = new Data[arraySize - 1];
    if (newArray == NULL) {
        return;
    }

    int i;
    for (i = 0; i = position) {
	    newArray[i] = myArray[i + 1];
        } else {
            newArray[i] = myArray[i];
        }
    }

    if (myArray != NULL) {
        delete[] myArray;
    }
    myArray = newArray;
    arraySize = arraySize - 1;
}

You can also remove an array value without resizing, by shifting the values in the array to the left (this means duplicating the last value)

void removeByShifting(int position) {
    int i;
    for (i = position + 1; i < arraySize; i++) {
        myArray[i - 1] = myArray[i];
    }
}

Finally, create a method for returning the array’s size:

int getSize() {
    return arraySize;
}
The main method

An example main() method for testing the code:

int main() {
    Array testArray(7);
    for (int i = 0; i < testArray.getSize(); i++) {
        testArray[i] = i + 1;
    }
	
    cout << &quot;Printing the original array&quot; <<; endl;
    for (int i = 0; i < testArray.getSize(); i++) {
        cout << testArray[i] << endl;
    }
    cout << endl;

    cout << &quot;Resizing the array to 5 elements instead of 7&quot; << endl;
    testArray.resize(5);
    for (int i = 0; i < testArray.getSize(); i++) {
	cout << testArray[i] << endl;
    }
    cout << endl;

    int element = 10;
    cout << &quot;Inserting a number on position 6 (7th element)&quot; &lt;&lt; endl;
    testArray.insert(element, 6);
    for (int i = 0; i < testArray.getSize(); i++) {
        cout << testArray[i] << endl;
    }
    cout << endl;

    cout << &quot;Removing the 0 element, position 5&quot; << endl;
    testArray.removeByResizing(5);
    for (int i = 0; i < testArray.getSize(); i++) {
        cout << testArray[i] << endl;
    }
    cout << endl;

    cout << &quot;Setting the value at position 0 to 103 using the [] operator&quot; << endl;
    testArray[0] = 103;
    for (int i = 0; i << testArray.getSize(); i++) {
	cout << testArray[i] << endl;
    }

    return 0;
}

The output:

Printing the original array
1 2 3 4 5 6 7

Resizing the array to 5 elements instead of 7
1 2 3 4 5

Inserting a number on position 6 (7th element)
1 2 3 4 5 0 10

Removing the 0 element, position 5
1 2 3 4 5 10

Setting the value at position 0 to 103 using the [] operator
103 2 3 4 5 10

Array data structure implementation in C

This is the same reasoning as above, but made using the C language.

#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct MyData {
	char* name;
	int value;
};

void deleteArray(MyData* myArray) {
	if (myArray != 0) {
		free(myArray);
		myArray = 0;
	}
}

MyData* createArray(int size) {
	/* we use calloc so we don't have bogus data */
	MyData* newArray = (MyData*)calloc(size, sizeof(MyData));
	return newArray;
}

/* pointer to pointer so we can modify the array which is passed to the function */
void resizeArray(int oldSize, int newSize, MyData** oldArray) {
	/* we create a new array */
	MyData* newArray = (MyData*)calloc(newSize, sizeof(MyData));
	if (newArray == 0) {
		return;
	}
	/* we try to find if the resizing creates a larger or a smaller array */
	int smallest;
	if (newSize < oldSize) {
		smallest = newSize;
	} else {
		smallest = oldSize;
	}
	int index;
	for (index = 0; index < smallest; index++) {
		/* we use (*oldArray) to get rid of the first '*' in MyData** oldArray
		so we can access it's elements */
		newArray[index] = (*oldArray)[index];
	}
	/* we free the memory of the old array and set the variable to point to the new
	location */
	free(*oldArray);
	*oldArray = newArray;
}

void insert(MyData** originalArray, MyData element, int position, int arraySize) {
	int i;
	/* if we want to insert on a position that exceeds current array's bounds
	we will resize it */
	if (position > arraySize) {
		MyData* newArray = (MyData*)calloc(position + 1, sizeof(MyData));
		if (newArray == 0) {
			return;
		}
		/* we simply copy the original elements over */
		for (i = 0; i < arraySize; i++) {
			newArray[i] = (*originalArray)[i];
		}
		/* we set the element to the specified position */
		newArray[position] = element;
		
		/* free the old space and make it point to the new location */
		free(*originalArray);
		*originalArray = newArray;
	}
	else {
		for (int i = arraySize - 1; i > position; i--) {
			originalArray[i] = originalArray[i - 1];
		}
		*originalArray[position] = element;
	}	
}

/* setting the element at a specified position */
void set(MyData* array, MyData elem, int position) {
	array[position] = elem;
}


void remove(MyData** originalArray, int position, int arraySize) {
	MyData* newArray = (MyData*)calloc(arraySize - 1, sizeof(MyData));
	if (newArray == 0) {
		return;
	}
	int i;
	for (i = 0; i < arraySize - 1; i++) {
		
		if (i >= position) {
			newArray[i] = (*originalArray)[i + 1];
		}
		else {
			newArray[i] = (*originalArray)[i];
		}
	}
	free(*originalArray);
	*originalArray = newArray;
}

int main() {	
	MyData* testArray = createArray(7);

	int i;
	for (i = 0; i < 7; i++) {
		testArray[i].value = i + 1;
		testArray[i].name = (char*)calloc(15, sizeof(char));
		strcpy(testArray[i].name, "this is a test");
	}
	
	printf("Printing the original array\n");
	for (i = 0; i < 7; i++) {
		printf("%d %s\n", testArray[i].value, testArray[i].name);
	}
	printf("\n");

	printf("Resizing the array to 5 elements instead of 7\n");
	resizeArray(7, 5, &testArray);
	for (i = 0; i < 5; i++) {
		printf("%d %s\n", testArray[i].value, testArray[i].name);
	}
	printf("\n");

	MyData data;
	data.name = (char*)calloc(10, sizeof(char));
	strcpy(data.name, "inserted");
	data.value = 2015;
	printf("Inserting a number on position 6 (7th element)\n");
	insert(&testArray, data, 6, 5);
	for (i = 0; i < 7; i++) {
		printf("%d %s\n", testArray[i].value, testArray[i].name);
	}
	printf("\n");

	printf("Removing the 0 element, position 5\n");
	remove(&testArray, 5, 7);
	for (i = 0; i < 6; i++) {
		printf("%d %s\n", testArray[i].value, testArray[i].name);
	}
	printf("\n");

	/* deallocating */
	for (i = 0; i < 6; i++) {
		/* don't forget to delete the allocated chars! */
		free(testArray[i].name);
	}
	deleteArray(testArray);
	return 0;
}

This is how to create an array data structure in C. You might be interested in:
Writing an array data structure to file

FacebookTwitterLinkedin