Implement an array class

An array is an index-based data structure, which means every element is referred to by an index. Array data are stored in sequential memory. The index runs from 0 to the array size minus one. The size of an array should be specified when initializing an array in Java. Here is an implementation of an array class and the methods in the class – add, remove, search, and traversal.

Most programming languages such as C, C++, and Java have built-in support for arrays. Some languages such as Python don’t have a built-in array, but provide external libraries such as array module or NumPy array to work with. Most time you don’t need to implement your own class. The implementation itself will help you understand how the array works under the hood.

Map of Array class implementations

you are here

Part 1 – Array implementation
Part 2 – Sorted array implementation
Part 3 – Matrix 2d array implementation

Table of Content

Define an Array class and add elements

First, you define an Array class. Add an element at the end, or the given index. In Java, you need to check whether you have reached the max size.

Java

public class Array<T> {	
    private T[] array;
    private int maxSize ;
    private int length = 0;
    
    //Constructor, Time O(1), Space O(1)
    @SuppressWarnings("unchecked")
    public Array(int size) {
    	maxSize = size;
    	array = (T[]) new Object[maxSize];
    }
    
    //Add one element at the end, Time O(1), Space O(1)
    public void add(T value) {
    	if( length == maxSize) {
    		System.out.println("reach max size!");
    		return;
    	}
        array[length] = value;
        length++;
    }
    
    //Add one element at index, Time O(n), Space O(1)
    public void insertAt(T value, int index) {  
    	if (length+1 > maxSize ) {
    		System.out.println("reach max size!");
    		return;
    	}
    	if (index < 0 || index > length) {
    		System.out.println("invalid index");
    		return;
    	}
    	length++;
        for (int i = length-1; i > index; i--) {
          array[i] = this.array[i-1];
        }
        array[index] = value;       
    }
}

public class Array<T> {

private T[] array;

private int maxSize ;

private int length = 0;

//Constructor, Time O(1), Space O(1)

@SuppressWarnings("unchecked")

public Array(int size) {

maxSize = size;

array = (T[]) new Object[maxSize];

}

//Add one element at the end, Time O(1), Space O(1)

public void add(T value) {

if( length == maxSize) {

System.out.println("reach max size!");

return;

}

array[length] = value;

length++;

}

//Add one element at index, Time O(n), Space O(1)

public void insertAt(T value, int index) {

if (length+1 > maxSize ) {

System.out.println("reach max size!");

return;

}

if (index < 0 || index > length) {

System.out.println("invalid index");

return;

}

length++;

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

array[i] = this.array[i-1];

}

array[index] = value;

}

Javascript

class Array{
    //Constructor, Time O(1), Space O(1)
    constructor() {
      this.length = 0;
      this.array = [];
    }
    //Add one element, Time O(1), Space O(1)
    insert(value) {
      this.array[this.length] = value;
      this.length++;
    }
    //Add one element at index, Time O(n), Space O(1)
    insertAt(value, index) {
      if (index < 0 || index > this.length) {
    		console.log("invalid index");
    		return;
    	}
      this.length++;
      for (let i = this.length; i >= index; i--) {
        this.array[i] = this.array[i-1];
      }
      this.array[index] = value;      
    }
}

class Array{

//Constructor, Time O(1), Space O(1)

constructor() {

this.length = 0;

this.array = [];

}

//Add one element, Time O(1), Space O(1)

insert(value) {

this.array[this.length] = value;

this.length++;

}

//Add one element at index, Time O(n), Space O(1)

insertAt(value, index) {

if (index < 0 || index > this.length) {

console.log("invalid index");

return;

}

this.length++;

for (let i = this.length; i >= index; i--) {

this.array[i] = this.array[i-1];

}

this.array[index] = value;

}

Python

class Array:
    #Constructor, Time O(1), Space O(1)
    def __init__(self, size):
        self.num_items = 0
        self.array = [None]*size
        self.max_size = size
    #Add one element, Time O(1), Space O(1)
    def add(self, value):
        if self.num_items == self.max_size:
            print ("Reach max size, cannot add.")
            return
        self.array[self.num_items] = value
        self.num_items += 1
    #Add one element at index, Time O(n), Space O(1)
    def insert_at(self, value, index) :
      if index < 0 or index > self.num_items : 
            print("invalid index")
            return
      self.num_items += 1
      for i in range (self.num_items-1, index, -1) :
            self.array[i] = self.array[i-1]
      self.array[index] = value

class Array:

#Constructor, Time O(1), Space O(1)

def __init__(self, size):

self.num_items = 0

self.array = [None]*size

self.max_size = size

#Add one element, Time O(1), Space O(1)

def add(self, value):

if self.num_items == self.max_size:

print ("Reach max size, cannot add.")

return

self.array[self.num_items] = value

self.num_items += 1

#Add one element at index, Time O(n), Space O(1)

def insert_at(self, value, index) :

if index < 0 or index > self.num_items :

print("invalid index")

return

self.num_items += 1

for i in range (self.num_items-1, index, -1) :

self.array[i] = self.array[i-1]

self.array[index] = value

Doodle

array add

Delete an element

Delete the element by key or by index. You need to move the following elements to their preceding position.

Java

    //Delete by key, Time O(n), Space O(1), n is array length
    public void delete(T key) {
    	int index = search(key);
    	if (index < 0) {
    		System.out.println("key not found!");
    		return;
    	}
        for (int j = index; j < length-1; j++)        
            array[j] = array[j+1];
        length--;
    }
    
    //Delete element at index, Time O(n), Space O(1), n is array length
    public void deleteAt(int index) {
    	if (index >= length || index < 0) {
    		System.out.println("invalid index!");
    		return;
    	}
        for(int i = index; i < length-1; i++) {
          array[i] = array[i+1];
        }
        length--;
    }

//Delete by key, Time O(n), Space O(1), n is array length

public void delete(T key) {

int index = search(key);

if (index < 0) {

System.out.println("key not found!");

return;

}

for (int j = index; j < length-1; j++)

array[j] = array[j+1];

length--;

}

//Delete element at index, Time O(n), Space O(1), n is array length

public void deleteAt(int index) {

if (index >= length || index < 0) {

System.out.println("invalid index!");

return;

}

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

array[i] = array[i+1];

}

length--;

}

Javascript

    //Delete by key, Time O(n), Space O(1), n is array length
    delete (key) {
      var index = this.search(key);
      if (index == -1) {
    		console.log("key not found!");
    		return;
    	}    
      for (let j = index; j < this.length-1; j++)        
          this.array[j] = this.array[j+1];
      this.length--;
    }
    //Delete element at index, Time O(n), Space O(1), n is array length
    deleteAt(index) {
      if (index >= this.length || index < 0) {
    		console.log("invalid index!");
    		return;
    	}
      for (let i = index; i < this.length-1; i++) {
        this.array[i]=this.array[i+1];
      }
      this.length--;
    }

//Delete by key, Time O(n), Space O(1), n is array length

delete (key) {

var index = this.search(key);

if (index == -1) {

console.log("key not found!");

return;

}

for (let j = index; j < this.length-1; j++)

this.array[j] = this.array[j+1];

this.length--;

}

//Delete element at index, Time O(n), Space O(1), n is array length

deleteAt(index) {

if (index >= this.length || index < 0) {

console.log("invalid index!");

return;

}

for (let i = index; i < this.length-1; i++) {

this.array[i]=this.array[i+1];

}

this.length--;

}

Python

    #Delete by key, Time O(n), Space O(1), n is array length
    def delete(self, key) :
        del_index = self.search(key)
        if del_index == -1: 
            print("Item not found, return.")
            return        
        for i in range(del_index, self.num_items-1):        
            self.array[i] = self.array[i+1]
        self.num_items -= 1
    
    #Delete element at index, Time O(n), Space O(1), n is array length
    def delete_at(self, index) :
        if index >= self.num_items or index < 0 : 
            print("invalid index!")
            return
        for  i in range (index, self.num_items-1): 
            self.array[i] = self.array[i+1]
        self.num_items -= 1

#Delete by key, Time O(n), Space O(1), n is array length

def delete(self, key) :

del_index = self.search(key)

if del_index == -1:

print("Item not found, return.")

return

for i in range(del_index, self.num_items-1):

self.array[i] = self.array[i+1]

self.num_items -= 1

#Delete element at index, Time O(n), Space O(1), n is array length

def delete_at(self, index) :

if index >= self.num_items or index < 0 :

print("invalid index!")

return

for i in range (index, self.num_items-1):

self.array[i] = self.array[i+1]

self.num_items -= 1

Doodle

array delete

Linear search

Starting from the index 0, compare each element in the array with the key. Return the first matched element’s index. If the key is not found, return -1.

Java

    //Search by key, Time O(n), Space O(1)
    public int search(T key) {
        int i;
        for (i = 0; i < length; i++) {
            if (array[i] == key) 
            	break;                   
        }        
        if (i == length) 
            return -1; 
        else 
            return i;
    }

//Search by key, Time O(n), Space O(1)

public int search(T key) {

int i;

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

if (array[i] == key)

break;

}

if (i == length)

return -1;

else

return i;

}

Javascript

    //Search by key, Time O(n), Space O(1)
    search(key) {
      for (var i = 0; i < this.length; i++) {
        if (this.array[i] == key) {
          return i;
        }
      } 
      return -1;
    }

//Search by key, Time O(n), Space O(1)

search(key) {

for (var i = 0; i < this.length; i++) {

if (this.array[i] == key) {

return i;

}

return -1;

}

Python

    #Search by key, Time O(n), Space O(1)
    def search(self, key) :
        for i in range(0, self.num_items) : 
            if self.array[i] == key: 
                return i
        return -1

#Search by key, Time O(n), Space O(1)

def search(self, key) :

for i in range(0, self.num_items) :

if self.array[i] == key:

return i

return -1

Doodle

array search

Print elements

Print all elements in the array from index 0 to the last.

Java

    //Print array, Time O(n), Space O(1)
	public void print() {
	    for (int i = 0; i < length; i++) 
	        System.out.print(array[i] + " ");
	    System.out.println();
	}

//Print array, Time O(n), Space O(1)

public void print() {

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

System.out.print(array[i] + " ");

System.out.println();

}

Javascript

   //Print array, Time O(n), Space O(1)
    print() {
      var s = '';
      for (var i = 0; i < this.length; i++) {
        s += this.array[i] + ' ';
      }
      console.log('array is ' + s);
    }

//Print array, Time O(n), Space O(1)

print() {

var s = '';

for (var i = 0; i < this.length; i++) {

s += this.array[i] + ' ';

}

console.log('array is ' + s);

}

Python

    #Print array, Time O(n), Space O(1)
    def print(self) :
        for i in range( 0, self.num_items): 
            print(self.array[i], end = ' ' )
        print()

#Print array, Time O(n), Space O(1)

def print(self) :

for i in range( 0, self.num_items):

print(self.array[i], end = ' ' )

print()

Doodle

array search

Free download

Download the array class in Java, JavaScript and Python code
Data Structures Illustrated Python Book

Login

Implement an array class

Map of Array class implementations

Table of Content

Define an Array class and add elements

Java

Javascript

Python

Doodle

Delete an element

Java

Javascript

Python

Doodle

Linear search

Java

Javascript

Python

Doodle

Print elements

Java

Javascript

Python

Doodle

Free download

You may also like