Question

Author code
/**
 * LinkedList class implements a doubly-linked list.
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
    /**
     * Construct an empty LinkedList.
     */
    public MyLinkedList( )
    {
        doClear( );
    }
    
    private void clear( )
    {
        doClear( );
    }
    
    /**
     * Change the size of this collection to zero.
     */
    public void doClear( )
    {
        beginMarker = new Node<>( null, null, null );
        endMarker = new Node<>( null, beginMarker, null );
        beginMarker.next = endMarker;
        
        theSize = 0;
        modCount++;
    }
    
    /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size( )
    {
        return theSize;
    }
    
    public boolean isEmpty( )
    {
        return size( ) == 0;
    }
    
    /**
     * Adds an item to this collection, at the end.
     * @param x any object.
     * @return true.
     */
    public boolean add( AnyType x )
    {
        add( size( ), x );   
        return true;         
    }
    
    /**
     * Adds an item to this collection, at specified position.
     * Items at or after that position are slid one position higher.
     * @param x any object.
     * @param idx position to add at.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
     */
    public void add( int idx, AnyType x )
    {
        addBefore( getNode( idx, 0, size( ) ), x );
    }
    
    /**
     * Adds an item to this collection, at specified position p.
     * Items at or after that position are slid one position higher.
     * @param p Node to add before.
     * @param x any object.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
     */    
    private void addBefore( Node<AnyType> p, AnyType x )
    {
        Node<AnyType> newNode = new Node<>( x, p.prev, p );
        newNode.prev.next = newNode;
        p.prev = newNode;         
        theSize++;
        modCount++;
    }   
    
    
    /**
     * Returns the item at position idx.
     * @param idx the index to search in.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public AnyType get( int idx )
    {
        return getNode( idx ).data;
    }
        
    /**
     * Changes the item at position idx.
     * @param idx the index to change.
     * @param newVal the new value.
     * @return the old value.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public AnyType set( int idx, AnyType newVal )
    {
        Node<AnyType> p = getNode( idx );
        AnyType oldVal = p.data;
        
        p.data = newVal;   
        return oldVal;
    }
    
    /**
     * Gets the Node at position idx, which must range from 0 to size( ) - 1.
     * @param idx index to search at.
     * @return internal node corresponding to idx.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size( ) - 1, inclusive.
     */
    private Node<AnyType> getNode( int idx )
    {
        return getNode( idx, 0, size( ) - 1 );
    }

    /**
     * Gets the Node at position idx, which must range from lower to upper.
     * @param idx index to search at.
     * @param lower lowest valid index.
     * @param upper highest valid index.
     * @return internal node corresponding to idx.
     * @throws IndexOutOfBoundsException if idx is not between lower and upper, inclusive.
     */    
    private Node<AnyType> getNode( int idx, int lower, int upper )
    {
        Node<AnyType> p;
        
        if( idx < lower || idx > upper )
            throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );
            
        if( idx < size( ) / 2 )
        {
            p = beginMarker.next;
            for( int i = 0; i < idx; i++ )
                p = p.next;            
        }
        else
        {
            p = endMarker;
            for( int i = size( ); i > idx; i-- )
                p = p.prev;
        } 
        
        return p;
    }
    
    /**
     * Removes an item from this collection.
     * @param idx the index of the object.
     * @return the item was removed from the collection.
     */
    public AnyType remove( int idx )
    {
        return remove( getNode( idx ) );
    }
    
    /**
     * Removes the object contained in Node p.
     * @param p the Node containing the object.
     * @return the item was removed from the collection.
     */
    private AnyType remove( Node<AnyType> p )
    {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        
        return p.data;
    }
    
    /**
     * Returns a String representation of this collection.
     */
    public String toString( )
    {
        StringBuilder sb = new StringBuilder( "[ " );

        for( AnyType x : this )
            sb.append( x + " " );
        sb.append( "]" );

        return new String( sb );
    }

    /**
     * Obtains an Iterator object used to traverse the collection.
     * @return an iterator positioned prior to the first element.
     */
    public java.util.Iterator<AnyType> iterator( )
    {
        return new LinkedListIterator( );
    }

    /**
     * This is the implementation of the LinkedListIterator.
     * It maintains a notion of a current position and of
     * course the implicit reference to the MyLinkedList.
     */
    private class LinkedListIterator implements java.util.Iterator<AnyType>
    {
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        
        public boolean hasNext( )
        {
            return current != endMarker;
        }
        
        public AnyType next( )
        {
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( );
            if( !hasNext( ) )
                throw new java.util.NoSuchElementException( ); 
                   
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }
        
        public void remove( )
        {
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( );
            if( !okToRemove )
                throw new IllegalStateException( );
                
            MyLinkedList.this.remove( current.prev );
            expectedModCount++;
            okToRemove = false;       
        }
    }
    
    /**
     * This is the doubly-linked list node.
     */
    private static class Node<AnyType>
    {
        public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
        {
            data = d; prev = p; next = n;
        }
        
        public AnyType data;
        public Node<AnyType>   prev;
        public Node<AnyType>   next;
    }
    
    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;
}

class TestLinkedList
{
    public static void main( String [ ] args )
    {
        MyLinkedList<Integer> lst = new MyLinkedList<>( );

        for( int i = 0; i < 10; i++ )
                lst.add( i );
        for( int i = 20; i < 30; i++ )
                lst.add( 0, i );

        lst.remove( 0 );
        lst.remove( lst.size( ) - 1 );

        System.out.println( lst );

        java.util.Iterator<Integer> itr = lst.iterator( );
        while( itr.hasNext( ) )
        {
                itr.next( );
                itr.remove( );
                System.out.println( lst );
        }
    }
}

In this project you will add methods to an existing linked list class.



Description:

Modify the author's "MyLinkedList" class to add the following methods.
Perform checking of the parameters and throw exceptions where appropriate.  
  

10 points each (a-h)

   a.  itemCount
        receives a value and returns a count of the number of times this item
        is found in the list.

   b.  swap
        receives two index positions as parameters and swaps the two nodes 
        (the nodes, not just the values inside) at these positions, provided 
        both positions are within the current size.

   c.  sublist
        receives two indexes and returns an ArrayList of node values from the first
        index to the second index, provided the indexes are valid.

   d.  select
        receives a variable number of indexes, and returns an ArrayList of node values
        corresponding to each index given, provided the indexes are valid.

   e.  reverse
        returns a new MyLinkedList that has the elements in reverse order.

   f.  erase 
        receives an index position and number of elements as parameters, and
        removes elements beginning at the index position for the number of 
        elements specified, provided the index position is within the size
        and together with the number of elements does not exceed the size.

   g.  insertList
        receives a List and an index position as parameters, and copies all of the 
        passed list into the existing list at the position specified by the parameter,
        provided the index position does not exceed the size.

   h.  shift
        receives an integer and shifts the list this many nodes forward or backward,
        for example, if passed 2, the first two nodes move to the tail, or if 
        passed -3, the last three nodes move to the front.  
           
              +2:  abcde -> cdeab       -3:  abcde ->  cdeab
          

20 points
   i.  main
        change the main method to demonstrate each of your methods.
  
   


Submit to eLearning:
 MyLinkedList.java

Answer 1

import java.util.*;

  

class Main{

    static Node head;

    // Doubly linked list node definition

    static class Node{

        int data;

        Node next;

        Node prev;

    };

   // Function to insert node in the list

    static void addNode(int value) {

        // List is empty so create a single node furst

        if (head == null) {

            Node new_node = new Node();

            new_node.data = value;

            new_node.next = new_node.prev = new_node;

            head = new_node;

            return;

        }

  

        // find last node in the list if list is not empty

          Node last = (head).prev;    //previous of head is the last node

  

        // create a new node

        Node new_node = new Node();

        new_node.data = value;

  

        // next of new_node will point to head since list is circular

        new_node.next = head;

  

        // similarly previous of head will be new_node

        (head).prev = new_node;

  

        // change new_node=>prev to last

        new_node.prev = last;

  

        // Make new node next of old last

        last.next = new_node;

    }

  

static void printNodes()   {

        Node temp = head;

        //traverse in forward direction starting from head to print the list

        while (temp.next != head)

        {

            System.out.printf("%d ", temp.data);

            temp = temp.next;

        }

        System.out.printf("%d ", temp.data);

  

        //traverse in backward direction starting from last node

        System.out.printf("\nCircular doubly linked list travesed backward: \n");

        Node last = head.prev;

        temp = last;

        while (temp.prev != last)

        {

            System.out.printf("%d ", temp.data);

            temp = temp.prev;

        }

        System.out.printf("%d ", temp.data);

    }

  

    public static void main(String[] args)

    {

        //the empty list

        Node l_list = null;

  

        // add nodes to the list

        addNode(40);

        addNode(50);

        addNode(60);

        addNode(70);

        addNode(80);

  

        //print the list

        System.out.printf("Circular doubly linked list: ");

        printNodes();

    }

}