Using a doubly linked list as the underlying data structure, implement a list ADT that implements...
Using a doubly linked list as the underlying data structure, implement a list ADT that implements the ListInterface.java found in the ProgProjTwo Eclipse project starting point for this assignment.
In addition to the forward iterator defined by resetIterator( ) and getNextItem( ) in ListInterface.java, implement a backwards iterator by providing resetBackIterator( ) and getPreviousItem( ) methods.
As noted in the syllabus addendum, you are encouraged to develop a find( ) helper method that can support various list ADT operations.
A DLLNode class for your use can also be found in ProgProjTwo. You may use a list node object of your own design, but the implementing data structure for this assignment must be a doubly linked list class that you develop.
Develop a test driver for the list implementation that exercises each of the ADT operations and the backwards iterator. The test driver must be consistent with your test plan.
In addition to submitting all of your source code in a single Eclipse project, and overall description of the project, a test plan and a test report, as described in the Programming Projects General requirements, are required.
Included code below
package dllNode;
public class DLLNode<E> {
private E info;
private DLLNode<E> next;
private DLLNode<E> prev;
public DLLNode(E info) {
this.info = info;
next = null;
prev = null;
}
public void setInfo(E info) {
this.info = info;
}
public E getInfo() {
return info;
}
public void setNext(DLLNode<E> reference) {
this.next = reference;
}
public DLLNode<E> getNext() {
return next;
}
public void setPrev(DLLNode<E> reference) {
this.prev = reference;
}
public DLLNode<E> getPrev() {
return prev;
}
}
__________________________________________________________________________________________________
package listInterface;
public interface ListInterface<E> {
int size(); // return the number of elements on this list
boolean isEmpty();
void add(E element);
boolean remove (E element);
// remove an element e from this list such that e.equals(element) and return true;
// if no such element exists, return false
boolean contains (E element);
// return true if this list contains an element e such that e.equals(element);
// otherwise, return false
E get(E element);
// return an element e from this list such that e.equals(element);
// if no such element exists, return null
String toString();
// returns an appropriately formatted string that represents this list.
void resetIterator();
// set the current position for the getNext() iterator to the first element on the list
E getNextItem();
// Preconditions: The list is not empty
// The resetIterator() method has been invoked
// The list has not been modified since the most recent resetIterator() call
//
// return the element at the current position on this list;
// update the current pointer to point to the next element on the list
// note: if the element returned is the last item on the list,
// set the value of the current position to the first element on the list
}
__________________________________________________________________________________________________
package project2;
import listInterface.ListInterface;
import dllNode.DLLNode;
public class DoublyLinkedList<E> implements ListInterface<E> {
protected DLLNode<E> head; // first node on the list
protected DLLNode<E> tail; // last node on the list
// other instance variables are needed
public DoublyLinkedList() {
head = null;
tail = null;
// you may want to have more stuff here
// depending upon your implementation
}
@Override
public void add(E element) {
}
// the find makes life easier, but is not strictly required
protected void find(E target) {
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return true;
}
@Override
public boolean contains (E element) {
return true;
}
@Override
public boolean remove (E element) {
return true;
}
@Override
public E get(E element) {
return null;
}
@Override
public String toString()
// Returns a nicely formatted string that represents this list.
{
return null;
}
@Override
public void resetIterator() {
}
@Override
public E getNextItem() {
return null;
}
public void resetBackIterator() {
}
public E getPreviousItem() {
return null;
}
}
Homework Answers
package dllNode;
//DLLNode.java
public class DLLNode<E> {
private E info;
private DLLNode<E> next;
private DLLNode<E> prev;
public DLLNode(E info) {
this.info = info;
next = null;
prev = null;
}
public void setInfo(E info) {
this.info = info;
}
public E getInfo() {
return info;
}
public void setNext(DLLNode<E> reference) {
this.next = reference;
}
public DLLNode<E> getNext() {
return next;
}
public void setPrev(DLLNode<E> reference) {
this.prev = reference;
}
public DLLNode<E> getPrev() {
return prev;
}
}
//end of DLLNode.java
package listInterface;
// ListInteface.java
public interface ListInterface<E> {
int size(); // return the number of elements on this list
boolean isEmpty();
void add(E element);
boolean remove (E element);
// remove an element e from this list such that e.equals(element) and return true;
// if no such element exists, return false
boolean contains (E element);
// return true if this list contains an element e such that e.equals(element);
// otherwise, return false
E get(E element);
// return an element e from this list such that e.equals(element);
// if no such element exists, return null
String toString();
// returns an appropriately formatted string that represents this list.
void resetIterator();
// set the current position for the getNext() iterator to the first element on the list
E getNextItem();
// Preconditions: The list is not empty
// The resetIterator() method has been invoked
// The list has not been modified since the most recent resetIterator() call
//
// return the element at the current position on this list;
// update the current pointer to point to the next element on the list
// note: if the element returned is the last item on the list,
// set the value of the current position to the first element on the list
}
//end of ListInterface.java
package project2;
import listInterface.ListInterface;
import dllNode.DLLNode
// DoublyLinkedList.java
public class DoublyLinkedList <E> implements ListInterface<E> {
protected DLLNode<E> head; // first node on the list
protected DLLNode<E> tail; // last node on the list
// other instance variables are needed
protected DLLNode<E> forwardIterator; // first node on the list
protected DLLNode<E> backIterator; // first node on the list
public DoublyLinkedList () {
head = null;
tail = null;
forwardIterator = head;
backIterator = tail;
// you may want to have more stuff here
// depending upon your implementation
}
@Override
public int size() {
int count =0;
DLLNode<E> curr = head;
while(curr != null)
{
count++;
curr = curr.getNext();
}
return count;
}
@Override
public boolean isEmpty() {
return(head == null);
}
// add the node at the end of the list
@Override
public void add(E element) {
if(head == null)
{
head = new DLLNode<E>(element);
tail =head;
resetIterator();
resetBackIterator();
return;
}
DLLNode<E> node = new DLLNode<E>(element);
tail.setNext(node);
node.setPrev(tail);
tail = node;
resetIterator();
resetBackIterator();
}
@Override
public boolean remove(E element) {
if(!contains(element))
return false;
else {
if(head.getInfo().equals(element))
{
if(head.getNext() == null)
head = tail = null;
else {
head = head.getNext();
head.setPrev(null);
}
}else {
DLLNode<E> curr = head;
while(curr!= null)
{
if(curr.getInfo().equals(element))
{
curr.getPrev().setNext(curr.getNext());
if(curr.getNext()!= null)
{
curr.getNext().setPrev(curr.getPrev());
}else
{
tail = curr.getPrev();
}
}
curr = curr.getNext();
}
}
resetIterator();
resetBackIterator();
return true;
}
}
@Override
public boolean contains(E element) {
DLLNode<E> curr = head;
while(curr != null)
{
if(curr.getInfo().equals(element))
return true;
curr =curr.getNext();
}
return false;
}
@Override
public E get(E element) {
if(!contains(element))
return null;
DLLNode<E> curr = head;
while(curr != null)
{
if(curr.getInfo().equals(element))
return curr.getInfo();
curr =curr.getNext();
}
return null;
}
@Override
public void resetIterator() {
forwardIterator = head;
}
@Override
public E getNextItem() {
if(forwardIterator == null)
return null;
E element = forwardIterator.getInfo();
if(forwardIterator.getNext() == null)
resetIterator();
else
forwardIterator = forwardIterator.getNext();
return element;
}
public void resetBackIterator() {
backIterator = tail;
}
public E getPreviousItem() {
if(backIterator == null)
return null;
E element = backIterator.getInfo();
if(backIterator.getPrev() == null)
resetBackIterator();
else
backIterator = backIterator.getPrev();
return element;
}
@Override
public String toString()
{
if(head == null)
return null;
DLLNode<E> curr = head;
String list = "[";
while(curr.getNext() != null)
{
list = list + curr.getInfo()+",";
curr = curr.getNext();
}
list = list + curr.getInfo()+"]";
return list;
}
}
//end of DoublyLinkedList.java
package project2;
// TestDoublyLL.java : Driver program to test DoublyLinkedList class
public class TestDoublyLL {
public static void main(String[] args) {
DoublyLinkedList <Integer> list = new DoublyLinkedList <Integer>();
for(int i=0;i<10;i++)
list.add(i);
System.out.println("Linked list :\n Size : "+list.size());
System.out.println(list);
System.out.println("Remove 11 from list : "+list.remove(11));
System.out.println("Remove 8 from list : "+list.remove(8));
System.out.println(" List contains 5: "+list.contains(5));
System.out.println("Updated Linked :\n Size : "+list.size());
System.out.println(list);
System.out.println("Get element 2 : "+list.get(2));
list.getNextItem(); //1st element
list.getNextItem();//2nd element
System.out.println("Get 3rd element from front: "+list.getNextItem()); // 3rd element
list.resetIterator(); // reset the iterator
list.getPreviousItem();// last element
list.getPreviousItem(); // 2nd last element
System.out.println("Get 3rd element from back: "+list.getPreviousItem()); // 3rd last element
list.resetBackIterator(); // reset the back iterator
}
}
//end of program
Output:
![Linked list Size 10 [0,1,2,3,4,5,6,7,8,9] Remove 11 from list: false Remove 8 from list: true List contains 5: true Updated L](http://img.homeworklib.com/questions/5d41b2b0-1e0c-11eb-a2df-af1b7c5cab98.png?x-oss-process=image/resize,w_560)
Add Answer to:
Using a doubly linked list as the underlying data structure,
implement a list ADT that implements...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes, do not create any new nodes. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- package lists; import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedPositionalList implements PositionalList { //---------------- nested Node class ---------------- /** * Node of a doubly linked list, which stores a reference to its * element and to both the previous and next...
Given a singly-linked list interface and linked list node class, implement the singly-linked list which has...
Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java: 1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T...
Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for ...
Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for an implementation of a Singly Linked List. There are 3 files: Driver.java -- testing the List functions in a main() method. LinkNode.java -- Class definition for a Node, which is the underlying entity that stores the items for the linked list. SinglyLinkedList.java -- Class definition for the Singly Linked List. All the heavy lifting happens here. Task 1 - Review & Testing: Create...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has you display a pessimistic poem from a list of phrases. Next, this program has you reverse the phrases to find another more optimistic poem. Use the following algorithm. 1. You are given a list of phrases each ending with a pound sign: ‘#’. 2. Create a single String object from this list. 3. Then, split the String of phrases into an array of phrases...
solve this Q in java languege Write a method that return DoublyLinkedList as reversed string For...
solve this Q in java languege Write a method that return DoublyLinkedList as reversed string For example: If the elements of a list is 1, 2, 3, 4, 5, 6 the reverse string should be 6, 5, 4, 3, 2, 1 implement reverse method you have two steps: 1- you should start traversing from the last element of DoublyLinkedList (the previous of the trailer) 2- you should add the element inside each node to string don't forget the space in...
JAVA - Circular Doubly Linked List Does anybody could help me with this method below(previous)? public...
JAVA - Circular Doubly Linked
List
Does anybody could help me with this method below(previous)?
public E previous() {
// Returns the previous Element
return null;
}
Explanation:
We have this class with these two implemented
inferfaces:
The interfaces are:
package edu.ics211.h04;
/**
* Interface for a List211.
*
* @author Cam Moore
* @param the generic type of the Lists.
*/
public interface IList211 {
/**
* Gets the item at the given index.
* @param index the index....
Plz help me with the code. And here are the requirement. Thanks!! You are required to...
Plz help me with the code. And here are the requirement. Thanks!! You are required to design and implement a circular list using provided class and interface. Please filling the blank in CircularList.java. This circular list has a tail node which points to the end of the list and a number indicating how many elements in the list. And fill out the blank of the code below. public class CircularList<T> implements ListInterface<T> { protected CLNode<T> tail; // tail node that...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your...
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards. void addEnd(int x): create this method to add x to the end of the list. void displayInReverse(): create this method to display the list elements from the last item to the first one. Create a main() function to test...
Question from Object-Oriented Data Structures Using Java 4th Edition Chapter 5 Question 30 Add the following...
Question from Object-Oriented Data Structures Using Java 4th Edition Chapter 5 Question 30 Add the following methods to the LinkedCollection class, and create a test driver for each to show that they work correctly. Code each of these methods by accessing the internal variables of the LinkedCollection, not by calling the previously defined methods of the class.String toString() creates and returns a string that correctly represents the current collection. 1. Such a method could prove useful for testing and debugging...
JAVA - Circular Doubly Linked
List
Does anybody could help me with this method below(previous)?
public E previous() {
// Returns the previous Element
return null;
}
Explanation:
We have this class with these two implemented
inferfaces:
The interfaces are:
package edu.ics211.h04;
/**
* Interface for a List211.
*
* @author Cam Moore
* @param the generic type of the Lists.
*/
public interface IList211 {
/**
* Gets the item at the given index.
* @param index the index....
Most questions answered within 3 hours.
-
If there’s an f value of 1 and a critical value of 3.68 do i
reject...
asked 1 minute ago -
sketch a molecular orbital diagram (MO) for Li2 and
C2. How do you find the bond...
asked 1 minute ago -
Trace amounts of
sulfur (S) in coal are burned in the presence of diatomic oxygen
(O2)...
asked 7 minutes ago -
Diatomic iodine [I2] decomposes at high temperature to form I
atoms according to the reaction: I2(g)⇌2I(g),...
asked 10 minutes ago -
Hello:
Need help with this program. In JavaScript please
// Assume hot dogs come in packages...
asked 16 minutes ago -
A quality control engineer is interested in the mean length of
sheet insulation being cut automatically...
asked 17 minutes ago -
Consider two parallel wires placed a distance of 12.5 cm apart.
The current in the first...
asked 31 minutes ago -
All of the amino acids that are used to synthesize
human proteins (with the exception of...
asked 30 minutes ago -
One of the consequences of collinearity in multiple regression
is inflated standard errors in some
or...
asked 38 minutes ago -
Courington Detailing's cost formula for its materials and
supplies is $2,040 per month plus $9 per...
asked 37 minutes ago -
Observations are taken on sales of a certain mountain bike in 30
sporting goods stores. The...
asked 39 minutes ago -
A 0.25 M aqueous solution of a weak monoprotic acid has a pH of
3.37. Calculate...
asked 39 minutes ago