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. The method should still return null if i is not a valid index.
Code
import java.util.Iterator;
public class DLList<T> implements
Iterable<T> {
private static class Node<T> {
public Node<T> prev,
next;
public T data;
public
Node(Node<T> prev, T data, Node<T> next) {
this.prev =
prev;
this.next =
next;
this.data =
data;
}
}
private int numNodes;
private Node<T> head, tail;
private static class Conductor<T>
implements Iterator<T> {
public Node<T>
car;
public
Conductor(DLList<T> list) {
car =
list.head;
}
public boolean hasNext()
{
return car !=
null;
}
public T next() {
T data =
car.data;
car =
car.next;
return
data;
}
public void remove()
{
}
}
public DLList() {
head = tail = null;
}
public void add(T data) {
if (tail == null) {
head = new
Node<T>(null, data, null);
tail =
head;
} else {
tail.next = new
Node<T>(tail, data, null);
tail =
tail.next;
}
numNodes++;
}
public int size() {
return numNodes;
}
public T get(int i) {
if (i < 0)
throw new
IndexOutOfBoundsException();
Node<T> current = head;
for (int j = 0; current != null
&& j < i; j++) {
current =
current.next;
}
if (current == null)
throw new
IndexOutOfBoundsException();
return current.data;
}
public T remove(int i) {
if (i < 0)
throw new
IndexOutOfBoundsException();
Node<T> current = head;
for (int j = 0; current != null
&& j < i; j++) {
current =
current.next;
}
if (current == null)
throw new
IndexOutOfBoundsException();
if (current.prev != null)
current.prev.next = current.next;
else
head =
head.next;
if (current.next != null)
current.next.prev = current.prev;
else
tail =
tail.prev;
numNodes--;
return current.data;
}
public Iterator<T> iterator() {
return new
Conductor<T>(this);
}
private static class
BackwardConductor<T> implements Iterator<T> {
public Node<T>
car;
public
BackwardConductor(DLList<T> list) {
car =
list.tail;
}
public boolean hasNext()
{
return car !=
null;
}
public T next() {
T data =
car.data;
car =
car.prev;
return
data;
}
public void remove()
{
}
}
public Iterator<T>
descendingIterator() {
return new
BackwardConductor<T>(this);
}
public void reverse() {
Node<T> temp = head,
temp2;
if (temp != null) {
head =
tail;
tail =
temp;
temp =
head;
while (temp !=
tail) {
temp2 = temp.next;
temp.next = temp.prev;
temp.prev = temp2;
temp = temp.next;
}
temp2 =
temp.next;
temp.next =
temp.prev;
temp.prev =
temp2;
}
}
public boolean add(int i, T s) {
if (i < 0 || i >= size())
{
return
false;
}
Node temp = head;
for (int index = 0; index < i;
index++) {
temp =
temp.next;
}
Node newNode = new
Node<T>(temp.prev, s, temp);
if (temp == head) {
head.prev =
newNode;
head =
newNode;
numNodes++;
return
true;
}
temp.prev.next = newNode;
temp.prev = newNode;
numNodes++;
return true;
}
}
public T get(int i)
{
int n = size();//getting size of the list
if(0<=i && i<n)//if valid index
{
int s=i+1;
int e = n-s;
if(s<e)//then it is closer to
starting
{
Node<T>
temp = head;
s=s-1;
while(temp!=null
&& 0<s)
{
temp=temp.next;
s--;
}
return
temp.data;//return element at index i
}
else//then it is closer to
ending
{
Node<T>
temp =tail;
s=e;
while(temp!=null
&& 0<s)
{
temp=temp.prev;
s--;
}
return
temp.data;//return element at index i
}
}
return null;//if not valid index
}
Improve the speed of public T get(int i) by having it work backward from the end...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...
Hi! Can someone can convert this java code to c++. ASAP thanks I will thumbs up Here's the code: package lists; import bookdata.*; public class DoublyLinkedList { int size; //Variable que define el tamano de la lista. Node head, tail; //Nodos que definen el Head y Tail en la lista. //Constructor public DoublyLinkedList(){ this.head = null; this.tail = null; this.size = 0; } //Insert a new book in alphabetic order. public void insert(Book nb){ //Creamos uno nuevo nodo con el...
Java Programming: The following is my code: public class KWSingleLinkedList<E> { public void setSize(int size) { this.size = size; } /** Reference to list head. */ private Node<E> head = null; /** The number of items in the list */ private int size = 0; /** Add an item to the front of the list. @param item The item to be added */ public void addFirst(E...
Add the following method to xxxxxp3: // deletes x from sorted list k if exist, k = 0, 1, 2 private void delete(x, k) // returns position of x in sorted list k if exist otherwise, -1. k = 0, 1, 2 private int search(x, k) import java.util.Scanner; class xxxxxp3{ private node[] head = new node[3]; private class node{ int num; node link; node(int x){ num=x; link = null; } } public void prtlst(int k){ System.out.printf("\nContents of List-%d:",k); for(node cur...
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...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Any suggestions? public class LinkedList<T> { Node<T> itsFirstNode; Node<T> itsLastNode; private int size; public LinkedList() { itsFirstNode = null; itsLastNode = null; size = 0; } public Iterator<T> getIterator() { return new Iterator(this); } // THIS WILL NEED...
Please help with the codes for the implementation of java.util.List, specifically for the 3 below overridden methods @Override public int lastIndexOf(Object arg0) { required code } @Override public ListIterator<R> listIterator() { required code } @Override public ListIterator<R> listIterator(int arg0) { required code } PLEASE NOTE: Below are some of other overridden methods that are already implemented, they are meant to be examples of what the answers to the above questions for the 3 methods should...
could somone please help me to complete this ! public class MyLinkedList<AnyType> { private Node<AnyType> head, tail; private int size; public MyLinkedList() { this.head = null; this.tail = null; this.size = 0; } //1.Insert a node at the end of the list public void insert(AnyType data) { Node<AnyType> newNode = new Node(); newNode.data = data; if (head == null) { head = newNode; tail = newNode; head.next = null; tail.next = null; } else { tail.next = newNode; tail =...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function import algs13.Bag; import java.util.HashSet; // See instructions below public class MyDigraph { static class Node { private String key; private Bag<Node> adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag<Node> adj () { return adj;...
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...