1) Simple Array List
package com.tcs.hdfc.bancs.arraylist;
import java.util.Arrays;
interface SimpleList {
/* This will get the object at the given index */
public Object get(int index);
public void set(int index, Object element);
public void add(int index, Object element);
public void add(Object element);
public Object remove(int index);
public Object remove(Object obj);
public int size();
public void clear();
}
class SimpleArrayList implements SimpleList {
private Object[] array;
SimpleArrayList(Object[] originalArray) {
if (null != originalArray) {
array = new Object[originalArray.length];
for (int i = 0; i < originalArray.length; i++) {
array[i] = originalArray[i];
}
}
}
/* This will get the object at the given index */
public Object get(int index) {
// if index is invalid then return null : -ve or can out of range
// else return array[index]
if (index < 0 || index > array.length - 1) {
return null;
} else {
return array[index];
}
}
/**
* This function will set the value at the given index Hint : kind of replacing
* the value
*/
public void set(int index, Object element) {
}
/**
* This add will add the value at the given index and shift the other elements
*/
public void add(int index, Object element) {
// since you are increasing the number of elements
// you need to resize your array
// { 12, 34, 18, 19 };
int prevArraySize = array.length;
Object[] newArray = new Object[prevArraySize + 1];
// {null,null,null,null,null}
// copy old to new
for (int i = 0; i < array.length; i++) {
newArray[i] = array[i];
}
// {12 ,34,18,19,null}
// shift : start shifting from given index
for (int i = newArray.length - 1; i > index; i--) {
newArray[i] = newArray[i - 1];
// {12 ,34,18,19,null}
// i=4
// {12 ,34,18,19,19}
// i=3
// {12 ,34,18,18,19}
// i=2
}
// {12, 34, 18 , 18, 19}
// replace the given element with the element at given index
newArray[index] = element;
array = newArray;
}
/**
* This add will add the value at the end;
*/
public void add(Object element) {
// add value at the end
// index = array.length // 4: last index
add(array.length, element);
}
/**
* This function will remove the value at the given index and also will return
* the same. Object valueToReturn = array[index] [12, 34, 100, 18, 19] index = 3
* Copy values from 0-index-1 (inclusive) and index (Exclusive) - length into
* new array array = newArray return valueToReturn
*
*/
public Object remove(int index) {
return null;
}
/**
* This function will remove the value based on the object value passed
*/
public Object remove(Object obj) {
return null;
}
/**
* This function will remove all the elements
*/
public void clear() {
}
public int size() {
return array.length;
}
public String toString() {
return Arrays.toString(array);
}
}
public class TestSimpleArrayList {
public static void main(String[] args) {
// way 1
Integer[] ageArray = { 12, 34, 18, 19 };
SimpleArrayList simpleArrayList = new SimpleArrayList(ageArray);
Integer integer = (Integer) simpleArrayList.get(2);
Object age2 = simpleArrayList.get(3);
System.out.println(integer);
System.out.println(age2);
// test case for invalid index
System.out.println(simpleArrayList.get(9));
// java.lang.ArrayIndexOutOfBoundsException: 9
System.out.println(simpleArrayList.get(-1));
System.out.println(simpleArrayList.get(4));
System.out.println(simpleArrayList);
simpleArrayList.add(2, 100);
// 12 34 100 18 19
System.out.println(simpleArrayList);
simpleArrayList.add(90);
System.out.println(simpleArrayList);
}
}
Fail fast Iterator :
import java.util.Arrays;
import java.util.ConcurrentModificationException;
interface SimpleIterator {
public boolean hasNext();
public Object next();
public Object currentElement();
public Object remove();
public void reset();
}
interface SimpleList {
/**
* Get will return object present at the given index else will return null
*
* @param index
* @return
*/
public Object get(int index);
void clear();
/**
* Set will be used to replace or update the value at the given index else do
* nothing
*
* @param index
* @param element
*/
public void set(int index, Object element);
/**
* Add will be used to add the value at the given index and shift the rest of
* the values
*
* @param index
* @param element
*/
public void add(int index, Object element);
public void add(Object element);
public Object remove(int index);
public Object remove(Object element);
public int contains(Object element);
public int size();
public SimpleIterator iterator();
}
class SimpleArrayList implements SimpleList {
private Object[] array;
private int modCount;
public SimpleArrayList(Object[] recArray) {
if (null != recArray) {
array = new Object[recArray.length];
for (int i = 0; i < recArray.length; i++) {
array[i] = recArray[i];
}
}
}
/**
* Get will return object present at the given index else will return null
*
* @param index
* @return
*/
@Override
public Object get(int index) {
if (index >= 0 && index < array.length) {
return array[index];
}
return null;
}
@Override
public void set(int index, Object element) {
if (index >= 0 && index < array.length) {
modCount++;
array[index] = element;
}
}
/**
* Add will be used to add the value at the given index and shift the rest of
* the values
*
* @param index
* @param element
*/
@Override
public void add(int index, Object element) {
/*
* 0) Valid index 1) Resize : increase by one : new array 2) Copy old values to
* new array Create a vacancy by shifting to right after the index { 23, 56, 12,
* -90, 56, 13 }; add(3,89) {null,null,null,null,null,null} { 23, 56, 12, 89
* ,-90, 56, 13 };
*/
if (index >= 0 && index <= array.length) {
modCount++;
int size = array.length;
Object[] newArray = new Object[size + 1];
for (int i = 0; i < index; i++) {
newArray[i] = array[i];
}
newArray[index] = element;
int j = index + 1;
for (int i = index; i < array.length; i++) {
newArray[j++] = array[i];
}
array = newArray;
}
}
@Override
public String toString() {
return Arrays.toString(array);
}
@Override
public void add(Object element) {
add(array.length, element);
}
@Override
public Object remove(int index) {
/*
* 1) Valid index 2) take a copy of object to return 3) Create a new array of
* one size less 4) { 23, 56, 12, 89 ,-90, 56, 13 } remove(3) 5) Copy 0: < index
* and copy index+1 : length
*/
Object objToReturn = null;
if (index >= 0 && index < array.length) {
modCount++;
objToReturn = array[index];
Object[] newArray = new Object[array.length - 1];
int j = 0;
for (int i = 0; i < array.length; i++) {
if (i != index) {
newArray[j++] = array[i];
}
}
array = newArray;
}
return objToReturn;
}
@Override
public Object remove(Object element) {
int index = contains(element);
return remove(index);
}
@Override
public int contains(Object element) {
int index = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] == element || array[i].equals(element)) {
index = i;
break;
}
}
return index;
}
@Override
public int size() {
return array.length;
}
@Override
public void clear() {
modCount++;
array = new Object[0];
}
@Override
public SimpleIterator iterator() {
return new SimpleListIterator();
}
private class SimpleListIterator implements SimpleIterator {
// private SimpleArrayList simpleArrayList;
private int position;
int expectedModCount = modCount;
@Override
public boolean hasNext() {
if (position < array.length) {
return true;
}
return false;
}
@Override
public Object next() {
checkForComodification();
return array[position++];
}
@Override
public Object currentElement() {
checkForComodification();
if (position < array.length) {
return array[position];
}
return null;
}
@Override
public Object remove() {
/*
* 1) Valid index 2) take a copy of object to return 3) Create a new array of
* one size less 4) { 23, 56, 12, 89 ,-90, 56, 13 } remove(3) 5) Copy 0: < index
* and copy index+1 : length
*/
checkForComodification();
Object objToReturn = null;
if (position >= 0 && position < array.length) {
objToReturn = array[position];
Object[] newArray = new Object[array.length - 1];
int j = 0;
for (int i = 0; i < array.length; i++) {
if (i != position) {
newArray[j++] = array[i];
}
}
array = newArray;
expectedModCount = modCount;
}
return objToReturn;
}
@Override
public void reset() {
checkForComodification();
position = 0;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
/**
* This class will test the SimpleArrayList class
*
* @author mohitmalhotra
*
*/
public class TestSimpleArrayList {
public static void main(String[] args) {
Integer[] integers = { 23, 56, 12, -90, 56, 13 }; // 6
Double[] doubles = { 23.9, 56.34, 12.55, -90.67, 56.56, 13.0 }; // 6
SimpleList simpleList1 = new SimpleArrayList(integers);
System.out.println("Calling get method at index 4 " + simpleList1.get(4));
System.out.println("Calling get method at index 90 " + simpleList1.get(90));
System.out.println("Before set() " + simpleList1);
System.out.println("Calling set(4,100)");
simpleList1.set(4, 100);
System.out.println("After set() " + simpleList1);
System.out.println("Before add(3,89) " + simpleList1);
System.out.println("Calling add(3,89)");
simpleList1.add(3, 89);
System.out.println("After add(3,89) " + simpleList1);
System.out.println("Before add(900) " + simpleList1);
System.out.println("Calling add(900)");
simpleList1.add(900);
System.out.println("After add(900) " + simpleList1);
System.out.println("Before remove(3) " + simpleList1);
System.out.println("Calling remove(3)");
Object element = simpleList1.remove(3);
System.out.println("After remove(3) element is " + element + " List is " + simpleList1);
System.out.println("Before remove(-90) " + simpleList1);
System.out.println("Calling remove(-90)");
Object element1 = simpleList1.remove(new Integer(-90));
System.out.println("After remove(-90) element is " + element1 + " List is " + simpleList1);
System.out.println("size of simple list is " + simpleList1.size());
for (int i = 0; i < simpleList1.size(); i++) {
if ((Integer) simpleList1.get(i) % 2 == 1) {
System.out.println("num is odd " + simpleList1.get(i));
}
}
System.out.println("Iterating through iterator");
System.out.println(simpleList1);
SimpleIterator simpleIterator1 = simpleList1.iterator();
// Correct code
// while (simpleIterator1.hasNext()) {
// simpleIterator1.remove();
// }
//
while (simpleIterator1.hasNext()) {
simpleList1.remove(simpleIterator1.next());
}
// Incorrect code to while "adding"
// while (simpleIterator1.hasNext()) {
// simpleList1.add(simpleIterator1.next());
// }
/*
* new Thread(()->{ simpleIterator1.remove(); }).start();
*
* new Thread(()->{ simpleIterator1.remove(); }).start();
*/
System.out.println(simpleList1);
// SimpleIterator simpleIterator12= simpleList1.listIterator(3); // 3 2
// 1 0
// while(simpleIterator1.hasPrevious()) {
// System.out.println(simpleIterator1.previous());
// }
simpleList1.clear();
System.out.println(simpleList1);
System.out.println("size of simple list after clear is " + simpleList1.size());
}
}
Last updated
