CMSC 132 Exam 2 review(A+ Graded)

When implementing a linked list class, the inner class representing the nodes serves as a __________ around a piece of _________ and a reference to another node. correct answers wrapper, data What does an empty linked list look like? correct answers head --- null Use a for loop to traverse through a linked list. correct answers for(NodeT curr = head; curr != null; curr = ){ } What is something important to think about when writing methods for a linked list implementation? correct answers Ask yourself what these methods will do if the linked list is empty. (T/F) It is better to use == over .equals() when comparing data from a linked list. correct answers FALSE. Use the .equals() method Random access (retrieve element at specified index) What will the runtimes be for an array vs linked list? correct answers - Arrays are better, for this example they would have a O(1) runtime. - A linked list would run in O(n) even for the best case. Binary search What will the runtimes be for an array vs linked list? correct answers - Arrays are better, they have fast random access. It would have a runtime of O(log n). - A linked list would be very bad for the binary search algorithm, there is no random access so starting from the middle of the list to search for the element is not an intelligent approach. The runtime would be O(n*log n). Insert at tail What will the runtimes be for an array vs linked list? correct answers - For arrays it would be O(n), unless you did a trick where you multiplied the size of your array by a constant when you want to add something beyond the size of the original array, in that case you could say 'in aggregate the operation could be as fast as O(1). - Linked list is better. If your linked list is maintaining a tail reference and you want to add a number to the end of the list, all you do is wrap it in a node and make tail equal to the node. If this is the case, the runtime is O(1). Insert at head