Skip to content

Instantly share code, notes, and snippets.

@sricharankrishnan
Last active March 22, 2023 07:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sricharankrishnan/36defc44723412c4a49910f18c973837 to your computer and use it in GitHub Desktop.
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
/**
* 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