Question

Write a method max() which take a generic singly linked list as an argument and returns the maximum element reference in the list.

     If the list is empty, please throw an empty collection exception.

     The method prototype is defined as follows.

Please write down your code in the method body enclosed in braces:

public static <T extends Comparable<T>> T max(SingleLinkedList<T> list) throws EmptyCollectionException {

}

2) What is the big O notation of the max method?

a) O(N)

b) O(1)

c) O(N log N)

d) O(log N)

e) O(N2)

3) If we have to sort the list, which algorithm could you use? Briefly write the pseudo code of a sort algorithm.

Thanks.

Answer 1

Given a single linked list of n nodes and find the smallest and largest element in linked list

java code for it-

class RONALDO

{

static class Node

{

int data;

Node next;

}

static Node head=null;

static int largestElement(Node head)

{

Int max=Integer.MIN_VALUE;

while(head!=null)

{

if(max<head.data)

max=head.data;

head=head.next;

}

return max;

}

static int smallestElement(Node head)

{

int min=Integer.MAX_VALUE;

while(head!=null)

{

if(min>head.data)

min=head.data;

head=head.next;

}

return min;

}

static void push(int data)

{

Node newNode=new Node();

newNode.data= data;

newNode.next=(head);

(head)=newNode;

}

static void printList(Node head)

{

while(head!=null)

{

System.out.println(head.data + " -> ");

head=head.next;

}

System.out.println("NULL");

}

public static void main(String[] args)

push(15);

push(14);

push(13);

push(22);

push(17);

System.out.println("Linked list is : ");

printList(head);

System.out.println("Maximum element in linked list: ");

System.out.println(largestelement(head));

System.out.print("Maximum element in Linked List: " );

System.out.print(smallestElement(head));

}

}

2-O(N2)

3- class BUBBLESORT

{

void bubblesort(int arr[])

{

int n=arr.length;

for(int i=0; i<n-1;i++)

for(int j=0;j< n-i-1;j++)

if(arr[j] >arr[j+1])

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

void printArray(int arr[])

{

int n=arr.length;

for(int i=0;i<n;++i)

System.out.print(arr[i] + " ");

System.out.print();

}

public static void main(String args[])

{

BubbleSort ob= new BuubleSort();

int arr[]={12,56,32,14,56,43,63};

ob.bubbleSort(arr);

System.out.println("Sorted array"):

ob.printArray(arr);

}

}

Hey!! i wrote each part answer in detail,kindly c it properly ,if any query then dm me and kindly uprate my ratings as it is the most important thing for me at the moment..