A doubly-linked list is one in which each Node has pointers to both the next and
ID: 3736212 • Letter: A
Question
A doubly-linked list is one in which each Node has pointers to both the next and previous node, enabling traversal of the data structure in either direction. Implement the two remove methods for this class:
boolean remove (T item);
T remove (int index);
An Iterator enables the user to traverse the data structure and can be used with both arrays and linked structures. Add the following methods to DoublyLinkedList and ArrayLIstWithIterator:
hasPrevious();
previous();
previousIndex();
Then run ListsWithIterator.java. Your output should look like this:
here's our list
[bag, set, queue, stack]
removing bag
[set, queue, stack]
removing stack
[set, queue]
removing queue
[set]
removing set
[ ]
trying to remove set again
[ ]
adding items back in
[bag, set, queue, stack]
removing item at first index bag
[set, queue, stack]
removing item at last index stack
[set, queue]
removing item at index 1 queue
[set]
removing item at index 0 set
[ ]
printing items and indices in reverse order
3 stack
2 queue
1 set
0 bag
trying to remove item from empty list
off end of list
Next write a program Backwards.java that reads in the words from message.txt, stores them in a list, and then traverses the list in reverse order, printing out every other word.
Code
Explanation / Answer
here is your modified code :---------------->>>>>>>>>>>
import java.util.ListIterator;
import java.util.NoSuchElementException;
/*
* DoublyLinkedList
*
* doubly-linked implementation of a list
*
* also has private inner class for ListIterator
*/
public class DoublyLinkedList<T> implements List<T>
{
private class Node
{
private T data;
private Node next;
private Node prev;
public Node(T item)
{
data = item;
next = null;
prev = null;
}
}
private Node head;
private Node tail;
private int size;
public DoublyLinkedList()
{
head = null;
tail = null;
size = 0;
}
public void add (T item)
{
checkForNull(item);
Node newest = new Node (item);
if (size == 0)
{
head = newest;
}
else
{
tail.next = newest;
newest.prev = tail;
}
tail = newest;
size++;
}
public boolean remove (T item)
{
// to be implemented
if(size == 0){
return false;
}
Node curr = head;
while(curr != null){
if(item.equals(curr.data)){
curr.next = curr.next;
curr.next.prev = curr.prev;
return true;
}
curr = curr.next;
}
return false;
}
public boolean contains (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return true;
}
current = current.next;
}
return false;
}
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node newest = new Node (item);
if (index == 0)
{
newest.next = head;
head = newest;
}
else
{
Node current = head;
for (int i = 0; i < index-1; i++)
{
current = current.next;
}
// righthand neighbor
newest.next = current.next;
newest.next.prev = newest;
// lefthand neighbor
current.next = newest;
current.next.prev = current;
}
size++;
}
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node current = head;
for (int i = 0; i < index; i++)
{
current = current.next;
}
T removed = current.data;
current.data = item;
return removed;
}
public T remove (int index)
{
// to be implemented
if(size == 0){
return (T)null;
}
if(index < 0 || index >= size){
return (T)null;
}
Node curr = head;
while(curr != null){
if(item.equals(curr.data)){
curr.next = curr.next;
curr.next.prev = curr.prev;
return curr.data;
}
curr = curr.next;
}
return (T)null;
}
public T get (int index)
{
checkIndex(index);
Node current = head;
for (int i = 0; i < index; i++)
{
current = current.next;
}
return current.data;
}
public int indexOf (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return i;
}
current = current.next;
}
return -1;
}
public int lastIndexOf (T item)
{
Node current = tail;
for (int i = size-1; i >= 0; i--)
{
if (current.data.equals(item))
{
return i;
}
current = current.prev;
}
return -1;
}
public int size()
{
return size;
}
public String toString()
{
String s = "[";
Node current = head;
while (current != null)
{
s+= current.data;
if (current.next != null) s+= ", ";
current = current.next;
}
return s + "]";
}
// creates iterator
public ListIterator<T> listIterator()
{
return new DoublyLinkedListIterator();
}
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException ("null not a possible value!");
}
}
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index out of range!");
}
}
/* iterator class */
private class DoublyLinkedListIterator implements ListIterator<T>
{
// instance variables
private Node forward;
private Node back;
private int count;
// constructor
public DoublyLinkedListIterator()
{
forward = head;
back = tail;
count = 0;
}
// methods
public boolean hasNext()
{
return forward!= null;
}
public T next()
{
if (hasNext())
{
T item = forward.data;
forward = forward.next;
count++;
return item;
}
else
{
throw new NoSuchElementException ("Off end of list");
}
}
public int nextIndex( )
{
return count;
}
public boolean hasPrevious()
{
// to be implemented
return forward.prev.prev != null;
}
public T previous()
{
// to be implemented
if (hasPrevious())
{
T item = forward.prev.prev.data;
forward = forward.prev;
count--;
return item;
}
else
{
throw new NoSuchElementException ("Off end of list");
}
}
public int previousIndex( )
{
// to be implemented
return count-2;
}
// unimplemented methods
public void add (T item)
{
throw new UnsupportedOperationException();
}
public void set (T item)
{
throw new UnsupportedOperationException();
}
public void remove ( )
{
throw new UnsupportedOperationException();
}
}
}
------------------------------------------------------------------------
import java.util.ListIterator;
import java.util.NoSuchElementException;
/*
* ArrayList
*
* array-based implementation of a list
*
* also has private inner class for ListIterator
*/
public class ArrayListWithIterator<T> implements List<T>
{
public static final int DEFAULT_CAPACITY = 10;
private T [] collection;
private int size;
public ArrayListWithIterator()
{
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public ArrayListWithIterator(int capacity)
{
collection = (T[]) new Object[capacity];
size = 0;
}
public void add (T item)
{
checkForNull(item);
ensureSpace();
collection[size] = item;
size++;
}
public boolean remove (T item)
{
for(int i = 0;i<size;i++){
if(collection[i].equals(item)){
for(int j = i;j<size-1;j++){
collection[j] = collection[j+1];
}
size--;
return false;
}
}
}
public boolean contains (T item)
{
for (int i = 0; i < size; i++)
{
if (collection[i].equals(item))
{
return true;
}
}
return false;
}
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
ensureSpace();
shiftRight(index);
collection[index] = item;
size++;
}
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
T removed = collection[index];
collection[index] = item;
return removed;
}
public T remove (int index)
{
if(index < 0 || index >= size){
return (T)null;
}
T item = collection[index];
for(int i = index;i<size-1;i++){
collection[i] = collection[i+1];
}
size--;
return item;
}
public T get (int index)
{
if (size == 0)
{
return null;
}
checkIndex(index);
return collection[index];
}
public int indexOf (T item)
{
for (int i = 0; i < size; i++)
{
if (item.equals(collection[i]))
{
return i;
}
}
return -1;
}
public int lastIndexOf (T item)
{
for (int i = size-1; i >= 0; i--)
{
if (item.equals(collection[i]))
{
return i;
}
}
return -1;
}
public int size()
{
return size;
}
public String toString()
{
if (size == 0)
{
return "[]";
}
String s = "[";
for (int i = 0; i < size; i++)
{
s+= collection[i];
if (i!= size-1)
{
s+= ", ";
}
}
return s + "]";
}
// creates iterator
public ListIterator<T> listIterator()
{
return new ArrayListIterator();
}
private void ensureSpace()
{
if (size == collection.length)
{
@SuppressWarnings("unchecked")
T [] larger = (T[]) new Object[size*2];
for (int i = 0; i < size; i++)
{
larger[i] = collection[i];
}
collection = larger;
}
}
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index outside of list!");
}
}
private void shiftRight (int index)
{
for (int i = size; i > index; i--)
{
collection[i] = collection[i-1];
}
}
private void shiftLeft (int index)
{
for (int i = index; i < size-1; i++)
{
collection[i] = collection[i+1];
}
}
/* iterator class */
private class ArrayListIterator implements ListIterator<T>
{
// instance variable
private int count;
// constructor
public ArrayListIterator()
{
count = 0;
}
// methods
public boolean hasNext()
{
return count < size;
}
public T next()
{
if (hasNext())
{
return collection[count++];
}
else
{
throw new NoSuchElementException("off end of list");
}
}
public int nextIndex( )
{
return count;
}
public boolean hasPrevious()
{
// to be implemented
return count-2 >= 0;
}
public T previous()
{
// to be implemented
if (hasPrevious())
{
return collection[count-2];
count--;
}
else
{
throw new NoSuchElementException("off end of list");
}
}
public int previousIndex( )
{
// to be implemented
return count-2;
}
// unimplemented methods
public void add (T item)
{
throw new UnsupportedOperationException();
}
public void set (T item)
{
throw new UnsupportedOperationException();
}
public void remove ( )
{
throw new UnsupportedOperationException();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.