Question

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 the class definition at the top of the file.

Block level comments are required. You should comment anytime coding is not clear. That is just good programming.

Question

P16.1
Add a method reverse to our implementation of the LinkedList class that reverses the links in a list. Implement this method by directly rerouting the links, not by using an iterator.

P16.4
Add a method size to our implementation of the LinkedList class that computes the number of elements in the list by following links and counting the elements until the end of the list is reached.

LinkedList Class

import java.util.NoSuchElementException;

/**
A linked list is a sequence of nodes with efficient
element insertion and removal. This class
contains a subset of the methods of the standard
java.util.LinkedList class.
*/
public class LinkedList
{  
private Node first;

/**
Constructs an empty linked list.
*/
public LinkedList()
{  
first = null;
}

/**
Returns the first element in the linked list.
@return the first element in the linked list
*/
public Object getFirst()
{  
if (first == null) { throw new NoSuchElementException(); }
return first.data;
}

/**
Removes the first element in the linked list.
@return the removed element
*/
public Object removeFirst()
{  
if (first == null) { throw new NoSuchElementException(); }
Object element = first.data;
first = first.next;
return element;
}

/**
Adds an element to the front of the linked list.
@param element the element to add
*/
public void addFirst(Object element)
{  
Node newNode = new Node();
newNode.data = element;
newNode.next = first;
first = newNode;
}

/**
Returns an iterator for iterating through this list.
@return an iterator for iterating through this list
*/
public ListIterator listIterator()
{  
return new LinkedListIterator();
}

class Node
{  
public Object data;
public Node next;
}

class LinkedListIterator implements ListIterator
{  
private Node position;
private Node previous;
private boolean isAfterNext;

/**
Constructs an iterator that points to the front
of the linked list.
*/
public LinkedListIterator()
{  
position = null;
previous = null;
isAfterNext = false;
}
  
/**
Moves the iterator past the next element.
@return the traversed element
*/
public Object next()
{  
if (!hasNext()) { throw new NoSuchElementException(); }
previous = position; // Remember for remove
isAfterNext = true;

if (position == null)
{
position = first;
}
else
{
position = position.next;
}

return position.data;
}
  
/**
Tests if there is an element after the iterator position.
@return true if there is an element after the iterator position
*/
public boolean hasNext()
{  
if (position == null)
{
return first != null;
}
else
{
return position.next != null;
}
}
  
/**
Adds an element before the iterator position
and moves the iterator past the inserted element.
@param element the element to add
*/
public void add(Object element)
{  
if (position == null)
{
addFirst(element);
position = first;
}
else
{  
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
position.next = newNode;
position = newNode;
}

isAfterNext = false;
}
  
/**
Removes the last traversed element. This method may
only be called after a call to the next() method.
*/
public void remove()
{  
if (!isAfterNext) { throw new IllegalStateException(); }

if (position == first)
{
removeFirst();
}
else
{  
previous.next = position.next;
}
position = previous;
isAfterNext = false;
}

/**
Sets the last traversed element to a different value.
@param element the element to set
*/
public void set(Object element)
{
if (!isAfterNext) { throw new IllegalStateException(); }
position.data = element;
}
}
}

Answer 1

import java.util.NoSuchElementException;

/**

A linked list is a sequence of nodes with efficient

element insertion and removal. This class

contains a subset of the methods of the standard

java.util.LinkedList class.

*/

public class LinkedList

{

private Node first;

/**

Constructs an empty linked list.

*/

public LinkedList()

{

first = null;

}

/**

Returns the first element in the linked list.

@return the first element in the linked list

*/

public Object getFirst()

{

if (first == null) { throw new NoSuchElementException(); }

return first.data;

}

/**

Removes the first element in the linked list.

@return the removed element

*/

public Object removeFirst()

{

if (first == null) { throw new NoSuchElementException(); }

Object element = first.data;

first = first.next;

return element;

}

/**

Adds an element to the front of the linked list.

@param element the element to add

*/

public void addFirst(Object element)

{

Node newNode = new Node();

newNode.data = element;

newNode.next = first;

first = newNode;

}

/*

P16.4 : Returns the size of the linked list

*/

public int size()

{

               int count = 0;

               Node current = first;

               while(current != null)

               {

                              count++;

                              current = current.next;

               }

               return count;    

}

/*

P16.1 : Reverse the linked list by directly rerouting the links

*/

public void reverse()

{

               Node current = first; //set current node to first

               Node prev = null; // prev = null

               Node next = null; // next = null

               // loop that continues till all the links have been changed

               while(current != null)

               {

                              next = current.next; // get the node which next of current

                              current.next = prev; // set next of current to previous node

                              prev = current; // set previous to current

                              current = next; // current will be the previous next of current

               }

               first = prev; // finally set first node to previous last node

}

/**

Returns an iterator for iterating through this list.

@return an iterator for iterating through this list

*/

public ListIterator listIterator()

{

return new LinkedListIterator();

}

class Node

{

public Object data;

public Node next;

}

class LinkedListIterator implements ListIterator

{

private Node position;

private Node previous;

private boolean isAfterNext;

/**

Constructs an iterator that points to the front

of the linked list.

*/

public LinkedListIterator()

{

position = null;

previous = null;

isAfterNext = false;

}

/**

Moves the iterator past the next element.

@return the traversed element

*/

public Object next()

{

if (!hasNext()) { throw new NoSuchElementException(); }

previous = position; // Remember for remove

isAfterNext = true;

if (position == null)

{

position = first;

}

else

{

position = position.next;

}

return position.data;

}

/**

Tests if there is an element after the iterator position.

@return true if there is an element after the iterator position

*/

public boolean hasNext()

{

if (position == null)

{

return first != null;

}

else

{

return position.next != null;

}

}

/**

Adds an element before the iterator position

and moves the iterator past the inserted element.

@param element the element to add

*/

public void add(Object element)

{

if (position == null)

{

addFirst(element);

position = first;

}

else

{

Node newNode = new Node();

newNode.data = element;

newNode.next = position.next;

position.next = newNode;

position = newNode;

}

isAfterNext = false;

}

/**

Removes the last traversed element. This method may

only be called after a call to the next() method.

*/

public void remove()

{

if (!isAfterNext) { throw new IllegalStateException(); }

if (position == first)

{

removeFirst();

}

else

{

previous.next = position.next;

}

position = previous;

isAfterNext = false;

}

/**

Sets the last traversed element to a different value.

@param element the element to set

*/

public void set(Object element)

{

if (!isAfterNext) { throw new IllegalStateException(); }

position.data = element;

}

}

}