/*********************** * In this file, you need to implement a class called \"
ID: 3745468 • Letter: #
Question
/***********************
* In this file, you need to implement a class called "customDSLL<Item>" abbreviated for custom-DataStructure-Linkedlist,
which needs to be implemented using a Doubly Linkedlist.
* You need to write code at places which say "TO DO".
* Do not change the method definitions, since that would make this file incompatible with the client.java file.
* Also, feel free to add additional classes/methods if required. Hint: You should add an inner class for Iterator interface, like it is done in the slides.
*/
package homework1;
import java.util.Iterator;
public class customDSLL<Item> implements Iterable<Item>{
private Node front;
private Node back;
private class Node{
/*
* TO DO
* Inner class
*/
}
public boolean isEmpty() {
/*
* TO DO
* return true if the DS is empty, else return false
*/
return true;
}
public int size() {
/*
* TO DO
* return the size of the DS, i.e the number of elements in the DS. Can you do it in constant time?
*/
return 0;
}
public void insertFront(Item it) {
/*
* TO DO
* Insert a new element at the front pointer.
*/
}
public void insertBack(Item it) {
/*
* TO DO
* Insert a new element at the back pointer.
*/
}
public Item removeFront() {
/*
* TO DO
* Remove a new element from the front pointer.
*/
return null;
}
public Item removeBack() {
/*
* TO DO
* Remove a new element from the back pointer.
*/
return null;
}
public Iterator<Item> iterator() {
/*
* TO DO
* Implement the iterator method like in the slides to enable usage of "foreach" loop.
*/
return null;
}
}
Explanation / Answer
Given below is the completed code for the question.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you
/***********************
* In this file, you need to implement a class called "customDSLL<Item>" abbreviated for custom-DataStructure-Linkedlist,
which needs to be implemented using a Doubly Linkedlist.
* You need to write code at places which say "TO DO".
* Do not change the method definitions, since that would make this file incompatible with the client.java file.
* Also, feel free to add additional classes/methods if required. Hint: You should add an inner class for Iterator interface, like it is done in the slides.
*/
package homework1;
import java.util.Iterator;
public class customDSLL<Item> implements Iterable<Item>{
private Node front;
private Node back;
private class Node{
private Item data;
private Node previous;
private Node next;
Node(Item data, Node previous, Node next){
this.data = data;
this.next = next;
this.previous = previous;
}
}
public customDSLL(){
front = null;
back = null;
}
public boolean isEmpty() {
/*
* return true if the DS is empty, else return false
*/
return front == null;
}
public int size() {
/*
* return the size of the DS, i.e the number of elements in the DS. Can you do it in constant time?
Ans: In order to do in constant time, a new field size has to be added to the class and update whenever list is modified
*/
int s = 0;
Node current = front;
while(current != null){
s++;
current = current.next;
}
return s;
}
public void insertFront(Item it) {
/*
* Insert a new element at the front pointer.
*/
front = new Node(it, null, front);
if(back == null) //adding first node to list
back = front;
else
front.next.previous = front;
}
public void insertBack(Item it) {
/*
* Insert a new element at the back pointer.
*/
Node n = new Node(it, back, null);
if(isEmpty())
front = back = n;
else{
back.next = n;//link the last node to newnode
back = n;
}
}
public Item removeFront() {
/*
* Remove a new element from the front pointer.
*/
Item value = null;
if(!isEmpty()){
value = front.data;
front = front.next;
if(front == null)
back = null;
else
front.previous = null;
}
return value;
}
public Item removeBack() {
/*
* Remove a new element from the back pointer.
*/
Item value = null;
if(!isEmpty()){
back = back.previous;
if(back == null) //now list is empty
front = null;
else
back.next = null; //no more next node, since removed tail
}
return value;
}
public Iterator<Item> iterator() {
/*
* Implement the iterator method like in the slides to enable usage of "foreach" loop.
*/
return new DLLIterator();
}
class DLLIterator implements Iterator<Item>{
private Node current;
DLLIterator(){
current = front;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item it = current.data;
current = current.next;
return it;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.