I need to create a class “DoublyLinkedList” which has a generic type E and subcl
ID: 3880223 • Letter: I
Question
I need to create a class “DoublyLinkedList” which has a generic type E and subclasses the abstract “LabTemplate” class.
In “DoublyLinkedList”, I need to implement every abstract method defined in the “LabTemplate” class.
The class header for “DoublyLinkedList” should be as follows:
public class DoublyLinkedList<E> extends LabTemplate<E>{ }
I don't need to implement the node class.
•When adding an element to the head or tail of a list: create a new node with the given element, set the head or tail instance variable to the new node, set the new nodes next
and previous instance variables to the appropriate values, and increase the size instance variable.
•If a node does not have a next or pervious node (for example, the last node in the linked list does not have a next node), the value of its next or pervious instance variable should be null
•If the linked list is empty, the head and tail instance variables should be null
•If the linked list has a single element, the head and tail instance variables should both be set to the single node. But the nodes next and previous instance variables should both be null.
•When removing a node, we delink the node from the linked list. For example, if we want to remove the head node: we should get the second node in the linked list,
set that node to the head variable, set the value of the new head’s previous instance variable to null, set the value of the hold heads next instance variable to null,
and get the element stored in the old head and return it.
Here is the LabTemplate class
--------------------------------------------------------
public abstract class LabTemplate<E> {
protected Node<E> head;
protected Node<E> tail;
protected int size;
//Getter methods
//Get the size of the linked list
public abstract int getSize();
//Return a boolean indicating if the linked list is empty or not
public abstract boolean isEmpty();
//Return the element in the first node of the linked list
public abstract E getFirst();
//Return the element in the last node of the linked list
public abstract E getLast();
//Get the element at a specific node in the linked list. If the specified node does not exist, throw a new IndexOutOfBoundsException
public abstract E getElementAt(int index) throws IndexOutOfBoundsException;
public Node<E> getHeadNode(){
return head;
}
//Setter methods
//No need to implement this methods but feel free if you want the extra challenge
//public abstract void addElementAt(int index, E anElement);
//public abstract E removeElementAt(int index);
//Add a new node to the start of the linked list. You must update the head instance variable and make sure your new node both has the
//value provided by the method parameter and is properly linked to other nodes. You must also increment the size instance variable by 1
public abstract void addFirst(E anElement);
//Same as add first except we add to the tail of the linked list
public abstract void addLast(E anElement);
//Remove the last element in the LinkedList. Make sure to update the head instance variable, decrement the size instance variable by 1,
//return the element of the removed node, and have the nodes remaining in the linked list linked to the correct locations
public abstract E removeFirst();
//Same as removeFirst except we remove the last element of the linked list
public abstract E removeLast();
}
Here is Node class
------------------------------------------------------------
public class Node<E> {
//Instance Variables
private E element;
private Node<E> next;
private Node<E> previous;
//Parameterized Constructor
public Node(E anElement, Node<E> previousNode, Node<E> nextNode) {
element = anElement;
next = nextNode;
previous = previousNode;
}
//Getters and setters
public E getElement() {
return element;
}
public void setElement(E anElement) {
element = anElement;
}
public Node<E> getNextNode(){
return next;
}
public void setNextNode(Node<E> nextNode) {
next = nextNode;
}
public Node<E> getPreviousNode(){
return previous;
}
public void setPreviousNode(Node<E> nextNode) {
previous = nextNode;
}
public String toString() {
return element.toString();
}
}
Explanation / Answer
public class DoublyLinkedList<E> extends LabTemplate<E>{
@Override
public int getSize() {
// TODO Auto-generated method stub
if(head==null)
return 0;
int count = 0;
Node temp = head;
while (temp != null){
count = count + 1;
temp = temp.getNextNode();
}
return count;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return head==null;
}
@Override
public E getFirst() {
// TODO Auto-generated method stub
if(head==null)
return null;
return (E) head.getElement();
}
@Override
public E getLast() {
// TODO Auto-generated method stub
if(head==null)
return null;
Node temp = head;
while (temp.getNextNode() != null)
temp = temp.getNextNode();
return (E) temp.getElement();
}
@Override
public E getElementAt(int index) throws IndexOutOfBoundsException {
// TODO Auto-generated method stub
if(head==null)
return null;
else if(index < 0 || index >= getSize() )
throw new IndexOutOfBoundsException();
else{
int count = 0;
Node temp = head;
while (count < index && temp != null){
count = count + 1;
temp = temp.getNextNode();
}
return (E) temp.getElement();
}
}
@Override
public void addFirst(Object anElement) {
// TODO Auto-generated method stub
Node newNode = new Node(anElement,null, null);
newNode.setNextNode(head);
if (head != null)
head.setPreviousNode(newNode);
head = newNode;
}
@Override
public void addLast(Object anElement) {
// TODO Auto-generated method stub
Node newNode = new Node(anElement,null, null);
if (head == null) {
newNode.setNextNode(head);
head = newNode;
return;
}
Node temp = head;
while (temp.getNextNode() != null)
temp = temp.getNextNode();
temp.setNextNode(newNode);
newNode.setPreviousNode(temp);
}
@Override
public E removeFirst() {
// TODO Auto-generated method stub
Object o = null;
if (head != null) {
if (head.getNextNode() == null) {
o = head.getElement();
head = null;
} else {
o = head.getElement();
head.getNextNode().setPreviousNode(null);
head = head.getNextNode();
}
}
return (E) o;
}
@Override
public E removeLast() {
// TODO Auto-generated method stub
Object o = null;
if (head == null) {
return null;
}
Node temp = head;
Node prev = null;
while (temp.getNextNode() != null) {
prev = temp;
temp = temp.getNextNode();
}
if (prev == null){
o = head.getElement();
head = null;
}
o = prev.getNextNode().getElement();
prev.setNextNode(null);
return (E) o;
}
}
==============================================================
Thanks, let me know if there is any concern.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.