An array is an index-based data structure, which means every element is referred 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 implementation of array operations – add, remove, search and traversal.
Most programming languages such as C, C++ and Java have built-in support for array. Some languages such as Python doesn’t have 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 array works under the hood.
Map of Array implementations
Part 1 – Array implementation
Part 2 – Sorted array implementation
Part 3 – Matrix 2d array implementation
Table of Content
Add element in Array
Add element at the end, or at the given index. In Java, you need check whether you have reached the max size.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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
Delete element
Delete the element by key or by index. You need to move the following elements to their preceding position.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#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
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
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//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
|
1 2 3 4 5 6 7 8 9 |
//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
|
1 2 3 4 5 6 |
#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
Print elements
Print all elements in the array from index 0 to the last.
Java
|
1 2 3 4 5 6 |
//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
|
1 2 3 4 5 6 7 8 |
//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
|
1 2 3 4 5 |
#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
Free download
Download Java, JavaScript and Python code
Data Structures Illustrated Python Book
When you delete an element in an array, why do you move the right elements left to fill the hole?
The data in an array are leftmost. There are no holes (missing data) between them. If holes were allowed, all the algorithms of arrays would become more complicated. The only empty spots are at the end.