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 node in the list. */ private static class Node implements Position { /** The element stored at this node */ private E element; // reference to the element stored at this node /** A reference to the preceding node in the list */ private Node prev; // reference to the previous node in the list /** A reference to the subsequent node in the list */ private Node next; // reference to the subsequent node in the list /** * Creates a node with the given element and next node. * * @param e the element to be stored * @param p reference to a node that should precede the new node * @param n reference to a node that should follow the new node */ public Node(E e, Node p, Node n) { element = e; prev = p; next = n; } // public accessor methods /** * Returns the element stored at the node. * @return the stored element * @throws IllegalStateException if node not currently linked to others */ public E getElement() throws IllegalStateException { if (next == null) // convention for defunct node throw new IllegalStateException("Position no longer valid"); return element; } /** * Returns the node that precedes this one (or null if no such node). * @return the preceding node */ public Node getPrev() { return prev; } /** * Returns the node that follows this one (or null if no such node). * @return the following node */ public Node getNext() { return next; } public void setElement(E e) { element = e; } public void setPrev(Node p) { prev = p; } public void setNext(Node n) { next = n; } } private Node header; // header sentinel private Node trailer; // trailer sentinel private int size = 0; // number of elements in the list public LinkedPositionalList() { header = new Node<>(null, null, null); // create header trailer = new Node<>(null, header, null); // trailer is preceded by header header.setNext(trailer); // header is followed by trailer } private Node validate(Position p) throws IllegalArgumentException { if (!(p instanceof Node)) throw new IllegalArgumentException("Invalid p"); Node node = (Node) p; // safe cast if (node.getNext() == null) // convention for defunct node throw new IllegalArgumentException("p is no longer in the list"); return node; } private Position position(Node node) { if (node == header || node == trailer) return null; // do not expose user to the sentinels return node; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public Position first() { return position(header.getNext()); } @Override public Position last() { return position(trailer.getPrev()); } @Override public Position before(Position p) throws IllegalArgumentException { Node node = validate(p); return position(node.getPrev()); } @Override public Position after(Position p) throws IllegalArgumentException { Node node = validate(p); return position(node.getNext()); } private Position addBetween(E e, Node pred, Node succ) { Node newest = new Node<>(e, pred, succ); // create and link a new node pred.setNext(newest); succ.setPrev(newest); size++; return newest; } @Override public Position addFirst(E e) { return addBetween(e, header, header.getNext()); // just after the header } @Override public Position addLast(E e) { return addBetween(e, trailer.getPrev(), trailer); // just before the trailer } @Override public Position addBefore(Position p, E e) throws IllegalArgumentException { Node node = validate(p); return addBetween(e, node.getPrev(), node); } @Override public Position addAfter(Position p, E e) throws IllegalArgumentException { Node node = validate(p); return addBetween(e, node, node.getNext()); } @Override public E set(Position p, E e) throws IllegalArgumentException { Node node = validate(p); E answer = node.getElement(); node.setElement(e); return answer; } @Override public E remove(Position p) throws IllegalArgumentException { Node node = validate(p); Node predecessor = node.getPrev(); Node successor = node.getNext(); predecessor.setNext(successor); successor.setPrev(predecessor); size--; E answer = node.getElement(); node.setElement(null); // help with garbage collection node.setNext(null); // and convention for defunct node node.setPrev(null); return answer; } private class PositionIterator implements Iterator> { private Position cursor = first(); // position of the next element to report private Position recent = null; // position of last reported element public boolean hasNext() { return (cursor != null); } public Position next() throws NoSuchElementException { if (cursor == null) throw new NoSuchElementException("nothing left"); recent = cursor; // element at this position might later be removed cursor = after(cursor); return recent; } public void remove() throws IllegalStateException { if (recent == null) throw new IllegalStateException("nothing to remove"); LinkedPositionalList.this.remove(recent); // remove from outer list recent = null; // do not allow remove again until next is called } } private class PositionIterable implements Iterable> { public Iterator> iterator() { return new PositionIterator(); } } @Override public Iterable> positions() { return new PositionIterable(); // create a new instance of the inner class } private class ElementIterator implements Iterator { Iterator> posIterator = new PositionIterator(); public boolean hasNext() { return posIterator.hasNext(); } public E next() { return posIterator.next().getElement(); } // return element! public void remove() { posIterator.remove(); } } @Override public Iterator iterator() { return new ElementIterator(); } public String toString() { StringBuilder sb = new StringBuilder("("); Node walk = header.getNext(); while (walk != trailer) { sb.append(walk.getElement()); walk = walk.getNext(); if (walk != trailer) sb.append(", "); } sb.append(")"); return sb.toString(); } }
Hi. I have answered the same question before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks
// LinkedPositionalList.java
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedPositionalList<E> implements PositionalList<E> {
// ---------------- nested Node class ----------------
/**
* Node of a doubly linked list, which stores a reference to its element and
* to both the previous and next node in the list.
*/
private static class Node<E> implements Position<E> {
/** The element stored at this node */
private E element; // reference to the element stored at this node
/** A reference to the preceding node in the list */
private Node<E> prev; // reference to the previous node in the list
/** A reference to the subsequent node in the list */
private Node<E> next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e
* the element to be stored
* @param p
* reference to a node that should precede the new node
* @param n
* reference to a node that should follow the new node
*/
public Node(E e, Node<E> p, Node<E> n) {
element = e;
prev = p;
next = n;
}
// public accessor methods
/**
* Returns the element stored at the node.
*
* @return the stored element
* @throws IllegalStateException
* if node not currently linked to others
*/
public E getElement() throws IllegalStateException {
if (next == null) // convention for defunct node
throw new IllegalStateException("Position no longer valid");
return element;
}
/**
* Returns the node that precedes this one (or null if no such node).
*
* @return the preceding node
*/
public Node<E> getPrev() {
return prev;
}
/**
* Returns the node that follows this one (or null if no such node).
*
* @return the following node
*/
public Node<E> getNext() {
return next;
}
public void setElement(E e) {
element = e;
}
public void setPrev(Node<E> p) {
prev = p;
}
public void setNext(Node<E> n) {
next = n;
}
}
private Node<E> header; // header sentinel
private Node<E> trailer; // trailer sentinel
private int size = 0; // number of elements in the list
public LinkedPositionalList() {
header = new Node<E>(null, null, null); // create header
trailer = new Node<E>(null, header, null); // trailer is preceded by
// header
header.setNext(trailer); // header is followed by trailer
}
private Node<E> validate(Position<E> p) throws IllegalArgumentException {
if (!(p instanceof Node))
throw new IllegalArgumentException("Invalid p");
Node<E> node = (Node<E>) p; // safe cast
if (node.getNext() == null) // convention for defunct node
throw new IllegalArgumentException("p is no longer in the list");
return node;
}
private Position<E> position(Node<E> node) {
if (node == header || node == trailer)
return null; // do not expose user to the sentinels
return node;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Position<E> first() {
return position(header.getNext());
}
@Override
public Position<E> last() {
return position(trailer.getPrev());
}
@Override
public Position<E> before(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return position(node.getPrev());
}
@Override
public Position<E> after(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return position(node.getNext());
}
private Position<E> addBetween(E e, Node<E> pred, Node<E> succ) {
Node<E> newest = new Node<E>(e, pred, succ); // create and link a new
// node
pred.setNext(newest);
succ.setPrev(newest);
size++;
return newest;
}
@Override
public Position<E> addFirst(E e) {
return addBetween(e, header, header.getNext()); // just after the header
}
@Override
public Position<E> addLast(E e) {
return addBetween(e, trailer.getPrev(), trailer); // just before the
// trailer
}
@Override
public Position<E> addBefore(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> node = validate(p);
return addBetween(e, node.getPrev(), node);
}
@Override
public Position<E> addAfter(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> node = validate(p);
return addBetween(e, node, node.getNext());
}
@Override
public E set(Position<E> p, E e) throws IllegalArgumentException {
Node<E> node = validate(p);
E answer = node.getElement();
node.setElement(e);
return answer;
}
@Override
public E remove(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
Node<E> predecessor = node.getPrev();
Node<E> successor = node.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
E answer = node.getElement();
node.setElement(null); // help with garbage collection
node.setNext(null); // and convention for defunct node
node.setPrev(null);
return answer;
}
private class PositionIterator implements Iterator<Position<E>> {
private Position<E> cursor = first(); // position of the next element to
// report
private Position<E> recent = null; // position of last reported element
public boolean hasNext() {
return (cursor != null);
}
public Position<E> next() throws NoSuchElementException {
if (cursor == null)
throw new NoSuchElementException("nothing left");
recent = cursor; // element at this position might later be removed
cursor = after(cursor);
return recent;
}
public void remove() throws IllegalStateException {
if (recent == null)
throw new IllegalStateException("nothing to remove");
LinkedPositionalList.this.remove(recent); // remove from outer list
recent = null; // do not allow remove again until next is called
}
}
private class PositionIterable implements Iterable<Position<E>> {
public Iterator<Position<E>> iterator() {
return new PositionIterator();
}
}
@Override
public Iterable<Position<E>> positions() {
return new PositionIterable(); // create a new instance of the inner
// class
}
private class ElementIterator implements Iterator<E> {
Iterator<Position<E>> posIterator = new PositionIterator();
public boolean hasNext() {
return posIterator.hasNext();
}
public E next() {
return posIterator.next().getElement();
} // return element!
public void remove() {
posIterator.remove();
}
}
@Override
public Iterator<E> iterator() {
return new ElementIterator();
}
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node<E> walk = header.getNext();
while (walk != trailer) {
sb.append(walk.getElement());
walk = walk.getNext();
if (walk != trailer)
sb.append(", ");
}
sb.append(")");
return sb.toString();
}
/**
* method to swap nodes at indices p and q
*
* @param p
* index of first node to swap
* @param q
* index of second node to swap
*/
public void swap(int p, int q) {
// validating indices
if (p >= 0 && p < size && q >= 0 && q < size) {
// getting a reference to first node and advancing it p times
Node<E> n1 = header.getNext();
for (int i = 0; i < p; i++) {
n1 = n1.getNext();
}
//n1 is now node at index p
//doing the same for second node
Node<E> n2 = header.getNext();
for (int i = 0; i < q; i++) {
n2 = n2.getNext();
}
//n2 is now node at index q
//storing next of n1
Node<E> temp = n1.getNext();
//setting n2.next as n1.next
n1.setNext(n2.getNext());
//setting n1 as previous of n2.next
n2.getNext().setPrev(n1);
//setting temp as next of n2
n2.setNext(temp);
//setting n2 as previous of n2
temp.setPrev(n2);
//storing previous of n1
temp = n1.getPrev();
//setting n2.prev as new prev for n1
n1.setPrev(n2.getPrev());
//setting n1 as next of n2.prev
n2.getPrev().setNext(n1);
//setting temp as n2.prev
n2.setPrev(temp);
//setting n2 as next of temp
temp.setNext(n2);
}
}
}
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying...
Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation in Java #########LinkedBinary Tree class######### public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> { //---------------- nested Node class ---------------- /** Nested static class for a binary tree node. */ protected static class Node<E> implements Position<E> { private E element; // an element stored at this node private Node<E> parent; // a reference to the parent node (if any) private Node<E> left; // a reference to the left...
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...
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...
Complete P16.1 and P16.4 (Class Name: NewMethodDemo) Once complete, upload all .java files. For primary test class: Remember your header with name, date, and assignment. Also include class names that will be tested. Psuedocode (level 0 or mixture of level 0 and algorithm [do not number steps]) is required if main() contains more than simple statements (for example, your program includes constructs for decisions (if/else), loops, and methods. For Secondary class(es): Include a JavaDoc comment that describes the purpose of...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to both classes: public void reverseThisList(), This method will reverse the lists. When testing the method: print out the original list, call the new method, then print out the list again ------------------------------------------------------------------------- //ARRAY LIST class: public class ArrayList<E> implements List<E> { /** Array of elements in this List. */ private E[] data; /** Number of elements currently in this List. */ private int size; /**...
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...
Please answer in Java. The code that needs to be modified is below. Thank you. Question: Implement Doubly Linked List add method which add an element to a specific position. - It’s an instance method that takes a position and an element, then adds the element to this specific position and shifts the element currently at this position and any subsequent elements to the right. It throws an exception if the position is out of bound. It traverses the list...
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list. package linkedlists; public class SinglyLinkedList<E> implements Cloneable { // ---------------- nested Node class...
Complete HeapPriorityQueue (7 points). In lecture we implemented HeapPriorityQueue using an array-based representation of a heap (a complete binary tree whose entries satisfy the heap-order property). For this problem, complete the included HeapPriorityQueue class by using the LinkedBinaryTree class to represent a heap. Hint: the most challenging part of this problem is identifying the last Position in the heap and the next available Position in the heap. It is suggested that you review the array-based heap to better understand how...
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...