CS3401 Assignment 6
Homework Assignment #6
Exercise #1
Write an implementation of a generic version of MyLinkedList.java and its methods. In addition, you must modify the MyLinkedList class in the following ways while maintaining a generic implementation of this class:- Make the MyLinkedList class a doubly linked list. This means adding to the Node inner class the following field which also starts off equal to null:
public Node prev;
- As the program works now, the "list" field in the main MyLinkedList class always points to the first element in the linked list. Add a "last" field as well that always points to the last element.
public Node last;
Note: this field is not stored in the Node inner class.
- Modify the toString() method of the MyLinkedList class so that it returns a string consisting of all of the elements of the list from first to last on one line separated by commas with "<" in the front and ">" at the back, and then that one line is followed by a second line with all of the elements from last to first on one line separated by commas with "<<" in the front and ">>" at the back.
The first line must be produced by starting from the first node and traversing down using the next fields, and the second line must be produced by starting from the last node and traversing up using the prev
fields. For example, if the elements in the list were 2, 4, 6, 8, then
the following two-line string would be returned by the toString()
method:
<2, 4, 6, 8> <<8, 6, 4, 2>> - Add the following methods to your MyLinkedList class:
- public void addFirst(E e)
// Inserts the given element at the beginning of the list. - public void addLast(E e)
// Inserts the given element at the end of the list. - public void clear()
// Removes all of the elements from this list. - public boolean contains(E e)
// Returns true if the given element is in the list. - public E get(int index)
// Gets the element at the specified position in this list. - public E getLast()
// Gets the last element in the list. - public int indexOf(E e)
// Returns the index of the first occurrence of the
// given element, or -1 if not found. - public int lastIndexOf(E e)
// Returns the index of the last occurrence of the
// given element, or -1 if not found. - public boolean removeFirstOccurrence(E e)
// Removes the first occurrence of the given element.
// Returns true if found, false if not. - public boolean removeLastOccurrence(E e)
// Removes the last occurrence of the given element.
// Returns true if found, false if not.
- public void addFirst(E e)
And finally, you must also modify the TestMyLinkedList.java driver program (which now works with the non-generic MyLinkedList class), so that it uses the generic version of the MyLinkedList class to create a linked list of Integers. Add at least 5 Integer elements initially and then test all of the methods.
------------------------------------------------------------------------------------------------
This solution i think is mostly stable. About 80%
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=
mylinkedlist.java----------------------------------------------------------------------------------------------
/*Dalibor Labudovic
* Prof Alan Shaw
* CS3401
*
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
public MyLinkedList( )
{
clear( );
}
public void clear( )
{
beginMarker = new Node<AnyType>( null, null, null );
endMarker = new Node<AnyType>( null, beginMarker, null );
beginMarker.next = endMarker;
theSize = 0;
}
public boolean contains(AnyType x)
{
return IndexOf(x) >= 0;
}
public int size( )
{
return theSize;
}
public boolean isEmpty( )
{
return size( ) == 0;
}
public boolean add( AnyType x )
{
add( size( ), x );
return true;
}
public void add( int idx, AnyType x )
{
addBefore( getNode( idx, 0, size( ) ), x );
}
public void addBefore( Node<AnyType> p, AnyType x )
{
Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
}
public void addFirst(AnyType x)
{
add(0, x);
}
public void addLast(AnyType x)
{
add(size(), x);
}
public AnyType get( int idx )
{
return getNode( idx ).data;
}
public AnyType getLast()
{
return (AnyType) getNode(size()-1);
}
public AnyType set( int idx, AnyType newVal )
{
Node<AnyType> p = getNode( idx );
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
private Node<AnyType> getNode( int idx )
{
return getNode( idx, 0, size( ) - 1 );
}
public int IndexOf(AnyType x)
{
Node current = beginMarker;
int result = 0;
for(int i = 0; i < theSize;i++)
{
if(x.equals(current.data))
{
result = i;
return result;
}
}
return result;
}
public int lastIndexOf(AnyType x)
{
return IndexOf(x);
}
public boolean removeFirstOccurrence(AnyType x)
{
int result = (Integer) remove(IndexOf(x));
if(result == 0)
return false;
else
return true;
}
public boolean removeLastOccurence (AnyType x)
{
int result = (Integer) remove(lastIndexOf(x));
if(result == 0)
return false;
else
return true;
}
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;
}
public AnyType remove( int idx )
{
return remove( getNode( idx ) );
}
private AnyType remove( Node<AnyType> p )
{
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;
}
public String toString()
{
StringBuilder sb = new StringBuilder( "< " );
for( AnyType x : this )
sb.append( x + " " );
sb.append( ">" );
return new String( sb );
}
public java.util.Iterator<AnyType> iterator( )
{
return new LinkedListIterator( );
}
private class LinkedListIterator implements java.util.Iterator<AnyType>
{
private Node<AnyType> current = beginMarker.next;
private boolean okToRemove = false;
public boolean hasNext( )
{
return current != endMarker;
}
public AnyType next( )
{
if( !hasNext( ) )
throw new java.util.NoSuchElementException( );
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove( )
{
if( !okToRemove )
throw new IllegalStateException( );
MyLinkedList.this.remove( current.prev );
okToRemove = false;
}
}
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 Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
}
TestLinkedList.java
/*Dalibor Labudovic
* Prof Alan Shaw
* CS3401
*
*/
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList list = new MyLinkedList();
list.add(4);
list.add(48);
list.add(90);
list.add(34);
list.add(23);
System.out.println("Original list" + list.toString());
list.add(0,1);
System.out.println("Added 1 to position 0 list: " + list.toString());
list.remove(4);
System.out.println("Removed from positon 4: " + list.toString());
System.out.println("Does the list contain 48: " +list.contains(48));
list.addLast(4);
System.out.println("add last 4: " + list.toString());
list.addFirst(2);
System.out.println("add first 2: " + list.toString());
System.out.println("Last index of 4:" + list.lastIndexOf(4));
System.out.println("remove first occurance of 4:" + list.removeFirstOccurrence(4));
System.out.println("remove last occurance of 3:" + list.removeFirstOccurrence(3));
}
}
Comments
Post a Comment