2. This question requires that you implement methods for a class that represents

Question

2. This question requires that you implement methods for a class that represents a size field. You list. In this some are used. However, there is no that may question, both a header and nested class Node. You may assume the list assume an appropriate d should not does not store null values. You should only be following links; your solutions create or use any iterator classes. (a) Below you will implement addBefore, removeNode, and size. Before writing the code, give the running ilme for each method. size is o(N) the other two are o(1). (b) Implement removeNode below. public void removeNode( Node p p next prev previ p prev next p next; (c) Implement addBefore. This method adds x prior to Node p. public void addBefore( Node p, Any Type x) Node new Node new Node(x, p.prev, p); p prev next newNode; p prev newNode; (d) Implement size. Note that the size information is not directly stored; you have to compute it. public int size y int count 0; next for( Node

Explanation / Answer

b)

public void removeNode (Node p)       //this is doubly linked list implementation of removing a node.
{
// say for example i have doubly liked list like <- 1 <-> 2 <-> 3 -> , now we gonna remove 2 and our node 'p' is 2.  
   p.next.prev = p.prev;       // p.next.prev (prev pointer of 3) = p.prev (node 1)... which means <- 1 <- 3 -> //so prev of 3 is 1 now
   p.prev.next = p.next       // p.prev.next (next pointer of 1) = p.next (node 3)... which means <-1 <->3 -> thats how we remove node 2.
}

public void addBefore (Node p, AnyType x)   //we gonna add one new node at the beginning of doubly linked list
{
//suppose if we have list like <-2 <-> 3 ->, now we gonna add a new node '1' at the beginning
   Node newNode = new Node(x, p.prev, p);   // creating a new node of 1 will be done here
   p.prev.next = newNode;       // p.prev.next = newNode, that means newNode of next will be p (1->2)
   p.prev = newNode       // p.prev (2 of prev pointer ) = newNode .... 1 <-> 2.. thats how we add node at beginning
}

public int size()   //this function is to find the number of nodes in doubly linked list, since function is 'int' we need to return some value
{
   int count = 0;   //initializing one int variable and its value is 0
//take example, for(i=0;i<3;i++) ----> this loop will work 3 times, now below is the same implementation with linked list
   for(Node<AnyType>p = header.next; p != tail ; p = p.next)   // p = header.next -> will begin with 1st node ; till it reaches the tail ; increment hapens here
       count++;   //if linked list contains 3 elements, then loop will be happen 3 times and count becomes 3
   return count;   //returning count value to the function call

//Alternative solution
  
   int count = 0;
   Node<AnyType> tmp = header;   //now tmp holds the 1st node
   while(tmp.next!=null)       //this loop will executes till it reaches the end of the list
   {
       count++;       //count will increments here
       tmp = tmp.next       // tmp will moves to the next node
   }
   return count;
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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