1. Engineering
  2. Computer Science
  3. modify the single linked list java code to implement a...

Question: modify the single linked list java code to implement a...

Question details

Modify the single linked list java code to implement a DOUBLY linked list. [Data Structures]

Modify the ListReferenceBased.java file to implement the ListReferenceBased class as a . You need to modify the Node.java file to convert the implementation for a singly linked list . You need to modify the add and the remove methods in ListReferenceBased.java. doubly linked list. to that of a doubly linked list. . You must also implement the following missing methods in ListReferenceBased class as you did in the previous lab for the ListArrayBased class: contains returns either the index of the location in the list where the argument is present or -1 if the argument is not contained in the list, append appends the argument to the end of the list delete delete checks if a given item is contained in the list, and if it exists, deletes it display displays the list items in sequence displayReverse displays the list items in sequence constructors add a constructor that creates a list with the one generic element as its only content and a copy constructor when you add a new method, write the corresponding javadoc comments.PLEASE SEE THIS LINK FOR ALL OF THE JAVA FILES INCLUDING NODE.JAVA https://pastebin.com/t6Xfix8h

*** CODE TO BE MODIFIED ***

ListReferenceListBased.java

/**
* Reference-based implementation of ADT list.
* Modify the code to implement a doubly linked list.
* @author
*/

import java.util.Iterator;

public class ListReferenceBased implements ListInterface, Iterable{

/** reference to the first element of the list */
private Node head;
/** number of items in list */
private int numItems;
  
/** default constructor */
public ListReferenceBased() {
   numItems = 0;
   head = null;
} // end default constructor
  
/** Tests if this list has no elements.
* @return true if this list has no elements;
* false otherwise.
*/

public boolean isEmpty() {
   return numItems == 0;
} // end isEmpty
  
/**
* Returns the number of elements in this list.
* @return the number of elements in this list.
*/

public int size() {
   return numItems;
} // end size
  

/** Locates a specified node in a linked list.
*

  • Postcondition:
    * @param index position of the desired node. Assumes that
    * 1 <= index <= numItems+1
    * @return a reference to the desired Node.
    */
    private Node find(int index) {
       Node curr = head;
       for (int skip = 1; skip < index; skip++) {
       curr = curr.getNext();
       } // end for
       return curr;
    } // end find

    /** get the item location at the specified position in the list
    * @param index position of the node containing the item
    * @return the Object located at the specified index
    * @throws ListIndexOutOfBoundsException if the index is out of
    * range, i.e. when index <=0 || index > size()
    */
    public E get(int index)
       throws ListIndexOutOfBoundsException {
       if (index >= 1 && index <= numItems) {
       // get reference to node, then data in node
       Node curr = find(index);
       E dataItem = curr.getItem();
       return dataItem;
       }
       else {
       throw new ListIndexOutOfBoundsException(
                           "List index out of bounds exception on get");
       } // end if
    } // end get
      
      
      
    /**
    * Inserts the specified element at the specified position in this
    * list. Shifts the element currently at that position (if any)
    * and any subsequent elements to the right (adds one to their
    * indices).
    * @param index index at which the specified element is to be
    * inserted.
    * @param item element to be inserted.
    * @throws IndexOutOfBoundsException - if index is out of range
    * (index < 0 || index > size()).
    */
    public void add(int index, E item)
       throws ListIndexOutOfBoundsException {
       if (index >= 1 && index <= numItems+1) {
       if (index == 1) {
           // insert the new node containing item at
           // beginning of list
           Node newNode = new Node(item, head);
           head = newNode;
       }
       else{
           Node prev = find(index-1);
           // insert the new node containing item after
           // the node that prev references
           Node newNode = new Node(item, prev.getNext());
           prev.setNext(newNode);
          
       } // end if
       numItems++;
       }
       else {
       throw new ListIndexOutOfBoundsException(
                           "List index out of bounds exception on add");
       } // end if
    } // end add
      

    /**
    * appends the specified element to the end of this list.
    * @param elt element to be added at the end of the list
    */
    public void append(E item)
    {
       // TO COMPLETE
    }//end append
      

    /**
    * Removes the element at the specified position in this
    * list. Shifts any subsequent elements to the left (subtracts one
    * from their indices).
    * @param index the index of the element to remove
    * @throws IndexOutOfBoundsException - if index is out of range
    * (index < 0 || index > size()).
    */
    public void remove(int index)
       throws ListIndexOutOfBoundsException {
       if (index >= 1 && index <= numItems) {
       if (index == 1) {
           // delete the first node from the list
           head = head.getNext();
       }
       else{
           Node prev = find(index-1);
           // delete the node after the node that prev
           // references, save reference to node
           Node curr = prev.getNext();
           prev.setNext(curr.getNext());
       } // end if
       numItems--;
       } // end if
       else {
       throw new ListIndexOutOfBoundsException(
                           "List index out of bounds exception on remove");
       } // end if
    } // end remove
      
      
    /**
    * Remove all the elements in this list.
    */
    public void removeAll() {
       // setting head to null causes list to be
       // unreachable and thus marked for garbage
       // collection
       head = null;
       numItems = 0;
    } // end removeAll
      


    /**
    * delete the the specified element in this list if exists,
    * otherwise state that the item is not in the current
    * list. Shifts any subsequent elements to the left (subtracts one
    * from their indices).
    * @param elt the element, if it exists, to delete
    */
    public void delete(E item){
       //TO COMPLETE
    }
      
    /**
    * Looks for the index of the specified element in this list. If
    * the element is not present, the method returns -1
    * @param elt the element which index is looked for.
    * @return either the index of the location in the list where the
    * argument is present or -1 if the argument is not
    * contained in the list.
    */
    public int contains(E elt){
       // TO COMPLETE
    }
      
    /**
    * Prints all the elements in this list on the console in sequence
    */
    public void display(){
       // TO COMPLETE
    }

    /**
    * Prints all the elements in this list on the console in reverse
    * order
    */
    public void displayReverse(){
       // TO COMPLETE
    }

    public ListReferenceBasedIterator iterator(){
       return new ListReferenceBasedIterator(head);
    }
    public class ListReferenceBasedIterator implements Iterator{
       Node current;

       public ListReferenceBasedIterator(Node node){
       current=node;
       }
      
       public boolean hasNext(){
       return (current!=null);
       }

       public E next(){
       E elt = current.getItem();
       current = current.getNext();
       return elt;
       }

       public void remove(){}
    }
    } // end ListReferenceBased

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution