Java Question: Write a contains method for a linked implementation of a sorted l

Question

Java Question:

Write a contains method for a linked implementation of a sorted list.

This method is written from the implementation perspective, meaning it goes inside of the SortedLinkedList class.

This means you have access to firstNode and numberOfEntries.

For full credit, write an efficient solution. This will involve directly accessing the linked structure rather than only invoking existing methods. You should also take advantage of the knowledge that the list is always sorted.

You can assume T is Comparable.

The method header is: public boolean contains(T anEntry)

Explanation / Answer

Given below is the implementation of contains() method assuming the structure of the list as shown. Here Node class is a nested class, hence there is no need to write Node<T> . If Node is a separate generic class, then it would be written as Node<T>.

public class SortedLinkedList<T extends Comparable<T>> {
class Node
{
T data;
Node next;
}
private Node firstNode;
private int numberOfEntries;
public boolean contains(T anEntry)
{
Node curr = firstNode;

//if no data or we reach an element greater than the one we are looking for, we stop because the list is sorted
while(curr != null && curr.data.compareTo(anEntry) <= 0)
{
if(anEntry.compareTo(curr.data) == 0)
return true;
curr = curr.next;
}
return false;
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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