Take note this is in java programming.Answer the answers in java language. The f

Question

Take note this is in java programming.Answer the answers in java language.

The following remarks apply specifically for programming questions, if any:
1. Compile and test all codes before submitting to ensure that they are error free.
2. Provide the necessary comments in your source codes.
3. Include both codes and sample outputs (e.g. screen shots) in your answer script,
i.e. Word document. Additionally, attach also the original source codes (e.g. *.java
files) in the final zipped file for submission.
4. Note the differences between the codes for a complete Java program and Java
method.
Java program comprises all codes needed for compilation and execution of a
runnable system. A complete Java program can include multiple methods and
method calls. Modularity makes the entire program more readable and easier
to debug. You should always strive to modularize your codes.
A Java method on the other hand is limited to the implementation of
procedure/function performing a specific task.
5. Hence, read each question requirements properly in order to avoid loosing marks
unnecessarily.

Question 4 Given a list, L of n integers, write an algorithm to delete an element at position k assuming that k n). After the deletion, there should be no gap between any elements in L except for the last. For instance: .L (1,2, 3, 4, 5,6,7), k 2 After removing the th element, the intermediate L (1,2, 4, 5, 6, 7) After clearing the gaps, the final L (1,2, 4,5, 6, 7) (a) Implement the task using i. Array data structure. 10 marks ii. Linked list data structure 10 marks TCC 236/05 (b) Determine the complexity of each of your algorithms in terms of data movement and effort to delete the element. That is, in the worst case, how many times should the data in L be moved to fill the gap? Also, how many comparisons does it take to delete the k element? Provide the big-oh notation and explain your answers 10 marks

Explanation / Answer

public class MyArrayList {

private static final int SIZE_FACTOR=5;

private Object data[];

private int index;

private int size;

public MyArrayList(){
this.data=new Object[SIZE_FACTOR];
this.size=SIZE_FACTOR;
}

public void add(Object obj){
System.out.println("index:"+this.index+"size:"+this.size+"data size:"+this.data.length);
if(this.index==this.size-1){
//we need to increase the size of data[]
increaseSizeAndReallocate();
}
data[this.index]=obj;
this.index++;

}

private void increaseSizeAndReallocate() {
this.size=this.size+SIZE_FACTOR;
Object newData[]=new Object[this.size];
for(int i=0; i<data.length;i++){
newData[i]=data[i];
}
this.data=newData;
System.out.println("***index:"+this.index+"size:"+this.size+"data size:"+this.data.length);
}

public Object get(int i) throws Exception{
if(i>this.index-1){
throw new Exception("ArrayIndexOutOfBound");
}
if(i<0){
throw new Exception("Negative Value");
}
return this.data[i];

}

public void remove(int i) throws Exception{
if(i>this.index-1){
throw new Exception("ArrayIndexOutOfBound");
}
if(i<0){
throw new Exception("Negative Value");
}
System.out.println("Object getting removed:"+this.data[i]);
for(int x=i; x<this.data.length-1;x++){
data[x]=data[x+1];
}
this.index--;
}

public static void main(String[] args) throws Exception {
MyArrayList mal = new MyArrayList();
mal.add("0");
mal.add("1");
mal.add("2");
mal.add("3");
mal.add("4");
mal.add("5");
mal.add("6");
mal.add("7");
mal.add("8");
mal.add("9");

mal.remove(5);
System.out.println(mal.get(7));
}

}

// Editing in few min

b)

in linked list

In linked list you have to iterate from root node till kth node but after reaching just put kth node=null and done:

No comparisons are made.

complexity: 0(n)

in arraylist

we go directly to kth index. but after removing the elemnt we have to move all the (n-k) one index down

No comparisons are made.

complexity: 0(n) time.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.