Question

Improve class OurLinkedList, so that its users can readily access a list's middle node. Readily here means that when users instantiate an OurLinkedList object, they can access the node in the middle of the list without starting from the head, counting how many nodes to the end, then going back to the head, and skipping half as many nodes forward. In fact, there should be no counting for this improvement. Notice that lists with an even number of nodes, do not have a well defined middle node and it is up to you to determine which node near the middle will be considered the middle one.

Your improvement must be delivered only in the form of a new class that extends OurLinkedList. Name the extending class, after yourself, as following:

class YourfirstnameLinkedList extends OurLinkedList { ... }

replacing Yourfirstname above, with your actual first name (e.g., MyLinkedList).

SOURCE CODE FOR QUESTION

public class OurLinkedList {

class Node {
  
String value;
Node next;
  
Node(String v) {
value = v;
next = null;
} // constructor Node
} // class Node

/**
* Accessor for the field size.
* @return number of nodes in the list.
*/
public int getSize() {
return size;
} // method getSize

  
public boolean nodeExists(String v) {
// Initial assumption: no node found with string v
boolean stringFound = false;
// Start from the beginning.
Node currentNode = head;
if ( currentNode == null) {
// Empty list.
stringFound = false;
} else {
// List is not empty. Let's check if the last node contains
// string we are looking for. We do this here, because the
// last node is unreachable in a loop that terminates when
// .next == null.
stringFound = tail.value == v;
// Search through the rest of the linked list, hopping from
// node to node, following the .next pointer.
while (currentNode.next != null) {
if ( currentNode.value == v) {
stringFound = true;
}
currentNode = currentNode.next;
}
}
return stringFound;
} // method nodeExists

public void addNode(String v) {
if (!nodeExists(v)) {
// The list does not contain a node with the given string.
// Let's create one and call it newNode.
Node newNode = new Node(v);
// We are adding this newNode to the list, so let's increase the size.
size++;
// Now we need to determine where to add this new node.
if (head == null) {
// List is empty. Make this newNode the list's head.
head = new Node(v);
// Because the list is empty, make this node its tail as well.
tail = head;
} else {
// The list is not empty. Find its tail node and add the
// newNode after it.
tail.next = newNode;
// Make the newNode, the list's new tail.
tail = newNode;
}
}
}

public boolean remove(String v) {
boolean success = false;
if (nodeExists(v)) {
success = true;
}
return success;
}

class MyLinkedList extends OurLinked {...}

public static void main(String[] args) {
OurLinkedList demo = new OurLinkedList();
}

}

The question wants us to find the middle of the list immediately without traversing the linked list conventionally but any help is great. There is no need to print the list just to know where the middle of the list is.

Answer 1

1. The improved code in MyLinkedList class uses the single pointer mid which moves forward only when the counter variable is odd.
2. This ensures mid moves half the nodes only from the entire list.
3. There is no getting the size and traversing the list until size/2 elements.
4. Proper null checks are done to avoid null pointer exception.

public class OurLinkedList {

class Node {

String value;
Node next;

Node(String v) {
value = v;
next = null;
} // constructor Node
} // class Node

/**
* Accessor for the field size.
* @return number of nodes in the list.
*/
public int getSize() {
return size;
} // method getSize

public boolean nodeExists(String v) {
// Initial assumption: no node found with string v
boolean stringFound = false;
// Start from the beginning.
Node currentNode = head;
if (currentNode == null) {
// Empty list.
stringFound = false;
} else {
// List is not empty. Let's check if the last node contains
// string we are looking for. We do this here, because the
// last node is unreachable in a loop that terminates when
// .next == null.
stringFound = tail.value == v;
// Search through the rest of the linked list, hopping from
// node to node, following the .next pointer.
while (currentNode.next != null) {
if (currentNode.value == v) {
stringFound = true;
}
currentNode = currentNode.next;
}
}
return stringFound;
} // method nodeExists

public void addNode(String v) {
if (!nodeExists(v)) {
// The list does not contain a node with the given string.
// Let's create one and call it newNode.
Node newNode = new Node(v);
// We are adding this newNode to the list, so let's increase the size.
size++;
// Now we need to determine where to add this new node.
if (head == null) {
// List is empty. Make this newNode the list's head.
head = new Node(v);
// Because the list is empty, make this node its tail as well.
tail = head;
} else {
// The list is not empty. Find its tail node and add the
// newNode after it.
tail.next = newNode;
// Make the newNode, the list's new tail.
tail = newNode;
}
}
}

public boolean remove(String v) {
boolean success = false;
if (nodeExists(v)) {
success = true;
}
return success;
}
  
   //My code here
  
   class MyLinkedList extends OurLinked {
       public Node middleElement(Node node){
           //if empty list is provided then return null and not proceed with any of the computation
           //Here we are using the concept to find the middle element only when c is odd
           // So that mid moves only half the distance automatically without actually calculating the length of the list
           if(node!=null){
               Node mid= node;
               int c=0;
               while(node!=null){
                   if(c%2!=0) // mid moves only when the counter is odd , ensuring it moves the half of current list
                       mid=mid.next;
                   ++c;
                   node=node.next;
               }
           return mid;
           }
           //return node only if it is empty list and the null check is done in the driver method
           return node;
       }
   }

   @driver method
   public static void main(String[] args) {
       OurLinkedList demo = new OurLinkedList();
       Node mid= demo.middleElement(head);
       if(mid!=null)
           System.out.println(mid.data);
      
   }

}