Here are the class definitions of Node and List that implement a linked list.

class Node {

private Node next;

private int key;

Node(Node nxt, int keyValue); // constructor

Node getNext();

int getKey();

void putNext(Node nxt);

}

class List { // assume the class does not use a dummy Node

private Node head;

List(); // constructor

boolean exists(int ky); // returns true if ky is in the list

void insertAtHead(int ky); // inserts at the beginning of the list

void insertAtTail(int ky); // inserts at the end of the list

int removeFromHead(); // Returns -1 if the list is empty

void delete(int ky); // delete the element or do nothing if ky doesnt exist

int removeSmallest(); // removes the Node containing the smallest key

// and returns that key. Returns -1 if the list is empty.

// Could be duplicate entries, so remove the first

int removeLargest(); // removes the Node containing the largest key

// and returns that key. Returns -1 if the list is empty.

// Could be duplicate entries, so remove the first

int maxElement(); // calls the private version, doesnt delete the Node

int sum(); // calls the private version

int length(); // calls the private version

private int maxElement(Node x);

private int sum(Node x);

private int length(Node x);

}

**A linked list as defined above holds N nodes. What is the runtime in Big O notation of an algorithm

that searches the list for a given key when:

(a) The list elements are arbitrarily ordered

(b) The list elements are arranged in increasing order