Intro

It’s been some time since I started learning data structures and algorithms, but it’s no fun just using these data structures in my code. So, I have decided to write a blog post explaining multiple data structures. We’ll start with a very simple data structure: vectors in C++. Since we are trying to go down the level of abstraction, let’s recreate a vector-like structure in C. Here are some properties our vector must have:

• Must be able to resize and add more elements in O(1)
• Set a default value
• Easy access to the elements

Before reading this blog post, I highly recommend you try to implement this. Hit me up on my social if you implement it; I would love to check it out. Make sure you read about struct and malloc a little bit. You can find this code on GitHub.

Basic working

The working of a basic vector is simple. There is an array working under the hood that keeps resizing. Instead of resizing every time there is a new push or insertion, which would make each push operation O(n) since we would need to copy all the elements from the previous array, we make the size of the array twice the previous size, thus achieving an amortized O(1) time complexity for each push operation.

Basic structure

Let’s start by creating a basic struct for the vector. Since C is not an OOP language, we’ll have to use structs.

struct vec{
	int size;
	int current;
	int* container;
	int default_value;
};

Here we have a few key components: size, which keeps track of the vector’s capacity; current, which is the index where the next element will be pushed; container, which is an int pointer to the first value of the allocated array; and default_value, which is the default value specified by the user.

Basic methods

The makeVec() method

The makeVec function will initialize and return a vector. This function is helpful to abstract away the initialization code.

vec MakeVec(int given_size , int default_value){
	struct vec v1;
	v1.current = 0;
	v1.size = given_size;
	v1.container = (int*)malloc(given_size * sizeof(int));
	v1.default_value = default_value;
	if(v1.container == NULL){
		printf("malloc failed");
	}else{
		for(int i = 0 ; i < given_size ; i++){
			v1.container[i] = default_value;
		}
	}
	return v1;
}

The PushToVec() method

void PushToVec(vec* v, int value){
	if(v->current != v->size){
		v->container[v->current] = value;
		v->current++;
	}else{
		int new_size = v->size * 2;
		int* new_container = (int*)malloc(new_size * sizeof(int));
		for(int i = 0 ; i < new_size; i++){
			new_container[i] = (i < v-> size) ? v->container[i] : v->default_value;
		}
		free(v->container);
		v->size = new_size;
		v->container = new_container;
		v->container[v->current] = value;
		v->current++;
	}
}

The PushToVec function has two cases:

1. current < size: In this case, we set the array at the current position to the value and increment current to point to the next position.
2. current == size: Once current equals size, meaning the space in the container is full, we need to perform “array doubling.” This involves doubling the array size, copying over all elements, and adding the new value. We define new_size, allocate new_container, copy values, and finally, free the old container and set v->container to the new container.

If you’re wondering why we use v-> instead of v., it’s because v is a pointer to a struct, not the struct itself.

The atVec() function

int atVec(struct vec* v, int index){
	if(index >= 0 && index < v->size){
		return v->container[index];
	}
	fprintf(stderr, "Error: Index %d out of bounds for vector of size %d\n", index, v->size);
	exit(0);
}

This function returns the element at a particular index with some error handling. I had to use fprintf because there is no exception handling out of the box in C.

Usage

int main(){
	struct vec v1 = MakeVec(1,0);
	for(int i = 0 ; i < 10 ; i++){
		PushToVec(&v1,i+1);
		printf("%d\n",atVec(&v1,i));
	}
	printf("%d\n",atVec(&v1,20));
	freeVec(&v1);
	return 0;
}

This is a simple usage example of a vector. As an exercise, try writing the freeVec function on your own.