Question

Would someone be able to help me with this please? It has to do with Linked List Arrays, and I'm very confused on what to do. Any help along with steps would be very much appreciated. Cheers!

You are hired by a company to implement a singly-linked list that will hold integers, using Java programming language. However, the boss of the company insists that you don’t use any objects or structures in your implementation. You may use only integer arrays and individual integer variables.

Your implementaion should support the following operations:

• Insertion of the first integer element as the head of the list that will contain at most n elements throughout its lifetime.

• Keeping track of the ‘current’ element in the list (initially should be the head of the list)

• Advance ‘current’ to the next element in the list

• Reset ‘current’ to the head of the list

• Return the integer value of the ‘current’ element

• Insert a new value following the ‘current’ element in the list (should have no effect if n elements already had been inserted into the list)

• Delete the element following the ‘current’ element in the list (should have no effect if the ‘current’ element is the last one in the list)

  The boss also insists that your implementation is efficient and every operation should run in O(1)time, no matter what sequence of operations is performed. This is very important to the success of the company and they will not accept any code that is less efficient!

  Fill in the missing code in the following definitions and explain why every one of your operations runs inO(1) time:

1

public class List {
  private int ...
  private int[] ...

  /*********************************************************************
   * Initializes a linked list with integer ’val’ as the head of the list
   * and identifies it as the current element
   * Ensures that no more than ’n’ elements will be inserted into this list
   *********************************************************************/

  public List(int n, int val) {
    ...

}

  /*********************************************************************
   * Advances the current element to the next element in the linked list
   *********************************************************************/

  public void advance() {
    ...

}

  /*********************************************************************
   * Resets the current element to be the head of the list
   *********************************************************************/

  public void reset() {
    ...

}

  /*********************************************************************
   * Returns the integer value of the current element
   *********************************************************************/

  public int value() {
    ...

}

  /*********************************************************************
   * Deletes the element that follows the current element in the list
   * Has no effect if the current element is the last one in the list
   *********************************************************************/

  public void deleteNext() {
    ...

}

  /*********************************************************************
   * Inserts ’val’ into the list as the element that follows the current
   * one. Has no effect if n elements had already been inserted into the list
   * (not counting deletions)
   **********************************************************************/

  public void insertNext(int val) {
    ...

} }

Answer 1

public class List {
private int val;
private int[] elements;
/*********************************************************************
* Initializes a linked list with integer ’val’ as the head of the list
* and identifies it as the current element
* Ensures that no more than ’n’ elements will be inserted into this list
*********************************************************************/
public List(int n, int val) {
this.elements = new int[n];
this.val=0;
}

/*********************************************************************
* Advances the current element to the next element in the linked list
*********************************************************************/
public void advance() {
if(this.val<elements.length - 1)
this.val++;
}

/*********************************************************************
* Resets the current element to be the head of the list
*********************************************************************/
public void reset() {
this.val=0;
}

/*********************************************************************
* Returns the integer value of the current element
*********************************************************************/
public int value() {
return elements[this.val];
}

/*********************************************************************
* Deletes the element that follows the current element in the list
* Has no effect if the current element is the last one in the list
*********************************************************************/
public void deleteNext() {
if(this.val<elements.length - 1)
elements[++this.val]=0;
}

/*********************************************************************
* Inserts ’val’ into the list as the element that follows the current
* one. Has no effect if n elements had already been inserted into the list
* (not counting deletions)
**********************************************************************/
public void insertNext(int val) {
if(this.val<elements.length - 1)
elements[++this.val]=val;
}
}