1. Complete the method public int remove(Eelement). This method worked for the singly linked list,but now we need it to work for the doubly linked list. Make itupdate the necessary prev links.
2. Add the method public int removeLast(Eelement). This method should behave as the publicint remove(E element) method, but start from the tailrather than the head.
3. Add the methods public String toString() andpublic String reverseString(). The toString()method should return a string with all of the elements in order.The reverseString() method should return a string with all of theelements in reverse order. Use a space to separate elements.
4. Modify the method public boolean contains(Eelement). Currently, this method scans from the beginningto the end. Change the method to go from both ends at once to themiddle. Note that you will want 1 loop with two walkers.
5. Write a main method to test the class. You should thoroughlytest all of the methods worked on in this lab, calling othermethods as will be useful.

package datastructures;
public class OurLinkedList implements OurList{
private class Node{
E element; // the element the node contains
Node next; // a link to the next node in the list
Node prev; // a link to the previous node in the list
}
private int size;
private Node head;
private Node tail;

public OurLinkedList(){
size = 0;
head = null;
tail = null;
}

public void add(E element){
Node n = new Node();
n.element = element;
n.next = null;
n.prev = tail;
if(size == 0){
head = n;
}else{
tail.next = n;
}
tail = n;
size++;
}

public void add(E element, int index){
if(index > size){
throw new IndexOutOfBoundsException();
}else if(index == size){
add(element);
}else if(index == 0){
Node n = new Node();
n.element = element;
n.next = head;

n.prev = null;
head = n;
if(size == 0){
tail = n;
}
size++;
}else if(index < size/2){
Node walker = head;
for(int i = 0; i < index-1; i++){
walker = walker.next;
}
Node n = new Node();
n.element = element;
n.next = walker.next;
n.prev = walker;
walker.next.prev = n;
walker.next = n;
size++;
}else{
Node walker = tail;
for(int i = size-1; i > index+1; i--){
walker = walker.prev;
}
Node n = new Node();
n.element = element;
n.next = walker;
n.prev = walker.prev;
walker.prev.next = n;
walker.prev = n;
size++;
}
}

public E get(int index){
if(index >= size){
throw new IndexOutOfBoundsException();
}else if(index < size/2){
Node walker = head;
for(int i = 0; i < index; i++){
walker = walker.next;
}
return walker.element;
}else{
Node walker = tail;
for(int i = size-1; i > index; i--){
walker = walker.prev;
}
return walker.element;
}
}

public E remove(int index){

if(index >= size){
throw new IndexOutOfBoundsException();
}else if(index == 0){
E elem = head.element;
head = head.next;
if(head != null){
head.prev = null;
}
size--;
if(size == 0){
tail = null;
}
return elem;
}else if(index == size-1){
E elem = tail.element;
tail = tail.prev;
tail.next = null;
size--;
return elem;
}else if(index < size/2){
Node walker = head;
for(int i = 0; i < index; i++){
walker = walker.next;
}
E elem = walker.element;
walker.next.prev = walker.prev;
walker.prev.next = walker.next;
size--;
return elem;
}else{
Node walker = tail;
for(int i = size-1; i > index; i--){
walker = walker.prev;
}
E elem = walker.element;
walker.next.prev = walker.prev;
walker.prev.next = walker.next;
size--;
return elem;
}
}

public int remove(E element){
if(size == 0){
return -1;
}
if(head.element.equals(element)){
head = head.next;
size--;
if(size == 0){
tail = null;

}
return 0;
}

Node walker = head;
int position = 1;

while(walker.next != null &&!walker.next.element.equals(element)){
//walking as normal
walker = walker.next;
//increment position so we can return it
position++;
}
if(walker.next.element.equals(element)){
walker.next = walker.next.next;
size--;
return position;
}else{
return -1;
}
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}

public int indexOf(E element){
Node walker = head;
int position = 0;
while(walker != null){
if(walker.element.equals(element)){
return position;
}
walker = walker.next;
position++;
}
return -1;
}

public int lastIndexOf(E element){
Node walker = tail;
int position = size-1;
while(walker != null){
if(walker.element.equals(element)){
return position;

}
walker = walker.prev;
position--;
}
return -1;
}

public boolean contains(E element){
Node walker = head;
while(walker != null){
if(walker.element.equals(element)){
return true;
}
walker = walker.next;
}
return false;
}
//Empties the list
public void clear(){
head = null;
tail = null;
size = 0;
}
//Returns the first element
public E first(){
return head.element;
}
//Returns the last element
public E last(){
return tail.element;
}

package datastructures;public interface OurList{        public void add(int i);        //The default add inserts at the end of the list        //The version with an index inserts at the specified index        public void add(E element, int index);        //This method retrieves the specified element        //Note that get(0) corresponds to peek from a queue        //Note that get(listSize-1) corresponds to peek from a stack        public E get(int index);        //This method returns and removes the element at the specified index        //Note that remove(0) corresponds to remove from a queue        //Note that remove(listSize-1) corresponds to pop from a stack        public E remove(int index);        //This method finds and removes the specific element        //It will return the index from it was removed, or -1 otherwise        //In the default Java implementation it is instead a boolean        public int remove(E element);        //Returns true if the list is empty        public boolean isEmpty();        //Returns the size of the list        public int size();        //Returns the (first) index of a specified element        public int indexOf(E element);        //Returns the last index of a specified element        public int lastIndexOf(E element);        //Returns true if the element is in the list, false otherwise        public boolean contains(E element);        //Empties the list        public void clear();        //Returns the first element        public E first();        //Returns the last element        public E last();

If you could add a main method at the end as well, I'dappreciate it. Thank you!!

This is all the information given.

Answer rating: 100% (QA)

Certainly Heres an updated version of the OurLinkedList class that includes the requested modifications and a main method for testing java Copy code package datastructures public class OurLinkedList i... View the full answer