Implement Array from Scratch using C++

This tutorial will teach you how to implement array from scratch. By learning this, you will understand how different methods like push,shift,unshift,pop,concat where implemented in your favourite programming language.

I will be using C++ in this tutorial as low level programming language helps in improving problem solving skills and become a better programmer. You should be able to follow along with basic knowledge of Javascript or C++ or any other languages.

We will be covering:

• Creation

• Insertion

• Deletion

• Get

Creation

The code is a class to create a list/array with the variable to hold the current length, maximum length and the memory address of the array in heap. When the class in called to instantiate a list object, the size is initialised and the blocks of memory to store each data in the array next to each other and the address to these blocks is what is held in the arr variable in the class.

class Array {

    private:
      int *arr;
      int size;
      int length = 0;

    public:

       Array(){

          arr = new int[20];
      }

      Array(int sz){

          size = sz;
          arr = new int[size];
      }
}

In the code above, we are setting the default maximum size of the array to 20 in the default class constructor and using the size the user specified in the second constructor.

Insertion

To insert any value in the array, we need to specify the index/position it should be inserted. We will check if the position is not out of range before inserting in any position.

void insert(int index, int data){

          if(index < 0 || index > length) return -1;

          for(int i = length; i > index; i--){

              arr[i] = arr[i-1];
          }

          arr[index] = data;
          length++;
      }

If we want to implement a push or unshift method for instance, we will always insert at the last index for push and first index for unshift using this insert function.

Get

When we want to get a value from any position, we need to check if the position is not out of range.

int getAt(int index){

          if(index < 0 || index >= length) return -1;

          return arr[index];
 }

Deletion

Deleting a value at any index will need shifting all other values backwards to fill in the removed values. We also need to confirm that index is within range.

void deleteAt(int index){

          if(index < 0 || index >= length) return;

          int x = arr[index];

          for(int i = index; i < index - 1; i++){

              arr[i] = arr[i+1];
          }

          length--;
      }

To implement unshift and pop methods, we need to just remove from the start and end for unshift and pop respectively.

Final Code

#include <stdio.h>

class Array {

    private:
      int *arr;
      int size = 20;
      int length = 0;

    public:

       Array(){

          arr = new int[20];
      }

      Array(int sz){

          size = sz;
          arr = new int[size];
      }

      void insert(int index, int data){

          if(index < 0 || index > length) return;

          for(int i = length; i > index; i--){

              arr[i] = arr[i-1];
          }

          arr[index] = data;
          length++;
      }

      void deleteAt(int index){

          if(index < 0 || index >= length) return;

          int x = arr[index];

          for(int i = index; i < index - 1; i++){

              arr[i] = arr[i+1];
          }

          length--;
      }

       void getAt(int index){

          if(index < 0 || index >= length) return -1;

          return arr[index];
      }

      void display(){

          for(int i = 0; i < length; i++){

              printf("%d \n",arr[i]);
          }
      }
};

int main()
{

    Array arr(20);
    arr.insert(0,2);
    arr.display();

    return 0;
}