The following Java implementation of a class Node is given: data = d; next = n;
ID: 3791008 • Letter: T
Question
The following Java implementation of a class Node is given:
data = d;
next = n; }
Object data;
Node next; }
Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a reference to the header node.
Using the class Node described above, write a MySingleLinkedList class in Java includes methods to:
(a) int size() - return the size of the linked list.
(b) void print() - print the linked list.
(c) boolean contains(Object x) - test if a value x is contained in the linked list.
(d) boolean add(Object x) - add a value x if it is not already contained in the linked list.
(e) boolean remove(Object x) - remove a value x if it is contained in the linked list.
Explanation / Answer
public class MySingleLinkedList
{
Node head = null;
int listSize = 0;
public MySingleLinkedList() {
}
boolean contain(Object x)
{
Node temp = head;
/*
if (x instanceof Node)
x = (Node) x;
else
return false;
*/
while((temp != null) && (!x.equals(temp.data)))
{
temp = temp.next;
}
if ((temp != null) && (x.equals(temp.data)))
{
return true;
}
return false;
}
boolean add(Object x)
{
if (! contain(x))
{
//if (x instanceof Node)
//{
// x = (Node)x;
Node temp = new Node();
temp.data = x;
temp.next = head;
head = temp;
listSize++;
return true;
//}
}
return false;
}
int size()
{
return listSize;
}
boolean remove(Object x)
{
Node temp = head;
Node prev = null;
while((temp != null) && (!x.equals(temp.data)))
{
prev = temp;
temp = temp.next;
}
if ((temp != null) && (x.equals(temp.data)))
{
prev.next = temp.next;
temp = null;
return true;
}
return false;
}
void print()
{
Node temp = head;
while(temp!=null)
{
System.out.println(temp.data.toString());
temp = temp.next;
}
}
public static void main(String[] args)
{
MySingleLinkedList list = new MySingleLinkedList();
Integer n = new Integer(10);
list.add(n);
Integer n2 = new Integer(20);
Integer n3 = new Integer(30);
list.add(n2);
list.add(n3);
System.out.println("List after few insertions");
list.print();
if (list.contain(n2))
{
System.out.println("Found");
if (list.remove(n2))
{
System.out.println("Removed");
}
}
System.out.println("List after removal");
list.print();
}
}
/*
Sample run
List after few insertions
30
20
10
Found
Removed
List after removal
30
10
*/