Problem 1 In the LinkedListADT our count operation loops n times so its time complexity is O(n). How could you change the linked list implementation to make the operation constant O(1)?

Problem 2 Analyze the time and space complexity of the below algorithm // Clone the list starting from a node with the given key LinkedList clone(LinkedList list, int data) tNode = list.head allocate new empty LinkedList nlist while (tNode != null/None AND tNode.data != data) tNode = tNode.next while (tNode != null/None) nlist.addTail(tNode.data) tNode = tNode.next return nlist; Problem 3 Analyze the time and space complexity of the below algorithm. Assume Linked list count has time complexity O(n) // determine if palindrome // throw exception if empty list boolean palindrome(LinkedList list) lsize = list.count() if (list == null/None OR lsize == 0) throw exception declare StackADT s // assume no space allocated middle = (lsize+1)/2 tlist = list.head loop from 1 to middle-1 s.push(tlist.data) tlist = tlist.next if (lsize%2 == 0) // even list

Linked List ADT Given Node class, below is an example of implementation for some linked list operations... class Node data-type data Node next Node(data-type val) data = val next = null/None // implement get and set methods for data and next class LinkedList Node head Node tail LinkedList() Assign null/None to head and tail addHead(data-type val) Node n = Node(val) if (head == null/None) // no elements head = n tail = n else // have elements set n.next to head head =n addTail(data-type val) Node n = Node(val) if (head == null/None) // no elements head = n tail = n else // have elements set tail.next to n tail =n data-type deleteTail() Node n = tail if (head == null/None) // no elements throw exception if (head == tail) // one element head = null/None

tail = null/None else Node cur = head Loop until cur.getNext() == tail // find next to last element tail = cur set tail.next to null/None return n.getData data-type deleteHead() Node n = head if (head == null/None) // no elements throw exception if (head == tail) // one element head = null/None tail = null/None else set head to head.next return n.getData int count() int size = 0 Node n=head Loop until n==null Set n to n.next Increment size by 1 return size Node getHead() return head Node getTail() return tail