Im having trouble implenting these methods , any help would be appreciated. Than
ID: 3905375 • Letter: I
Question
Im having trouble implenting these methods , any help would be appreciated. Thank you in advance
DoublyLinkedList clone()
This method returns a shallow copy of this DoublyLinkedList. The nodes of this DoublyLinkedList are cloned but the values themselves are not cloned.
boolean contains(AnyType value)
This method returns true if this list contains the specified value, otherwise it returns false.
int indexOf(AnyType value)
This method returns the index of the first occurrence of the specified value in this list, or -1 if this list does not contain the value.
int lastIndexOf(AnyType value)
This method returns the index of the last occurrence of the specified value in this list, or -1 if this list does not contain the value
boolean removeFirstOccurrence(AnyType value)
This method removes the first occurrence of the specified value in this list (when traversing the list from head to tail). If the list does not contain the value, it is unchanged. The method returns true if the list contained the specified value, otherwise it returns false.
boolean removeLastOccurence(AnyType value)
This method removes the last occurrence of the specified value in this list (when traversing the list from head to tail). If the list does not contain the value, it is unchanged. The method returns true if the list contained the specified value, otherwise it returns false.
Object[] toArray()
This method returns an array containing all of the values in this list in proper sequence (from first to last value)
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// DoublyLinkedList.java
import java.util.Iterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
public class DoublyLinkedList<AnyType> implements List<AnyType> {
private static class Node<AnyType> {
private AnyType data;
private Node<AnyType> prev;
private Node<AnyType> next;
public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
setData(d);
setPrev(p);
setNext(n);
}
public AnyType getData() {
return data;
}
public void setData(AnyType d) {
data = d;
}
public Node<AnyType> getPrev() {
return prev;
}
public void setPrev(Node<AnyType> p) {
prev = p;
}
public Node<AnyType> getNext() {
return next;
}
public void setNext(Node<AnyType> n) {
next = n;
}
}
private int theSize;
private int modCount;
private Node<AnyType> header;
private Node<AnyType> trailer;
public DoublyLinkedList() {
header = new Node<AnyType>(null, null, null);
trailer = new Node<AnyType>(null, null, null);
modCount = 0;
clear();
}
public void clear() {
header.setNext(trailer);
trailer.setPrev(header);
theSize = 0;
}
public int size() {
return theSize;
}
public boolean isEmpty() {
return (size() == 0);
}
private Node<AnyType> getNode(int index) {
return (getNode(index, 0, size() - 1));
}
private Node<AnyType> getNode(int index, int lower, int upper) {
Node<AnyType> currNode;
if (index < lower || index > upper)
throw new IndexOutOfBoundsException();
int n = size();
if (index < n / 2) {
currNode = header.getNext();
for (int i = 0; i < index; i++)
currNode = currNode.getNext();
} else {
currNode = trailer;
for (int i = n; i > index; i--)
currNode = currNode.getPrev();
}
return currNode;
}
public AnyType get(int index) {
Node<AnyType> indexNode = getNode(index);
return indexNode.getData();
}
public AnyType set(int index, AnyType newValue) {
Node<AnyType> indexNode = getNode(index);
AnyType oldValue = indexNode.getData();
indexNode.setData(newValue);
return oldValue;
}
public boolean add(AnyType newValue) {
add(size(), newValue);
return true;
}
public void add(int index, AnyType newValue) {
addBefore(getNode(index, 0, size()), newValue);
}
private void addBefore(Node<AnyType> nextNode, AnyType newValue) {
Node<AnyType> prevNode = nextNode.getPrev();
Node<AnyType> newNode = new Node<AnyType>(newValue, prevNode, nextNode);
prevNode.setNext(newNode);
nextNode.setPrev(newNode);
theSize++;
modCount++;
}
public AnyType remove(int index) {
return remove(getNode(index));
}
private AnyType remove(Node<AnyType> currNode) {
Node<AnyType> prevNode = currNode.getPrev();
Node<AnyType> nextNode = currNode.getNext();
prevNode.setNext(nextNode);
nextNode.setPrev(prevNode);
theSize--;
modCount++;
return currNode.getData();
}
public DoublyLinkedList<AnyType> clone() {
//creating a new list
DoublyLinkedList<AnyType> list=new DoublyLinkedList<AnyType>();
/**
* copying the nodes and attributes
*/
for(int i=0;i<theSize;i++){
Node<AnyType> node=getNode(i);
list.add(node.getData());
}
list.theSize=this.theSize;
//list.modCount=this.modCount;
return list;
}
public boolean contains(AnyType value) {
// getting an iterator
Iterator<AnyType> it = iterator();
// looping through each elements
while (it.hasNext()) {
if (it.next().equals(value)) {
// found
return true;
}
}
// not found
return false;
}
/**
* @return the index of the given value if found, else -1
*/
public int indexOf(AnyType value) {
int index = -1;
Node<AnyType> temp = header;
while (temp != null) {
if (temp.data != null && temp.data.equals(value)) {
return index;
}
temp = temp.next;//moving to next node
index++;
}
return -1;// not found
}
/**
* @return the last index of the given value if found, else -1
*/
public int lastIndexOf(AnyType value) {
int index = theSize;
Node<AnyType> temp = trailer;
while (temp != null) {
if (temp.data != null && temp.data.equals(value)) {
return index;
}
temp = temp.prev; //moving to previous node
index--;
}
return -1;// not found
}
/**
* @remove the first occurrence of a given value, return true if successful
*/
public boolean removeFirstOccurrence(AnyType value) {
int index = indexOf(value);
if (index != -1) {
remove(index);
return true;
}
return false;
}
/**
* @remove the last occurrence of a given value, return true if successful
*/
public boolean removeLastOccurence(AnyType value) {
int index = lastIndexOf(value);
if (index != -1) {
remove(index);
return true;
}
return false;
}
/**
* @return the elements as an object array
*/
public Object[] toArray() {
Object array[] = new Object[theSize];
for (int i = 0; i < theSize; i++) {
array[i] = get(i);
}
return array;
}
public Iterator<AnyType> iterator() {
return new LinkedListIterator();
}
private class LinkedListIterator implements Iterator<AnyType> {
private Node<AnyType> cursor;
private int expectedModCount;
private boolean okToRemove;
LinkedListIterator() {
cursor = header.getNext();
expectedModCount = modCount;
okToRemove = false;
}
public boolean hasNext() {
return (cursor != trailer);
}
public AnyType next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!hasNext())
throw new NoSuchElementException();
AnyType nextValue = cursor.getData();
cursor = cursor.getNext();
okToRemove = true;
return nextValue;
}
public void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!okToRemove)
throw new IllegalStateException();
DoublyLinkedList.this.remove(cursor.getPrev());
expectedModCount++;
okToRemove = false;
}
}
}
// Test.java
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
/**
* Testing the new methods of DoublyLinkedList thoroughly
*/
DoublyLinkedList<String> list = new DoublyLinkedList<String>();
list.add("Oliver Queen");
list.add("Barry Allen");
list.add("Harrison Wells");
list.add("Barry Allen");
list.add("John Diggle");
list.add("Barry Allen");
list.add("Felicity Smoak");
System.out.println("List: " + Arrays.toString(list.toArray()));
DoublyLinkedList<String> clonedList = list.clone();
System.out.println("cloned list: "
+ Arrays.toString(clonedList.toArray()));
int index = list.indexOf("Barry Allen");
System.out.println("first index of Barry Allen: " + index);
System.out.println("removing last occurrence of Barry Allen: ");
list.removeLastOccurence("Barry Allen");
System.out.println("List: " + Arrays.toString(list.toArray()));
System.out.println("Removing first occurrence of Barry Allen");
list.removeFirstOccurrence("Barry Allen");
System.out.println("List: " + Arrays.toString(list.toArray()));
System.out.println("Contains Oliver Queen? "
+ list.contains("Oliver Queen"));
}
}
/*OUTPUT*/
List: [Oliver Queen, Barry Allen, Harrison Wells, Barry Allen, John Diggle, Barry Allen, Felicity Smoak]
cloned list: [Oliver Queen, Barry Allen, Harrison Wells, Barry Allen, John Diggle, Barry Allen, Felicity Smoak]
first index of Barry Allen: 1
removing last occurrence of Barry Allen:
List: [Oliver Queen, Barry Allen, Harrison Wells, Barry Allen, John Diggle, Felicity Smoak]
Contains Oliver Queen? true
Removing first occurrence of Barry Allen
List: [Oliver Queen, Harrison Wells, Barry Allen, John Diggle, Felicity Smoak]