NOTE!!!!: WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHIN
ID: 3803630 • Letter: N
Question
NOTE!!!!:
WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHING FROM THE JAVA API, PLEASE SOLVE THE PROBLEM BELOW.
WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHING FROM THE JAVA API, PLEASE SOLVE THE PROBLEM BELOW.
WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHING FROM THE JAVA API, PLEASE SOLVE THE PROBLEM BELOW.
WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHING FROM THE JAVA API, PLEASE SOLVE THE PROBLEM BELOW.
WITHOUT ALTERING THE ABSTRACTLINKEDLIST.JAVA FILE OR IMPORTING ANYTHING FROM THE JAVA API, PLEASE SOLVE THE PROBLEM BELOW.
For this program, you will be given an abstract class AbstractLinkedList.java; it is an implementation of a doubly-linked list with dummy header and tail. The class definition includes a fully implemented, generic Node class. You are to write the class MyLinkedList that implements all the abstract methods of the AbstractLinkedList class (specifically, remove, contains, get, indexOf, lastIndexOf, getNodeAt, toArray, and toString)
Below you will find the AbstractLinkedList.java file:
DO NOT ALTER THIS CODE. DO NOT ALTER THIS CODE. DO NOT ALTER THIS CODE. DO NOT ALTER THIS CODE. DO NOT ALTER THIS CODE. DO NOT ALTER THIS CODE.
/*
Models a doubly-linked list with dummy header and tail.
You should extend this class with your MyLinkedList to complete
the implementation.
*/
public abstract class AbstractLinkedList<E> {
protected final Node<E> myFront, myBack; // dummy header/tail
protected int mySize; // # of elements in list
/* Constructs a new empty list. */
public AbstractLinkedList() {
myFront = new Node<E>(null);
myBack = new Node<E>(null);
myBack.setPrevious(myFront);
myFront.setNext(myBack);
mySize = 0;
}
/* Inserts the given element at the given index. */
public void add(int index, E element) {
checkIndex(index, size());
Node<E> curr = getNodeAt(index);
// create the new node to hold the new element
Node<E> newNode = new Node<E>(element, curr.getPrevious(), curr);
(newNode.getNext()).setPrevious(newNode);
(newNode.getPrevious()).setNext(newNode);
mySize++;
}
/* Appends the given element to the end of this list. Returns true. */
public void add(E element) {
add(size(), element);
}
/*
Removes the element of this list at the given index and returns it.
Throws IndexOutOfBoundsException if index is out of range.
*/
public void remove(int index) {
checkIndex(index, size() - 1);
// get the node to remove, and update the references
Node<E> nodeToRemove = getNodeAt(index);
(nodeToRemove.getPrevious()).setNext(nodeToRemove.getNext());
(nodeToRemove.getNext()).setPrevious(nodeToRemove.getPrevious());
mySize--;
}
/*
Sets the element of this list at the given index to have the given value.
Throws IndexOutOfBoundsException if index is out of range.
*/
public void set(int index, E value) {
checkIndex(index, size() - 1);
getNodeAt(index).element = value;
}
/* Returns the number of elements in this list. */
public int size() {
return mySize;
}
/* Returns true if this list contains no elements. */
public boolean isEmpty() {
return mySize == 0;
}
/* Removes all elements from this list. */
public void clear() {
myFront.setNext(myBack);
myBack.setPrevious(myFront);
mySize = 0;
}
/*
Helper method: Throws an IndexOutOfBoundsException
if 0 <= index <= max is not true.
*/
private void checkIndex(int index, int max) throws IndexOutOfBoundsException{
if (index < 0 || index > max)
throw new IndexOutOfBoundsException();
}
/*
Removes the given element from this list, if it is present in the list.
Returns true if the element was in the list and was removed.
*/
public abstract boolean remove(E element);
/* Returns true if this list contains the given element. */
public abstract boolean contains(E element);
/*
Returns the element of this list at the given index.
Throws IndexOutOfBoundsException if index is out of range.
*/
public abstract E get(int index);
/*
Returns the first index where the given element occurs in this list,
or -1 if the element is not in this list.
*/
public abstract int indexOf(E element);
/*
Returns the last index where the given element occurs in this list,
or -1 if the element is not in this list.
*/
public abstract int lastIndexOf(E element);
/*
Helper method: returns the node at the given index.
-1 returns dummy header, and size() returns the dummy tail.
Consider the effiency of this method. How can you write it
minimize the number of comparisons?
*/
protected abstract Node<E> getNodeAt(int index) throws IndexOutOfBoundsException;
/*
Returns an array containing all of the elements in this list
in the correct order.
*/
public abstract E[] toArray();
/*
Returns a String representation of this list.
*/
public abstract String toString();
/* Represents one doubly-linked node in the list. */
protected class Node<E> {
private E element; /* The data element */
private Node<E> next; /* Reference to the next node in the list */
private Node<E> prev; /* Reference to the previous node in the list */
/* Constructs a new node to store the given element, with no next node. */
public Node(E element) {
this(element, null, null);
}
/* Constructs a new node to store the given element and the given next node. */
public Node(E element, Node<E> prev, Node<E> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
/* Accessor methods. */
public E getElement(){
return element;
}
public Node<E> getNext(){
return next;
}
public Node<E> getPrevious(){
return prev;
}
/* Mutator methods.*/
public void setElement(E el){
element = el;
}
public void setNext(Node<E> newNext){
next = newNext;
}
public void setPrevious(Node<E> newPrev){
prev = newPrev;
}
/* Returns a string representation of this node. */
public String toString() {
return "(" + element + ")";
}
}
}
Explanation / Answer
MyLinkedList.java
/**
* Custom MyLinkedList - extends AbstractLinkedList
* @author Anonymous
*
* @param <E>
*/
public class MyLinkedList<E> extends AbstractLinkedList<E>{
public boolean remove(E element) {
int index = indexOf(element);
if(index == -1) //element not present
return false;
//Remove method in abstract class
super.remove(index);
return true;
}
@Override
public boolean contains(E element) {
Node<E> current = getNodeAt(-1);
boolean contains = false;
while(current!=getNodeAt(size())){
if(current.getElement()==element){
contains = true;
break;
}
current = current.getNext();
}
return contains;
}
@Override
public E get(int index) {
Node<E> node = getNodeAt(index);
return node.getElement();
}
@Override
public int indexOf(E element) {
Node<E> current = myFront.getNext();
int index = 0;
while(current!=myBack){
if(current.getElement() == element){
return index;
}
current = current.getNext();
index++;
}
return -1;
}
@Override
public int lastIndexOf(E element) {
//Traversing from end of list backwards
Node<E> current = myBack;
int index = size();
while(current!=myFront){
if(current.getElement() == element){
return index;
}
current = current.getPrevious();
index--;
}
//If not found, return -1
return -1;
}
@Override
protected AbstractLinkedList<E>.Node<E> getNodeAt(int index) throws IndexOutOfBoundsException {
if(index < -1 || index > size())
throw new IndexOutOfBoundsException();
//index = size of list, return dummy back node
if(index == size())
return myBack;
Node<E> current = myFront;
int i = -1;
while(i<index){
current = current.getNext();
i++;
}
return current;
}
@SuppressWarnings("unchecked")
@Override
public E[] toArray() {
E[] arr = (E[])new Object[size()];
//Current node to first item in the list
Node<E> current = myFront.getNext();
//i = 0 - first item
int i=0;
while(current!=myBack){
arr[i] = current.getElement();
current = current.getNext();
i++;
}
return arr;
}
@Override
public String toString() {
Node<E> current = myFront.getNext();
StringBuilder builder = new StringBuilder();
while(current!=myBack){
builder.append(current.toString());
current = current.getNext();
}
return builder.toString();
}
}
Main.java : Test class used to test MyLinkedList class
public class Main {
public static void main(String args[]){
MyLinkedList<Integer> list = new MyLinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(5);
System.out.println(list.toString());
list.add(3,4);
System.out.println(list.toString());
System.out.println(list.contains(6));
System.out.println(list.contains(4));
System.out.println(list.indexOf(2));
System.out.println(list.indexOf(4));
list.add(5,4);
System.out.println(list.toString());
System.out.println(list.lastIndexOf(4));
System.out.println(list.remove((Integer)6));
System.out.println(list.toString());
System.out.println(list.get(2));
System.out.println(list.indexOf(8));
System.out.println(list.lastIndexOf(8));
Object[] arr = list.toArray();
for(Object o:arr){
Integer i = (Integer)o;
System.out.print(i+" ");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.