Modify the following code so that it is an implementation of a doubly-linked lis
ID: 3604200 • Letter: M
Question
Modify the following code so that it is an implementation of a doubly-linked list.
public class LinkedList<T> {
Node<T> itsFirstNode;
Node<T> itsLastNode;
private int size;
public LinkedList() {
itsFirstNode = null;
itsLastNode = null;
size = 0;
}
public Iterator<T> getIterator() {
return new Iterator(this);
}
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element) {
Node<T> node = new Node(element);
if (itsFirstNode == null) {
itsFirstNode = node;
itsLastNode = node;
}
else {
itsLastNode.setNextNode(node);
itsLastNode = node;
}
size++;
}
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element, int index) {
int counter = 0;
Node<T> newNode = new Node(element);
Node<T> current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index - 1 )
break;
current = current.getNextNode();
counter++;
}
newNode.setNextNode(current.getNextNode());
current.setNextNode(newNode);
size++;
}
public T get(int index) {
int counter = 0;
Node<T> current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index)
break;
current = current.getNextNode();
counter++;
}
return current.getData();
}
// TO BE IMPLEMENTED
/*
// returns true if element is in the list, false if not
public boolean contains(T element) {
}
// returns the index of the element if it is in the list, -1 if not found
public int indexOf(T element) {
}
// returns an Iterator at the location of the element if it is in the list
// returns the null reference if the element is not found
public Iterator<T> iteratorAt(T element) {
}
*/
public String toString() {
String returnVal = "";
Node<T> current = itsFirstNode;
if (size != 0 ) {
while (current.getNextNode() != null ) {
returnVal += current.toString();
returnVal += " ";
current = current.getNextNode();
}
returnVal += current.toString();
}
return returnVal;
} // end toString
class Node<T> {
private T data;
private Node<T> itsNext;
private Node<T> itsPrior;
public Node(T data) {
itsNext = null;
itsPrior = null;
this.data = data;
}
public T getData() {
return this.data;
}
public Node<T> getNextNode() {
return itsNext;
}
// TO BE IMPLEMENTED
/*
public Node<T> getPriorNode() {
}
*/
public void setNextNode(Node<T> next) {
itsNext = next;
}
// TO BE IMPLEMENTED
/*
public void setPriorNode(Node<T> prior) {
}
*/
public String toString() {
return data.toString();
}
} // end of Node<T>
}
Explanation / Answer
public class LinkedList<T> {
Node<T> itsFirstNode;
Node<T> itsLastNode;
private int size;
public LinkedList() {
itsFirstNode = null;
itsLastNode = null;
size = 0;
}
/*You need to implement the Iterable interface, which means you need to implement the iterator() method in order to make Node objects iterable */
/*
public Iterator<T> getIterator() {
return new Iterator(this);
}*/
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element) {
Node<T> node = new Node(element);
if (itsFirstNode == null) {
itsFirstNode = node;
itsLastNode = node;
}
else {
itsLastNode.setNextNode(node);
node.setPriorNode(itsLastNode);//prior node set from new node to last node
itsLastNode = node;
}
size++;
}
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element, int index) {
int counter = 0;
Node<T> newNode = new Node(element);
Node<T> current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index - 1 )
break;
current = current.getNextNode();
counter++;
}
newNode.setNextNode(current.getNextNode());
Node<T> temp=current.getNextNode();//temp node is next node of current node
temp.setPriorNode(newNode);
current.setNextNode(newNode);
newNode.setPriorNode(current);
size++;
}
public T get(int index) {
int counter = 0;
Node<T> current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index)
break;
current = current.getNextNode();
counter++;
}
return current.getData();
}
// TO BE IMPLEMENTED
// returns true if element is in the list, false if not
public boolean contains(T element) {
Node<T> head=itsFirstNode;
boolean res=false;
if(itsFirstNode==null) return res;
else{
while(head!=null){
if(head.getData()==element){
res=true;
break;
}
head.setNextNode(head.getNextNode());
}
}
return res;
}
// returns the index of the element if it is in the list, -1 if not found
public int indexOf(T element) {
Node<T> head=itsFirstNode;
int index=0;
if(itsFirstNode==null) return -1;
else{
while(head!=null){
if(head.getData()==element){
break;
}
head.setNextNode(head.getNextNode());
index++;
}
}
return index;
}
// returns an Iterator at the location of the element if it is in the list
// returns the null reference if the element is not found
/* we cannot get java iterator to an user defined object unless implementing iterable interface*/
/* therefore i changed return type to Node<T> and return reference to current node*/
public Node<T> iteratorAt(T element) {
Node<T> head=itsFirstNode;
if(itsFirstNode==null) return null;
else{
while(head!=null){
if(head.getData()==element){
break;
}
head.setNextNode(head.getNextNode());
}
}
return head;
}
public String toString() {
String returnVal = "";
Node<T> current = itsFirstNode;
if (size != 0 ) {
while (current.getNextNode() != null ) {
returnVal += current.toString();
returnVal += " ";
current = current.getNextNode();
}
returnVal += current.toString();
}
return returnVal;
} // end toString
class Node<T> {
private T data;
private Node<T> itsNext;
private Node<T> itsPrior;
public Node(T data) {
itsNext = null;
itsPrior = null;
this.data = data;
}
public T getData() {
return this.data;
}
public Node<T> getNextNode() {
return itsNext;
}
// TO BE IMPLEMENTED
public Node<T> getPriorNode() {
return itsPrior;
}
public void setNextNode(Node<T> next) {
itsNext = next;
}
// TO BE IMPLEMENTED
public void setPriorNode(Node<T> prior) {
itsPrior=prior;
}
public String toString() {
return data.toString();
}
} // end of Node<T>
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.