Homework Soursefinish the java programming Begin by creating an implementat
finish the java programming
Begin by creating an implementation of the Linked List ADT. Your implementation should
be contained in a file named MyLinkedList.java (thus you are implementing a class
called MyLinkedList). Include your Node implementation in the same file. The API (i.e.
the public methods) of your Linked List class are specified below – do not implement any
more public methods than the ones shown. Your data structures must be written to store any
kind of object. In other words, use a reference of type Object to store data in the nodes of
your list. You are free to re-use and adapt any code found in the Course notes.
public MyLinkedList()- Provide a default constructor that initializes an empty
Linked List, with a size of 0.
void insert(Object theItem)- Insert a new item at the front of the list.
Duplicate items are permitted.
Object delete(Object theItem)- Delete the first instance of a given item, if
it exists in the list. Use the equals method of the Object class to compare two
Objects. Return a reference to the deleted item, or null if it was not found.
int getSize()- Return the number of items in the list. In order to implement this
efficiently, you should keep a private instance variable that maintains a count of the
number of items in the list.
Object initTraversal()- Initialize a private instance variable to point to the
first Node in the list (or null if the list is empty). Return the item in the first Node (if
the list is not empty) or else return null.
Object traverse()- Advance the instance variable from initTraversal to the next
node in the list (if it exists) or else set it to null if the end of the list has been reached.
Return the item pointed to (if the traversal variable is not null) or else return null.
MyLinkedList reverse()- Return a new MyLinkedList object which contains
the same items but in reverse order. This method should create a new empty list, and
then must call a private, recursive method named addRecursively(...) to add
elements to this new list. In other words, your reverse() method will call
addRecursively(...) and then addRecursively(...) will call itself a
sufficient number of times to correctly fill the new list. The parameters of the recursive
method are given as (…) to indicate that the list of parameters is up to you. The return
value, if any, is also for you to choose.
String toString()- Return a String representation of the list. Separate each
item with an underscore “_”, and enclose the items in braces, e.g. {anItem_78_5.9_z}.
This public method must call a private, recursive method named
toStringItem(...) to generate the hyphen-separated list of items (you may add
the braces in the public method though). As was the case for reverse(), the choice of
parameters and return type, if any, are up to you.
Create a new class named MyCharacterListTools that provides the API shown below.
This class does not need a constructor nor will any user-defined constructor be called by the
provided code in MainClassQ1.java.
MyLinkedList createCharacterList(String str) – This method is to
return a MyLinkedList whose data items are the characters of str. All of the
characters must appear in the list and in the same order as they are given in str.
void removeNonLetters(MyLinkedList list) – This method is to remove
from the list any spaces, numbers and punctuation characters (this is to be done inplace).
Letters of the alphabet are to be left in the list in the same order they were given.
For example, if the list contained {H_e_l_l_o_ _W_o_r_l_d_!} then after calling this
function, the list would hold {H_e_l_l_o_W_o_r_l_d}. You may use the built-in Java
static method Character.isLetter(char ch) to test whether the list items are
letters.
boolean testEquality(MyLinkedList l1, MyLinkedList l2) – This
method is to compare two MyLinkedLists for equality. Two lists are considered
equal if their contents are the same and in the same order. Letter case should not be
observed (i.e. \'A\' is equal to \'a\', \'B\' is equal to \'b\', etc...). If the two lists are equal then
return true. Return false otherwise. The static built-in Java methods
Character.toLowerCase(char ch) and Character.toUpperCase(char
ch) may be used in this method.
Solution
Answer:
class MyLinkedList
{
@Override
public String toString()
{
String s = null;
s = this.toStringItem(this.strt, s);
return \"MyLL [start = \" + strt + \", end = \" + end + \", size = \" + sz + \"]\";
}
private String toStringItem(Node curNode, String op)
{
if(curNode != this.end)
{
if(op != null)
{
op = op + curNode.gtDta() + \"_\";
}
else
{
op = curNode.gtDta()+\"_\";
}
op = this.toStringItem(curNode.getLnk(), op);
} else {
op = op + curNode.gtDta();
}
return op;
}
class Node
{
protected Object dta;
protected Node lnk;
public Node()
{
lnk = null;
dta = 0;
}
public Node(Object d,Node n)
{
dta = d;
lnk = n;
}
public void setLnk(Node n)
{
lnk = n;
}
public void setData(Object d)
{
dta = d;
}
public Node getLnk()
{
return lnk;
}
public Object gtDta()
{
return dta;
}
}
protected Node strt;
protected Node end ;
public int sz ;
public MyLinkedList()
{
strt = null;
end = null;
sz = 0;
}
public boolean isEmp()
{
return strt == null;
}
public int getSz()
{
return sz;
}
public void insert(Object val)
{
Node nptr = new Node(val, null);
sz++ ;
if(strt == null)
{
strt = nptr;
end = strt;
}
else
{
nptr.setLnk(strt);
strt = nptr;
}
}
public Node initTraversal()
{
Node node = null;
if(sz > 0)
{
node = strt;
}
return node;
}
public Node traverse(Node node)
{
Node nextNode = null;
if(node.getLnk() != null)
{
nextNode = node.getLnk();
}
return nextNode;
}
public MyLinkedList reverse()
{
MyLinkedList rvrsLst = new MyLinkedList();
rvrsLst = this.addRecursively(this.strt, rvrsLst);
return rvrsLst;
}
private MyLinkedList addRecursively(Node curNode, MyLinkedList rvrsLst)
{
if(curNode != this.end)
{
this.addRecursively(curNode.getLnk(), rvrsLst);
}
rvrsLst.insert(curNode.gtDta());
return rvrsLst;
}
public Node delete(Object theItem)
{
Node curNode = strt;
Node deletedNode = null;
if(strt.getLnk() != null)
{
while(!curNode.gtDta().equals(theItem))
{
curNode = curNode.getLnk();
}
}
if(curNode.gtDta().equals(theItem))
{
if(curNode.getLnk() != null)
{
Node tmp = curNode.getLnk();
deletedNode = tmp;
tmp = tmp.getLnk();
curNode = tmp;
sz--;
}
}
return deletedNode;
}
public void disp()
{
System.out.print(\"\ Singly LL = \");
if (sz == 0)
{
System.out.print(\"empty\ \");
return;
}
if (strt.getLnk() == null)
{
System.out.println(strt.gtDta() );
return;
}
Node ptr = strt;
System.out.print(strt.gtDta()+ \"->\");
ptr = strt.getLnk();
while (ptr.getLnk() != null)
{
System.out.print(ptr.gtDta()+ \"->\");
ptr = ptr.getLnk();
}
System.out.print(ptr.gtDta()+ \"\ \");
}
}
