Sequences As we have already seen, sequences are an abstract datatype representi

ID: 3598966 • Letter: S

Question

Sequences

As we have already seen, sequences are an abstract datatype representing the notion of ordered collections of objects of the same type. This tells us what the objects which inhabit this datatype look like, but not the operations that we can reasonably perform on them. To help with this, we can turn to the Sequence<T> interface given below in the Java programming language:

public interface Sequence<T> {

/**

* Adds the specified object to the end of the sequence.

* @param obj object to be appended to this sequence

void add(T obj);

/**

* Adds the specified object at the given position in the sequence.

* @param idx index at which the specified object is to be inserted

* @param obj object to be appended to this sequence

* @throws IndexOutOfBoundsException if the index is out of range

* (index < 0 || index > size())

void add(int idx, T obj) throws IndexOutOfBoundsException;

/**

* Removes all of the elements from the sequence.

void clear();

/**

* Returns the object at the specified position in the sequence.

* @param idx index of the element to return

* @return the object at the specified position in the sequence

* @throws IndexOutOfBoundsException if the index is out of range

* (index < 0 || index > size())

T get(int idx) throws IndexOutOfBoundsException;

/**

* Returns {@code true} if the sequence contains the specified object and

* {@code false} otherwise.

* @param obj the object to find in the sequence

* @return {@code true} if the sequence contains the specified object and

* {@code false} otherwise

boolean contains(T obj);

/**

* Returns the index of the first occurrence of the specified object in

* this sequence, or -1 if object is not present.

* @param obj the object to find in the sequence

* @return the index of the first occurrence of the specified object in

* this sequence, or -1 if object is not present

int indexOf(T obj);

/**

* Returns {@code true} if the sequence is empty and {@code false}

* otherwise.

* @return {@code true} if the sequence is empty and {@code false}

* otherwise

boolean isEmpty();

/**

* Removes the object at the specified position in the sequence.

* @param idx index of the element to remove

* @return the object previously at the specified position

* @throws IndexOutOfBoundsException if the index is out of range

* (index < 0 || index > size())

T remove(int idx) throws IndexOutOfBoundsException;

/**

* Remove the first occurrence of the specified object from the sequence,

* if it is present.

* @param obj the object to remove

* @return {@code true} if the sequence contained the specified object and

* {@code false} otherwise

boolean remove(T obj);

/**

* Returns the number of elements in the sequence.

* @return the number of elements in the sequence

int size();

/**

* Returns an array containing all of the elements in the sequence in the

* proper order (from first to last).

* @return an array containing the elements of the sequence

T[] toArray();

}

The first part of your project is to define a LinkedList<T> class which implements this interface. You will notice that there is no requirement to provide a definition for a toString() member function, this is left to your own discretion. In addition, pay attention to the specifications of the individual member functions: some of them may be of use in implementing others. Lastly, the interface only defines the minimal set of functions/methods that your implementation must provide (i.e. the public API through which objects of the LinkedList<T> type may be manipulated). This does not mean that you ought not define additional functions to help in implementing these.

Explanation / Answer

Hi,

Good Question. I have given the working code and inline-explanations.

If any doubt, let me know.

//Given Interface

interface Sequence<T>{

void add(T obj);

void add(int index, T obj);

void clear();

T get(int index);

boolean contains(T obj);

int indexOf(T obj);

boolean isEmpty();

T remove(T obj);

T remove(int index);

int size();

<T> T[] toArray();

}

//Next node in the list

class NextNodeLink<T> {

public T data1;

public NextNodeLink nextLink;

public NextNodeLink(T d1) {

data1 = d1;

}

//Actual list implementing the given interface

public class LinkedList<T> implements Sequence<T>{

private NextNodeLink first;

public LinkedList() {

first = null;

}

@Override

public boolean isEmpty() {

return first == null;

}

//Add element at the end

@Override

public void add(T obj) {

NextNodeLink<T> link = new NextNodeLink<T>(obj);

NextNodeLink<T> temp = first;

if(temp != null){

while(temp.nextLink != null){

temp = temp.nextLink;

}

temp.nextLink = link;

}else{

first = link;

}

//Add at the given position. Move the temp pointer to the index-1 position and inserts the element btw index-1 and index+1

@Override

public void add(int index, T obj) {

NextNodeLink<T> link = new NextNodeLink<T>(obj);

NextNodeLink<T> temp = first;

int i = 0;

if( index < 0 || index > this.size()){

System.out.println("Index("+index+") is greater than size of the list or Index is negative");

} else if(temp != null){

while(temp.nextLink != null && i < (index-1)){

temp = temp.nextLink;

i++;

}

link.nextLink = temp.nextLink;

temp.nextLink = link;

}

//Java GC will take care of removing the unused objects

@Override

public void clear() {

first = null;

}

//Iterate and return the element

@Override

public T get(int index) {

if(index > this.size() || index < 0){

System.out.println("Index("+index+") is greater than size("+this.size()+") of the list OR index is negative");

return null;

}

NextNodeLink<T> temp = first;

int i = 0;

while(temp != null && i < index){

temp = temp.nextLink;

i++;

}

return temp.data1;

}

//Iterate and look for the asked element

@Override

public boolean contains(T obj) {

NextNodeLink<T> temp = first;

while(temp != null){

if(temp.data1 == obj){

return true;

}

temp = temp.nextLink;

}

return false;

}

//Iterate and look for the given element and return the maintained counter

@Override

public int indexOf(T obj) {

NextNodeLink<T> temp = first;

int i = 0;

while(temp != null){

if(temp.data1 == obj){

return i;

}

temp = temp.nextLink;

}

return -1;

}

@Override

public T remove(T obj) {

NextNodeLink<T> temp = first;

if(temp.data1.equals(obj)){

first = first.nextLink;

return temp.data1;

}

while(temp.nextLink != null){

if(temp.nextLink.data1.equals(obj)){

temp.nextLink = temp.nextLink.nextLink;

return temp.data1;

}

temp = temp.nextLink;

}

return null;

}

@Override

public T remove(int index) {

if(index > this.size() || index < 0){

System.out.println("Index("+index+") is greater than size("+this.size()+") of the list OR index is negative");

return null;

}

NextNodeLink<T> toBeRemoved = null;

if(index == 0){

toBeRemoved = first;

first = first.nextLink;

} else{

NextNodeLink<T> temp = first;

int i = 0;

while(temp != null && i < (index-1)){

temp = temp.nextLink;

toBeRemoved = temp.nextLink;

i++;

}

temp.nextLink = temp.nextLink.nextLink;

}

return toBeRemoved.data1;

}

@Override

public int size() {

NextNodeLink<T> temp = first;

int i = 0;

while(temp != null){

i++;

temp = temp.nextLink;

}

return i;

}

@Override

public <T> T[] toArray() {

NextNodeLink<T> temp = first;

T[] data = (T[])new Object[this.size()];

int i =0;

while(temp != null){

data[i] = temp.data1;

temp = temp.nextLink;

i++;

}

return data;

}

@Override

public String toString(){

NextNodeLink<T> temp = first;

String data = new String();

while(temp != null){

data += temp.data1;

temp = temp.nextLink;

}

return data;

}

class LinkListTest {

public static void main(String[] args) {

LinkedList<String> list = new LinkedList<String>();

list.add("a");

list.add("c");

list.add("d");

list.add("e");