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.
Part 1 – Array implementation
Part 2 – Sorted array implementation
Part 3 – Matrix implementation
Table of Content
Add element
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 25 26 27 |
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 23 |
class Array: #Constructor, Time O(1), Space O(1) def __init__(self, size): self.length = 0 self.array = [None]*size self.maxSize = size #Add one element, Time O(1), Space O(1) def add(self, value) : self.array[self.length] = value self.length += 1 #Add one element at index, Time O(n), Space O(1) def insertAt(self, value, index) : if index < 0 or index > self.length : print("invalid index") return self.length += 1 for i in range (self.length-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 23 |
//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 19 |
#Delete by key, Time O(n), Space O(1), n is array length def delete (self, key) : index = self.search(key) if index == -1 : print("key not found!") return for j in range(index, self.length-1, +1): self.array[j] = self.array[j+1] self.length -= 1 #Delete element at index, Time O(n), Space O(1), n is array length def deleteAt(self, index) : if index >= self.length or index < 0 : print("invalid index!") return for i in range (index, self.length-1, +1): self.array[i] = self.array[i+1] self.length -= 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.length, +1) : 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.length, +1): print(self.array[i], end = ' ' ) print() |
Doodle
Download Java, JavaScript and Python code
Array operations animated visual
Data structures and Java collections