-
-
Save sricharankrishnan/36defc44723412c4a49910f18c973837 to your computer and use it in GitHub Desktop.
A dynamic array data structure implementation done in java along with applicable time complexities
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* DSA Implementation Example: Array (Dynamic). | |
* The time complexities are as follows: | |
* 1. public E get(int index) - O(1) | |
* 2. public void set(int index, E value) - O(1) | |
* 3. public void add(E value) - O(1) Amortized or O(n) Worst Case | |
* 4. public void remove(int index) - O(n) | |
**/ | |
import java.util.*; | |
public class DynamicArray<E> { | |
private int size; | |
private int capacity; | |
private Object[] elements; | |
public DynamicArray() { | |
this.size = 0; | |
this.capacity = 5; | |
this.elements = new Object[this.capacity]; | |
} | |
/* O(1) */ | |
public E get(int index) { | |
if (this.isEmpty()) { | |
return null; | |
} | |
else if (index < 0 || index >= this.size) { | |
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds."); | |
} | |
else { | |
return (E) this.elements[index]; | |
} | |
} | |
/* O(1) */ | |
public void set(int index, E value) { | |
if (!Objects.isNull(value)) { | |
if (index < 0 || index >= this.size) { | |
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds."); | |
} | |
else { | |
this.elements[index] = value; | |
} | |
} | |
} | |
/* O(1) or O(n) */ | |
public void add(E value) { | |
if (this.isFull()) { | |
int capacity = (this.capacity == 0) ? 1 : this.capacity * 2; | |
this.resize(capacity); | |
} | |
this.elements[this.size++] = value; | |
} | |
/* O(n) */ | |
public void remove(int index) { | |
if (!this.isEmpty()) { | |
if (index < 0 || index >= this.size) { | |
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds."); | |
} | |
else { | |
for (int i = index; i < this.size - 1; ++i) { | |
this.elements[i] = this.elements[i + 1]; | |
} | |
--this.size; | |
this.elements[this.size] = null; | |
/* resizing - to ensure that we dont take up too much memory */ | |
if (this.size > 1 && (this.size <= (this.capacity/4))) { | |
this.resize(this.capacity/2); | |
} | |
} | |
} | |
} | |
private void resize(int capacity) { | |
this.capacity = capacity; | |
Object[] array = new Object[capacity]; | |
for (int i = 0; i < this.size; ++i) { | |
array[i] = (E) this.elements[i]; | |
} | |
this.elements = array; | |
} | |
public boolean isEmpty() { | |
return this.size == 0; | |
} | |
public boolean isFull() { | |
return this.size == this.capacity; | |
} | |
public int size() { | |
return this.size; | |
} | |
public String toString() { | |
String string = "["; | |
for (int i = 0; i < this.size; ++i) { | |
string += (i == this.size - 1) ? this.elements[i] : this.elements[i] + ", "; | |
} | |
return string += "]"; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment