Heres what I have so far: import java.util.Iterator; public class DoublyLinkedLi
ID: 3836660 • Letter: H
Question
Heres what I have so far:
import java.util.Iterator;
public class DoublyLinkedList<T> implements Iterable<T> {
private static class Node<T> {
public T data; // Data within each node
// Previous has a smaller index (closer to start)
// Next has a larger index (closer to end)
public Node<T> prev, next;
}
/**
* The conductor is capable of walking down the "train" of nodes. This
* allows it to follow Java's "iterator" interface.
*
* @param <T>
*/
private static class Conductor<T> implements Iterator<T> {
private Node<T> current;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public T next() {
// Retrieve passenger from current car
T s = current.data;
// Conductor advances to next car
current = current.next;
return s;
}
public Conductor(Node<T> n) {
current = n;
}
}
// First and last nodes of the list.
private Node<T> start, end;
/**
* Create an empty list.
*/
public DoublyLinkedList() {
start = end = null;
}
/**
* Add an element to the end.
*
* @param s
* Data for that element
*/
public void add(T s) {
if (start == null) {
assert end == null;
start = end = new Node<T>();
start.data = s;
// end == start so it doesn't need to be changed
// start.next and start.prev are both null
} else {
// Add to the end
// First, attaching a new boxcar to the end
end.next = new Node<T>();
// Next, building a doorway from the new last to the old last
end.next.prev = end;
// Then, setting up the data member of the new last boxcar
end.next.data = s;
// Finally, new last boxcar is the last boxcar!
end = end.next;
}
}
/**
* Access element at index i (0 based). start has index 0. Runs in O(i) time
* (fast to access near the start, slow near the end)
*
* @param i
* @return data in element at index i or null if i is not a valid index
*/
public T get(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.data;
} catch (NullPointerException e) {
return null; // Not a valid index
}
}
/**
* Remove an element from the list. Repairs the list so that it's connected
* but without that element. Runs in O(i) time.
*
* @param i
* @return data in removed element or null if i is not a valid index
*/
public T remove(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++) {
n = n.next;
}
// NOTE: n could be null, but then we would
// get caught by our null pointer catch clause
// Let's say we have a list x-A-B-C-x
// where next is to the right of each node
// and we want to remove B (variable n)
// The new list would be x-A-C-x
// First we will connect A to C.
if (n.prev != null) {
// If there is such an A
// Change its next variable to C
n.prev.next = n.next;
} else {
// If there is no such A,
// we must be the start of the list
assert n == start;
start = n.next;
}
// Then we will connect C to A
if (n.next != null) {
// If there is such a C
// Change its prev variable to A
n.next.prev = n.prev;
} else {
// If there is no such C,
// we must be the end of the list
assert n == end;
end = n.prev;
}
return n.data;
} catch (NullPointerException e) {
return null; // Not a valid index
}
}
@Override
public Iterator<T> iterator() {
return new Conductor<T>(start);
}
}
1. Size method (30 points) Implement a method public int size() that returns the number of elements of the list in constant time. You will need to add a member field to DoublyLinkedList to support it. The member field will have to be maintained by the other methods as operations are performed to add or remove elements from the list.
2. get method speedup (20 points) Improve the speed of public T get(int i) by having it work backward from the end of the array if you attempt to get a member which is closer to the end than the start. This improvement will be tested through timing tests on large lists.
3. reverse method (25 points) Implement a method public void reverse() that reverses the list. The list A-B-C-D would become D-C-B-A. The old start (A in the example) should be the new end and the old end should be the start. The next element after the start should be what was the previous element before the end, and so forth. The method should work for a list of any length, including the empty list. This method should not need to call “new”.
4. add with index method (25 points) Implement a method public boolean add(int i, T s) that adds an element with an element of type T at index i. (Note that this uses Java’s overload facility since we already have an add method with just a String argument.) Return false if index i does not already exist in the list, otherwise add the element and return true. (Note that this doesn’t let you add a new element to the very end but the existing add method accomplishes this.) The elements before index i should be unchanged. The elements already at index i and after should all be in the same order but at one index value greater than they were before the call to add.
Please work with the coding I provided! Please be serious, Thanks so much in advance! Will rate if excellent!
Explanation / Answer
the following is the code for DoubleLinked List with your requirements :
1.size method
2.get method speed up
3.reverse method
4.add with index method
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
*
* @author sample
*/
public class DoublyLinkedList<E> implements Iterable<E>{
private int N; // number of nodes
private Node head; //sentinel before the first node
private Node tail; //sentinel aftet the last node;
DoublyLinkedList(){
head = new Node();
tail = new Node();
head.next = tail;
tail.previous = head;
}
@Override
public ListIterator<E> iterator() {
return new DoublyListIterator();
}
private class Node{
private E data;
private Node previous;
private Node next;
Node(E item){
data = item;
next = null;
previous = null;
}
Node(){
data = null;
next = null;
previous = null;
}
}
public int size(){return N;}
public boolean isEmpty(){ return N==0;}
public void insert(E item){
Node last = tail.previous;
Node t = new Node(item);
t.next = tail;
t.previous = last;
tail.previous = t;
last.next = t;
N++;
}
public String toString(){
StringBuilder s = new StringBuilder();
Node current = head.next;
while(current != tail){
s.append(current.data+",");
current = current.next;
}
return s.toString();
}
private class DoublyListIterator implements ListIterator<E>{
private int index = 0;
private Node current;
private Node lastAccessed;
DoublyListIterator(){
current = head.next;
lastAccessed = null;
index = 0;
}
@Override
public boolean hasNext() {
return index < N;
}
@Override
public E next() {
if(!hasNext()){
throw new NoSuchElementException();
}
lastAccessed = current;
E item = current.data;
current = current.next;
index++;
return item;
}
@Override
public boolean hasPrevious() {
return index > 0;
}
@Override
public E previous() {
if(!hasPrevious()){
throw new NoSuchElementException();
}
current = current.previous;
lastAccessed = current;
index--;
return current.data;
}
@Override
public int nextIndex() {
return index;
}
@Override
public int previousIndex() {
return index - 1;
}
@Override
public void remove() {
Node a = lastAccessed.previous;
Node b = lastAccessed.next;
a.next = b;
b.previous = a;
N--;
index--;
/*if(current == lastAccessed){
current = b;
}else{
index--;
}*/
lastAccessed = null;
}
@Override
public void set(E e) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public void add(E e) {
Node b = new Node(e);
Node a = current.previous;
Node c = current;
a.next = b;
b.next = c;
c.previous = b;
b.previous = a;
index++;
N++;
lastAccessed = null;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
DoublyLinkedList<Integer> dl = new DoublyLinkedList<>();
ListIterator<Integer> li;
for(int i = 2; i <= 6; i++){
dl.insert(i);
}
li = dl.iterator();
for(int i = 10; i <= 15; i++){
li.add(i);
}
//print using toString()
System.out.println(dl);
System.out.println(" ");
//print using foreach
for(Integer i: dl){
System.out.print(i+",");
}
System.out.println(" ");
//print using iterator
li = dl.iterator();
while(li.hasNext()){
int t = li.next();
System.out.print(t+",");
}
//print using iterator in reverse order
System.out.println(" ");
while(li.hasPrevious()){
int t = li.previous();
//if(t == 3)
System.out.print(t+",");
//if(t % 2 ==0) li.remove();
}
System.out.println(" ");
}
}