Help starting an assingment

[LeslieMJ]

Hello.

this is my first post on these forums so bear with me if you can.

i have a java assignment that requires us to implement an arraylist class ourselves without importing from java.util.

for some reason my brain is not wrapping itself around this problem. i am going to copy and paste the assignment so it can be seen.

{
Your programming assignment is to implement an ArrayList class yourself (rather than using the class already in Java. That means DO NOT import java.util.ArrayList as that will confuse the compiler.)

You need not use any type parameter, so all elements of the ArrayList will be of type Object. You need to create a private array of type Object that will hold the elements; it could start out at length 10. If the user tries to add more elements than the array can hold, you need to create another array, and then copy the existing elements from the old array to the new one. The new array should be twice the size of the old one. You may need to repeat this process if the new array is exceeded.

Here is the interface you need to implement for ArrayList:
public ArrayList( ) // constructor that creates the private array
public void add(Object element) // add an element to the list
public Object get(int i) // return the element at index i
public int size( ) // return the number of elements in the list (which is NOT necessarily the length of your private array)
public void clear( ) // remove all elements from the list
public boolean isEmpty( ) // obvious
public String toString( ) // returns a String like [ firstElement, secondElement, … ] where you get the first element etc. by calling the to String method of each element in the list. Example [“Per”,”Tom”,”Kari”].

Also create a Main class that tests all functionality of your ArrayList implementation. It is best to do the complete Main class before you even start on the ArrayList class. When you start the ArrayList class, first make dummy methods so that the Main class can compile. Of course, all of your positive test should fail at first, and then they will succeed one by one as you fill in the bodies.
}

i am not looking for someone to complete this assignment for me as that would not be good for my learning. i am trying to figure out how to start this thing, most notably the add method. i don't know why my brain wont compute this assignment, but it will not do it and it is driving me crazy.

if someone would be able to push me in the right direction, i am hoping that will throw the lightswitch on in my head so i can stop feeling like an idiot.

Thanks in advance for any help.

V/R
Leslie

[ozzyman]

well that means you need to use a usual array, any type means Object, so you start with something like this:

Object[] ArrayList = new Object[10];

i used 10 because when you create an java.util.ArrayList the initial size is 10 unless specified.

when an item is added, if more items are required, firstly a new array with the correct size must be initialised, and then the original contents + the new contents copied to it, then you can return the new array.


hope this helps

[sunde887]

Re read the question until you fully understand it. Your job is to create a class with an array of objects which is changed by the methods. Try starting it and wee where you get stuck, when you do get stuck, please post your code and what is giving you trouble.

[LeslieMJ]

OK

First off i want to say thank you for the people that have answered me so far and given me some insight. i went back and worked on the code methods that were not giving me trouble. so far the only method giving me trouble is the add method.

everything else i have kept simple for right now so i have a foundation from which to work from and make the code better.

This add method though is driving me batty. i know when you import the ArrayList and Array from java.util, i am able to use the .add command to populate the array, but since i cant import and have to write it myself, i am having a hard time figuring out how to write this add method so that i can pull from it.

i do not know why this is so hard for me. i dont know if i am overthinking the issue or just not seeing something, but this one method is slowly driving me nuts.

once again, anyhelp no matter how small or trivial is appreciated.




(Code)
public class ArrayList {
private Object[] arrList;


public ArrayList(){ Object[] arrList = new Object[10];
}
public void add(Object element){

}

public Object get(int i){
return arrList[i];


}
public int size(){
return arrList.length;
}

public void clear(){
arrList = null;
}
public boolean isEmpty(){
if(arrList.length == 0){
return true;
}
else{
return false;
}
}
public String toString(){
return arrList.toString();
}



}

[ozzyman]

what do we need to do when we add an item?
lets analyze the following code:

java.util.ArrayList<Integer> intList = new java.util.ArrayList<Integer>(0);
intList.add(10);

the current length is 0, but we need to add an item, so first is first:
- ensure we have enough capacity;
- correct capacity is size() + 1;
then we create a temporary array with the correct size
- initialise new array[size()+1];
copy the current items to the new array with a loop
- for index item, new array[index] = ArrayList[index];
- new array[last index] = new item
return the new array
- clear the ArrayList
- initialize ArrayList with the right size
- copy items from temp 'new array'

[sunde887]

You need to make sure you are doubling the array size, not adding 1 to it.

You have to test how big the underlying array is. If it is the same as it's length, then you need to change the size before adding an element. If the underlying array has spaces left, then you simply add it to the first available spot in the array.

Lets say it is full, then you need to create a new array, which is 2 * the underlying arrays length. Then loop through the original array and add each item to this newly created array.

Next you need to set the underlying array to this new array, and add the input to the next open space in the underlying array.

public void add(Object o){
  if(array is not full){
    add o to next available spot in array
  }
  else{
    create new array that is originalArray.length * 2
    add each item from originalArray to newArray
    set original array to be the new array(originalArray = newArray)
    add the object to the next available space
  }
}

[ozzyman]

this isn't a challenge, please explain why you need to double the size?

say we have 10 items, and bearing in mind the .add method only adds 1 item, why can't the new size just be 10+1 = 11 items?

[sunde887]

It doesn't need to be twice the size, however, it will probably be a little quicker to not have to create a new array, and copy it on every add. Ultimately the main reason is this from the op.

You need not use any type parameter, so all elements of the ArrayList will be of type Object. You need to create a private array of type Object that will hold the elements; it could start out at length 10. If the user tries to add more elements than the array can hold, you need to create another array, and then copy the existing elements from the old array to the new one. The new array should be twice the size of the old one. You may need to repeat this process if the new array is exceeded.

Looks like the assignment is to double it.

[LeslieMJ]

i would like to thank both of you for your help. i am going to study what yall have wrote and sleep on it as the assignment is not due until tomorrow night. hopefully reading over your posts and thinking on them while i sleep will jog my memory.

Thanks again.

[Junky]

My 2 cents

What does size mean? It can either represent the length of the array or it represent the capacity ie how many elements are in the array. I'd encourage using a private instance variable to keep track of the capacity. Each time an element is added, increase it by one. Each time an element is deleted, decrease it by one. Do this and you will know where in the array the next element should be inserted.

[sunde887]

That is a great point junky makes. Size will always produce 10, 20, 40(etc) in it's current form.

[ozzyman]

sunde887 i'm not quite sure how that works still, what happens when he adds the .addAll method then?

ArrayList original = 1 item
double original size = 2
ArrayList newArL = 10 items
out of bound exception

besides i find it a bit random still, not to mention the waste of memory.

public void addAll(ArrayList arL) {
    for (Object o:arL) {
        original.add(o);
        //each run the size is doubled
        //size = originalSize*(2^iterations)
        //after <100 iterations size = 1 googol?
    }
}

[sunde887]

Im not trying to argue with you about this. To be honest I'm not sure if saving the space for 10 objects in memory is worse, or continually copying arrays is worse. I am merely pointing out that his assignment specs are to double the underlying arrays size. I also don't see an addAll method in the list of methods he needs to implement.

Also, the add method will only double the underlying array when it gets full.

Say you have 10 items in the array list, and you want to add a new one. Add will first create a new array

Object[] newArray = new Object[oldArray.length * 2];

Then it will copy the items into this new array, so there will be 10 filled items out of a total 20 available spaces, and the new item will be added to the array, making it have 11 filled spots 9 empty spots. Finally it will set the underlying array to be equal to the newly created array.

So you can call add 9 more times before a copy is needed.

I hope I am making myself clearer now.

I think where you may be confusing what Im saying was doubling on each add, where you only double the array if it's got 10, 20, 40, 80, 160, etc items in it already.

perhaps some pseudo code

public void add(Object o){
  if(underlying array is full){
    create new array that is 2 * the underlying arrays size
    copy original array to new array
    add o to new array
    set old array to new array
  }
  else{  //when the underlying array is not full
    add o to next available space in array
  }
}

Im aware my pseudo code isn't that great(sorry)

To the op: I really suggest you follow junkies advice and use a counter to keep track of the items in the array.

[ozzyman]

what is wrong with copying the original array to a temp one, and then copying back? better it uses up a little process than a lot more memory. your suggested method doesn't copy correctly the method of java.util.ArrayList because thats not what ArrayList does.

and even though you are saying to double the array size when it is full, that is besides the point. if the array length is 500 and you double it, you get 500 blanks, which is needless because you already know the correct size, which is size() + size of new items (.add = 1). if you didn't know the new size that would be different, and even then your method would be incorrect because the new size could be more than double.

worse than that, any time a loop is run over the array, it would use up a lot more processes anyway because there would be a lot more items to run through. besides that, if Junky never advised him to follow the actual number of items size() would give him incorrect size of items with your method.

[sunde887]

I suggest you check out the API's array list. They create a temp array of (size * 3) / 2 + 1

so if the underlying array has a size of 10, it gets bumped up to (10 * 3) / 2 + 1, or 16.

Check the code, I believe they do something similar to what I am suggesting(just there way doesn't double)

ugh. You are simply not understanding me. I left out the fact that you would have to also increment the counter. Either way, my method is very similar to the API's method.

With your method, if you have an array list with 500 items, to add one Item you would copy the 500 elements to a new array everytime you wanted to add an element?

[ozzyman]

According to the ArrayList API:
add(Object o)
Appends the specified element to the end of this list.

if the the list is 10 long and you add 1 item, according to you, the new item would be added to the 16th element. so when you use a function like .get(index) you wouldn't find your elements

and yes there is nothing wrong with copying.

[sunde887]

I suggest you view the source code to see exactly how they decided to do it.

Also, note it says append to the end of the list, and not end of the underlying array. Obviously my first approach was a bit off, and with junky's recomendation I will update my pseudocode

public void add(Object o){
  if(underlying array is full){
    create a temp int of underlying array * 2
    copy array to be new size
    add at index (size marker)
    increment size marker
  }
  else{
    add o at index (size marker)
    increment size marker
  }
}

This is very similar to the source code from the java class library for arrayList.

[ozzyman]

give me the link to the source code and i'll read it

and now what you're saying is, you need 2 arrays, 1 for keeping track of the indexes of the elements added, and 1 for the actual list.

'copy array to be new size' means that you can magically increase the size of the array without copying elements from 'b' to 'a' is it?

and what i'm getting at is if you double the array size or even multiply by 1.6, the bigger picture is that you could have 10s or 100s of lists in one program or many programs (if running programs simultaneously) and each object element could also be quite large, wasting a lot of memory. processing power isn't that important because all processors are very powerful. in todays term new mobile phones are having dual-core 1GHz processors but even if you look back 3 years ago my Nokia N95 had 233MHz which is enough to copy large arrays without freezing up.

[sunde887]

I sent you a private message, I use the following method to copy the array.

array = Arrays.copyOf(array, newSize);

Originally I would have used a loop, however; when scanning the source code I noticed they used copyOf.

Did you get my private message? I sent you my actualy code implementation to try and clear up what I am saying. I also included snippets of the java src. I will sent another pm with the location of the src.

[DarrylBurke]

Did you get my private message? I sent you my actualy code implementation

You don't really get what a forum is for, do you?

db