finish the java programming Begin by creating an implementation of the Linked Li

Question

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.

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.

Explanation / Answer

Code:

package linkedlist;

class MyLinkedList
{
   @Override
   public String toString() {
       String str = null;
       str = this.toStringItem(this.start, str);
       return "MyLinkedList [start=" + start + ", end=" + end + ", size=" + size + "]";
   }
   private String toStringItem(Node currentNode, String output) {
       if(currentNode != this.end) {
           if(output != null) {
               output = output + currentNode.getData()+"_";
           } else {
               output = currentNode.getData()+"_";
           }
           output = this.toStringItem(currentNode.getLink(), output);
       } else {
           output = output + currentNode.getData();
       }
       return output;
   }
   class Node {
       protected Object data;
   protected Node link;
     
   /* Constructor */
   public Node()
   {
   link = null;
   data = 0;
   }
   /* Constructor */
   public Node(Object d,Node n)
   {
   data = d;
   link = n;
   }
   /* Function to set link to next Node */
   public void setLink(Node n)
   {
   link = n;
   }
   /* Function to set data to current Node */
   public void setData(Object d)
   {
   data = d;
   }
   /* Function to get link to next node */
   public Node getLink()
   {
   return link;
   }
   /* Function to get data from current Node */
   public Object getData()
   {
   return data;
   }
   }
protected Node start;
protected Node end ;
public int size ;

/* Constructor */
public MyLinkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insert(Object val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
  
public Node initTraversal() {
   Node node = null;
   if(size > 0) {
       node = start;
   }
   return node;
}
  
public Node traverse(Node node) {
   Node nextNode = null;
   if(node.getLink() != null) {
       nextNode = node.getLink();
   }
   return nextNode;
}
  
public MyLinkedList reverse() {
   MyLinkedList reverseList = new MyLinkedList();
   reverseList = this.addRecursively(this.start, reverseList);
       return reverseList;
}
  
private MyLinkedList addRecursively(Node currentNode, MyLinkedList reverseList) {
       if(currentNode != this.end) {
           this.addRecursively(currentNode.getLink(), reverseList);
       }
       reverseList.insert(currentNode.getData());
       return reverseList;
   }
   /* Function to delete an element at start */
public Node delete(Object theItem) {
   Node currentNode = start;
   Node deletedNode = null;
   if(start.getLink() != null) {
       while(!currentNode.getData().equals(theItem)) {
       currentNode = currentNode.getLink();
   }
   }
   if(currentNode.getData().equals(theItem)) {
       if(currentNode.getLink() != null) {
           Node temp = currentNode.getLink();
           deletedNode = temp;
           temp = temp.getLink();
           currentNode = temp;
           size--;
       }
   }
       return deletedNode;
}
/* Function to display elements */
public void display()
{
System.out.print(" Singly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.