The caterpillar data structure looks like the following picture: Each body node

Question

The caterpillar data structure looks like the following picture: Each body node is connected to two leg nodes, as shown in the picture: Each body node is connected to its predecessor and successor body nodes through double links. Each body node and each leg node can store an integer item. You can assume a WindowLinked class and an object w of this class. w. link indicates the position of a window on a body node (in other words, w. link is a reference to a body node). (a) Write two class definitions ListBody and ListLeg for implementing the caterpillar data structure. Write a method connectLegToBody (ListBody b, ListLeg 1) for connecting an object of class List Body to an object of class ListLeg. (b) Write a method DeleteBefore (Window Linked w) to delete the node that is to the left of the node that the window is on (in other words, the List Body node and its two legs to the left of the current window position are to be deleted). Write a method Search (int i) that searches for an integer i in a caterpillar. Recall that both the body and leg nodes can store an integer. You can assume any other method that you might require, but please explain clearly what the method does.

Explanation / Answer

ListBody.java

public class ListBody
{
   int data;
   ListLeg upLeg,downLeg;
   ListBody predecessor,successor;
}

ListLeg.java

public class ListLeg
{
   int data;
   public ListLeg(int data)
   {
       this.data = data;
   }
}

WindowLinked.java

public class WindowLinked
{
   ListBody link;//reference to a ListBody in caterpiller data structure.
   public void connectLegToBody(ListBody b,ListLeg l)
   {
       //Each ListBody has 2 legs. one is upLeg and other is downLeg.
       //formal parameter b has 2 legs.
       //I am doing like, if b's upLeg is null, then formal parameter l is assigned to upLeg otherwise assigned to downLeg.
       if(b.upLeg==null)
       b.upLeg = l;
       else
       b.downLeg = l;
   }
   public void deleteBefore(WindowLinked w)
   {
       //this method deletes successor body node of w.link
       if(w.link.successor!=null)
       {
           ListBody lb = w.link.successor;
           lb.predecessor = null;
           w.link.successor = null;
       }
   }
   public void search(int i)
   {
       //this method searches for i in data structure starting from link(ListBody object).
       while(link.successor!=null)//finds starting of data structure.
       link = link.successor;
       while(link!=null)
       {
           if(link.data==i)
           {
               System.out.println("Found at Body!!");
               break;
           }
           else if(link.upLeg!=null && link.upLeg.data==i)
           {
               System.out.println("Found at Up Leg!!");
               break;
           }
           else if(link.downLeg!=null && link.downLeg.data==i)
           {
               System.out.println("Found at Down Leg!!");
               break;
           }
           else
           link = link.predecessor;
       }
   }
}

Thankyou!!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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