Skip to content

dynamic array data structure #1272

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
May 3, 2020
Merged

dynamic array data structure #1272

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
dynamic array data structure
  • Loading branch information
@wesllhey
wesllhey committed Apr 10, 2020
commit e7ddedb37c5dc7b807f8e0f95b73091b6f016ed9
158 changes: 158 additions & 0 deletions DataStructures/DynamicArray/DynamicArray.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,158 @@
package DataStructures.DynamicArray;

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class DynamicArray<E> implements Iterable<E> {

private int capacity = 10;

private int size = 0;

private Object[] elements;

public DynamicArray(final int capacity) {
this.capacity = capacity;
this.elements = new Object[this.capacity];
}

public DynamicArray() {
this.elements = new Object[this.capacity];
}

public int newCapacity() {
this.capacity <<= 1;

return this.capacity;
}

public void add(final E element) {
if (this.size == this.elements.length)
this.elements = Arrays.copyOf(this.elements, newCapacity());

this.elements[this.size] = element;
size++;
}

public void put(final int index, E element) {
Objects.checkIndex(index, this.size);

this.elements[index] = element;
}

public E get(final int index) {
return getElement(index);
}

public E remove(final int index) {
final E oldElement = getElement(index);
fastRemove(this.elements, index);

return oldElement;
}

public int size() {
return this.size;
}

public boolean isEmpty() {
return this.size == 0;
}

public Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}

private void fastRemove(final Object[] elements, final int index) {
final int newSize = this.size - 1;

if (newSize > index)
System.arraycopy(elements, index + 1, elements, index, newSize - index);

elements[this.size = newSize] = null;
}

private E getElement(final int index) {
Objects.checkIndex(index, this.size);
return (E) this.elements[index];
}

@Override
public String toString() {
return Arrays.toString(Arrays.stream(this.elements).filter(Objects::nonNull).toArray());
}

@Override
public Iterator iterator() {
return new DynamicArrayIterator();
}

private class DynamicArrayIterator implements Iterator<E> {

private int cursor;

@Override
public boolean hasNext() {
return this.cursor != size;
}

@Override
public E next() {
if (this.cursor > DynamicArray.this.size) throw new NoSuchElementException();

if (this.cursor > DynamicArray.this.elements.length) throw new ConcurrentModificationException();

final E element = DynamicArray.this.getElement(this.cursor);

this.cursor++;

return element;
}

@Override
public void remove() {
if (this.cursor < 0) throw new IllegalStateException();

DynamicArray.this.remove(this.cursor);

this.cursor--;
}

@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);

for (int i = 0; i < DynamicArray.this.size; i++) {
action.accept(DynamicArray.this.getElement(i));
}
}
}

public static void main(String[] args) {
DynamicArray<String> names = new DynamicArray<>();
names.add("Peubes");
names.add("Marley");

for (String name : names) {
System.out.println(name);
}

names.stream().forEach(System.out::println);

System.out.println(names);

System.out.println(names.size());

names.remove(0);

for (String name : names) {
System.out.println(name);
}
}
}