Using a doubly linked list as the underlying data structure, implement a list AD
ID: 3595987 • Letter: U
Question
Using a doubly linked list as the underlying data structure, implement a list ADT that implements the following interface:
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 reset();
// set the current position for the getNext() iterator to the first element on the list
E getNext();
// Preconditions: The list is not empty
// The reset() method has been invoked
// The list has not been modified since the most recent reset() 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
}
In addition to the forward iterator defined by reset( ) and getNext( ) in interface above, implement a backwards iterator by providing resetBackwards( ) and getPrevious( ) methods. Also develop a find( ) helper method that can support various list ADT operations.
The following node must also be used:
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;
}
Develop a test driver for the list implementation that exercises each of the ADT operations and the backwards iterator.
Explanation / Answer
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 reset();
// set the current position for the getNext() iterator to the first element
// on the list
E getNext();
// Preconditions: The list is not empty
// The reset() method has been invoked
// The list has not been modified since the most recent reset() 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 listInterface;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;
import dllNode.DLLNode;
public class ADT<E> implements ListInterface<E> {
transient int modCount = 0;
transient int size = 0;
/**
* Pointer to first node. Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient DLLNode<E> first;
/**
* Pointer to last node. Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient DLLNode<E> last;
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
if (size() == 0) {
return true;
}
return false;
}
@Override
public void add(E element) {
// TODO Auto-generated method stub
linkLast(element);
}
/**
* Removes the first occurrence of the specified element from this list, if
* it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list contained
* the specified element (or equivalently, if this list changed as a result
* of the call).
*
* @param o
* element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
@Override
public boolean remove(E element) {
if (element == null) {
for (DLLNode<E> x = first; x != null; x = x.getNext()) {
if (x.getInfo() == null) {
unlink(x);
return true;
}
}
} else {
for (DLLNode<E> x = first; x != null; x = x.getNext()) {
if (element.equals(x.getInfo())) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* Returns {@code true} if this list contains the specified element. More
* formally, returns {@code true} if and only if this list contains at least
* one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o
* element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
@Override
public E get(E element) {
// TODO Auto-generated method stub
Iterator<E> iterator = new ListItr();
while (iterator.hasNext()) {
if (iterator.next().equals(element)) {
return element;
}
}
return null;
}
/**
* This point is not clear as these are the methods which should be
* implemented in Iterator class according to behavior.
*/
@Override
public void reset() {
// TODO Auto-generated method stub
}
/**
* This point is not clear as these are the methods which should be
* implemented in Iterator class according to behavior.
*/
@Override
public E getNext() {
// TODO Auto-generated method stub
return null;
}
public Iterator<E> iterator() {
return new ListItr();
}
public Iterator<E> reverseIterator() {
return new DescendingIterator();
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final DLLNode<E> l = last;
final DLLNode<E> newNode = new DLLNode<>(e);
last = newNode;
if (l == null)
first = newNode;
else {
l.setNext(newNode);
newNode.setPrev(l);
}
size++;
modCount++;
}
/**
* Unlinks non-null node x.
*/
E unlink(DLLNode<E> x) {
// assert x != null;
final E element = x.getInfo();
final DLLNode<E> next = x.getNext();
final DLLNode<E> prev = x.getPrev();
if (prev == null) {
first = next;
} else {
prev.setNext(next);
x.setPrev(null);
}
if (next == null) {
last = prev;
} else {
next.setPrev(prev);
x.setNext(null);
}
x.setInfo(null);
size--;
modCount++;
return element;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (DLLNode<E> x = first; x != null; x = x.getNext()) {
if (x.getInfo() == null)
return index;
index++;
}
} else {
for (DLLNode<E> x = first; x != null; x = x.getNext()) {
if (o.equals(x.getInfo()))
return index;
index++;
}
}
return -1;
}
private class ListItr implements ListIterator<E> {
private DLLNode<E> lastReturned;
private DLLNode<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr() {
nextIndex = 0;
next = first;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.getNext();
nextIndex++;
return lastReturned.getInfo();
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = (next == null) ? last : next.getPrev();
next = lastReturned;
nextIndex--;
return lastReturned.getInfo();
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
DLLNode<E> lastNext = lastReturned.getNext();
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.setInfo(e);
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.getInfo());
lastReturned = next;
next = next.getNext();
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr();
public DescendingIterator() {
itr.nextIndex = size();
itr.next = null;
}
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, DLLNode<E> succ) {
final DLLNode<E> pred = succ.getPrev();
final DLLNode<E> newNode = new DLLNode<>(e);
newNode.setNext(succ);
newNode.setPrev(pred);
succ.setPrev(newNode);
if (pred == null)
first = newNode;
else
pred.setNext(newNode);
size++;
modCount++;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
DLLNode<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
DLLNode<E> x = first;
for (int i = 0; i < index; i++)
x = x.getNext();
return x;
} else {
DLLNode<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.getPrev();
return x;
}
}
}
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 driver;
import java.util.Iterator;
import listInterface.ADT;
public class Driver {
public static void main(String[] args) {
ADT<String> adt = new ADT<>();
adt.add("First");
adt.add("Second");
adt.add("Third");
System.out.println("Contains First:-" + adt.contains("First"));
System.out.println("Get element :-" + adt.get("Third"));
System.out.println("Forward Iterator:- ");
Iterator<String> iterator = adt.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("REVERSE Iterator:- ");
Iterator<String> reverseIterator = adt.reverseIterator();
while (reverseIterator.hasNext()) {
System.out.println(reverseIterator.next());
}
}
}
SAMPLE OUTPUT:-
Contains First:-true
Get element :-Third
Forward Iterator:-
First
Second
Third
REVERSE Iterator:-
Third
Second
First
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.