Write a method for the LinkedList class that inserts int data into the list in a
ID: 3599975 • Letter: W
Question
Write a method for the LinkedList class that inserts int data into the list in ascending order.
Therefore,if we insert the int 7 into the linked list 2 -> 4 - >6 -> 10 -> 20, the linked list should become
headNode ->2 -> 4 - >6 -> 7 -> 10 -> 20 -> endNode
This method is headed by public void OrderInsert(int item)
Then change it so that it handles String data. This method will then have the header public void OrderInsert(String item).
Submit your LinkedList class file for Strings with the String version of OrderInsert and I will test it in a main program.
------------------------------------------------------------
LINKEDLIST.JAVA FILE
public class LinkedList
{
// uses the Node class
private Node headNode; // refers to dummy head node of the linked list-"bookend"
private Node endNode; // refers to dummy end node of the linked list-"bookend"
//Constructor – establishes an empty linked list
public LinkedList()
{
// sets up two linked dummy "bookend" nodes
endNode=new Node("a",null);
headNode=new Node("b",endNode);
}
//Methods - InsertBegin
public void InsertBegin(String item)
{
if(headNode.getLink()==endNode)// if the list is empty
{
Node n = new Node();
n.setDatum(item);
n.setLink(endNode);
headNode.setLink(n);
}
else
{
Node n = new Node();
n.setDatum(item);
n.setLink(headNode.getLink());
headNode.setLink(n);
}
}
public void InsertEnd(String item)
{
if( headNode.getLink()==endNode)// if the list is empty
{
InsertBegin(item);
}
else
{
Node n = endNode;
n.setDatum(item);
endNode= new Node("c",null);
n.setLink(endNode);
}
}
private void DisplayHelper(Node r)
{
if(r.getLink() != endNode)
{
System.out.println(r.getLink().getDatum());
DisplayHelper(r.getLink());
}
}
// Method Display
public void Display()
{
System.out.println("The data in the linked list are:");
Node l = headNode.getLink();
while (l != endNode)
{
System.out.println( l.getDatum());
l = l.getLink();
}
}
private Node FindHelper(String item, Node r)
{
if (r==null) return null;
if ((r.getLink()!=null) &&(r.getLink().getDatum()==item)) return r.getLink();
return FindHelper(item,r.getLink());
}
public Node Find(String item)
{
return FindHelper(item,headNode);
}
public void DeleteFirst()
{
headNode.setLink(headNode.getLink().getLink());
}
public Node Previous(String item)
{
//returns a reference to the node preceding the node that contains item
// if item is in the list
//if item is not in the list, return null
if (item.compareTo(headNode.getLink().getDatum())==0 )
{
return headNode;
}
else
{
Node p = headNode.getLink();
Node q= p.getLink();
while(q.getDatum().compareTo(item) !=0)
{
p=p.getLink();
q=q.getLink();
if(q.getLink()==null) return null;
}
return p;
}
}
}
}
-------------------------------------------
LINKEDLISTMAIN.JAVA FILE
public class LinkedListMain
{
//uses Node class and LinkedList class
public static void main(String[] args)
{
// See Node.java and LinkedList.java
// constructs empty list with dummyheadNode linked to dummy endNode.
LinkedList list1 = new LinkedList();
list1.InsertBegin("tree");
list1.InsertBegin("trunk");
list1.InsertBegin("leaf");
list1.InsertEnd("branch");
list1.InsertEnd("twig");
list1.Display();
//delete the first item in the list
System.out.println("Delete the first.");
list1.DeleteFirst();
//display the list after the first item is delted
System.out.println("The data, after the deletion, in the list are:");
list1.Display();
Node n = list1.Find("branch");
System.out.println("Finds " + n.getDatum());
/*
Node n = list1.Previous("bark");
System.out.println("Previous to bark is "+ n.getDatum());
*/
list1.OrderInsert("moss");
}
}
Explanation / Answer
class LinkedList {
// uses the Node class
private Node headNode; // refers to dummy head node of the linked
// list-"bookend"
private Node endNode; // refers to dummy end node of the linked
// list-"bookend"
// Constructor – establishes an empty linked list
public LinkedList() {
// sets up two linked dummy "bookend" nodes
endNode = new Node("a", null);
headNode = new Node("b", endNode);
}
// Methods - InsertBegin
public void InsertBegin(String item) {
if (headNode.getLink() == endNode)// if the list is empty
{
Node n = new Node();
n.setDatum(item);
n.setLink(endNode);
headNode.setLink(n);
} else {
Node n = new Node();
n.setDatum(item);
n.setLink(headNode.getLink());
headNode.setLink(n);
}
}
public void InsertEnd(String item) {
if (headNode.getLink() == endNode)// if the list is empty
{
InsertBegin(item);
} else {
Node n = endNode;
n.setDatum(item);
endNode = new Node("c", null);
n.setLink(endNode);
}
}
private void DisplayHelper(Node r) {
if (r.getLink() != endNode) {
System.out.println(r.getLink().getDatum());
DisplayHelper(r.getLink());
}
}
// Method Display
public void Display() {
System.out.println("The data in the linked list are:");
Node l = headNode.getLink();
while (l != endNode) {
System.out.println(l.getDatum());
l = l.getLink();
}
}
private Node FindHelper(String item, Node r) {
if (r == null)
return null;
if ((r.getLink() != null) && (r.getLink().getDatum() == item))
return r.getLink();
return FindHelper(item, r.getLink());
}
public Node Find(String item) {
return FindHelper(item, headNode);
}
public void DeleteFirst() {
headNode.setLink(headNode.getLink().getLink());
}
public Node Previous(String item) {
// returns a reference to the node preceding the node that contains item
// if item is in the list
// if item is not in the list, return null
if (item.compareTo(headNode.getLink().getDatum()) == 0) {
return headNode;
} else {
Node p = headNode.getLink();
Node q = p.getLink();
while (q.getDatum().compareTo(item) != 0) {
p = p.getLink();
q = q.getLink();
if (q.getLink() == null)
return null;
}
return p;
}
}
public void OrderInsert(String item) {
if (item.compareTo(headNode.getLink().getDatum()) == 0) {
Node n = new Node();
n.setDatum(item);
n.setLink(headNode.getLink());
headNode.setLink(n);
}else if(item.compareTo(headNode.getLink().getDatum()) < 0){
Node n = new Node();
n.setDatum(item);
n.setLink(headNode.getLink());
headNode.setLink(n);
}else {
Node p = headNode.getLink();
Node q = p;
while (p.getDatum().compareTo(item) <= 0 && p!=endNode) {
q=p;
p = p.getLink();
}
if(p==endNode){
Node n = new Node();
n.setDatum(item);
n.setLink(endNode);
q.setLink(n);
}else{
Node n = new Node();
n.setDatum(item);
n.setLink(p);
q.setLink(n);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.