Question
JAVA: Given a doubly-linked list interface below, write NEW instance methods of the following: Using the operations defined for a doubly linked List data structure,
JAVA: Given a doubly-linked list interface below, write NEW instance methods of the following:
Using the operations defined for a doubly linked List data structure, given in the MyLinkedList interface on our ecampus page. Write a NEW instance called toStringReverse(). This method is specific to a doubly linked list and is not part of the MyLinkedList interface. This method creates a comma delimited list of the lists contents in reverse. It has NO parameters and returns a value of type String.
Using the operations defined for a doubly linked List data structure, given in the MyLinkedList interface on our ecampus page. Write a NEW instance called addAscending. This method is specific to our doubly linked list and is not part of the MyLinkedList interface. This method receives a single parameter which is the value to be inserted into the list. Since this is a generic list we may ASSUME that the class on which the list is instantiated implements the Comparable interface [thus contains a compareTo method].
public class DLinkedList implements MyLinkedList{ // this is an "inner" class that is contained // inside sLinkedList and represents a "contained" // node class that is totally private to // SLinkedList private static class DNode { S item; DNode next; DNode prev; public DNode (S value) { item = value; next=null; prev = null; } public DNode (S value, DNode predecessor, DNode successor) { item = value; next = successor; prev = predecessor; } }// end class node // Data members of dLinkedList private DNode head; private DNode tail; private int currentSize; public DLinkedList(){ currentSize =0; head = null; tail = null; } public boolean isEmpty(){ return (currentSize==0); }// end isempty public int size(){ return currentSize; }// end size /** * This method deletes all of the list's contents. * * */ public void clear(){ head = null; tail = null; currentSize =0; }// end clear /** * This method searches the list for the * specified value and returns the index * number of the first element containing * the value or -1 if the value is * not found. * * @param value: the search value * @return index of element containing value or -1 * */ public int find( S value){ int position = 0; int returnValue = -1; DNode nextNode; nextNode = head; while ( nextNode != null){ if( nextNode.item.equals( value)) { returnValue = position; break; } position++; nextNode = nextNode.next; } return returnValue; } public S get (int position) { // This method retrieves the value stored in a node in the list // returns the value, but does not unlink the node. The method // receives the logical position of the node in the list. S returnValue=null; DNode currentNode=null; // inchworm variable if(position > currentSize-1 || position < 0) throw new ListException("No such position"); // We want to be efficient... // Iterate until we locate the node who's value //should be returned // after the loop nextNode points to the node // containing the value we want. /// I need a loop if (position <= this.currentSize/2){ // start at head currentNode = head; for(int i=0; i < position; i++){ currentNode = currentNode.next; } returnValue = (S) currentNode.item; } else{ // start at tail currentNode = tail; for(int i=this.currentSize-1; i > position; i--) currentNode = currentNode.prev; returnValue = (S) currentNode.item; } return returnValue; }// end getvalue /** * This method inserts the value at the given position. * * @param position location where new value is to be inserted, 0<=position<=current size * @param value new value to be added to the list * */ public void add( int position, S value){ DNode currentNode; DNode newNode; if (position < 0 || position > currentSize) throw new ListException("Invalid position given"); // There are 4 special conditions for which we must plan // 1) Adding the first node to an empty list if ( this.isEmpty()){ tail = head = new DNode( value ); } // 2) Adding a new node at the head of the list else if ( position == 0 ){ newNode = new DNode(value); newNode.next =head; head.prev = newNode; head = newNode; } // 3) Adding a new node at the tail of the list else if (position == this.currentSize){ newNode = new DNode( value ); tail.next = newNode; newNode.prev = tail; tail = newNode; } // 4) Adding a new node in the middle else{ currentNode = head; for (int i=0; i < position; i++) currentNode = currentNode.next; // CurrentNode is not AT the position where we want to add newNode = new DNode( value); newNode.next = currentNode; newNode.prev = currentNode.prev; currentNode.prev.next = newNode; currentNode.prev = newNode; } currentSize++; } /** * This method inserts the value at the end of the list. * * @param value new value to be added to the list * */ public void add( S value){ this.add( this.currentSize, value); } /** * This method removes and RETURNS the value at the location * indicated by position. * * @param position location of value to remove from the list 0<=position currentNode; if (position < 0 || position >= this.currentSize) { throw new ListException("error"); } // There are 4 special conditions for which we must plan // 1) Removing the only node in a list if (this.currentSize == 1 && position ==0){ returnValue = (S) head.item; head = tail = null; } // 2) Removing the head of the list else if (position ==0){ currentNode = head; head = head.next; currentNode.next =null; head.prev = null; } // 3) Removing the tail of the list else if (position == this.currentSize-1){ currentNode = tail; tail = tail.prev; tail.next = null; currentNode.prev =null; } // 4) Removing a node in the middle else{ currentNode = head; for (int i=0; i < position; i++) currentNode = currentNode.next; // curreent node is NOW the node to delete currentNode.prev.next = currentNode.next; currentNode.next.prev = currentNode.prev; currentNode.next = null; currentNode.prev = null; } this.currentSize--; return returnValue; } /** * This method removes all occurrences of elements in the list argument from the list * * * * */ public void removeAll(MyLinkedList list){ // iterate through the list parameter removing each occurrence of // the values it contains boolean result=false; S temp; int pos=-1; for (int i=0; i < list.size(); i++){ temp = list.get(i); // retrieve the ith element pos = this.find(temp); while(pos != -1){ result = true; this.remove(pos); // remove the element pos = find( temp ); }// end while }// end for } // to string method public String toString(){ String returnValue=""; DNode current =head; while(current != null){ returnValue = returnValue + current.item + " "; current = current.next; } return returnValue; } }// end class
public interface MyLinkedList{ /** * This method returns true if the current * size of the list is zero. * * */ public boolean isEmpty(); /** * This method returns the current number * of elements in the list. * * */ public int size(); /** * This method searches the list for the * specified value and returns the index * number of the first element containing * the value or -1 if the value is * not found. * @param value: the search value * @return index of element containing value or -1 * */ public int find( S value); /** * This method returns the value at a specific * position in the list. * * @param position: location of element to return 0<=positionlist); /** * This method deletes all of the list's contents. * * */ public void clear(); /** * This method produces a comma separated list of the list elements * */ public String toString(); }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started