1.(10 points) Explain why the “get” method is more efficient for an array based list than it is for a linked list
2.Explain the advantages and disadvantages of using a doubly linked list over a singly linked list(5 points)
- Handout G is the specification of a generic doubly linked list . Implement a new instance method addAtHead, which given a new value of type “S” adds it at the beginning of the list. (10 points)
- For a list, normally the find method ( public int find( S value) ) starts at index 0 and iterates through all of the elements in the list comparing each element to “value” until either it finds an element containing a value and returns the index of that element or reaches the end of the list without finding “value”. For the SortedArraybasedList in handout H, can we make it any more efficient? If so HOW…(10 points)
5.Consider the specification of the methods available for a Singly linked list given in (Handout B). You wish to add a new instance method to the class called “countOccurrences” which counts the number of times a specific value occurs in a list and return it. The methods specification should be: (10 points)
public int countOccurrences( S value)
6.What is an inner class, in the definition of an inner class what does the keyword static mean in the definition of the node class? (As seen in handout B)
7.Assuming the specification for a Stack given in Handout C. Write a client method called replace that given two integer values, replaces every instance of oldValue in the stack with newValue. The method should have the specification: ( 10 points)
public static void replace( Stack S, int old, int new)
8.(10 points) For the operations defined for a doubly linked list in handout G, write a instance method called equals which determines if two Lists are “equal”. This means that the two lists contain the same # of elements in the same order. At the end of the method the contents of the two lists should NOT be destroyed. This method would be added INTO the doubly linked list class. [Hint: the two lists participating in the method are “other” and “this”]
public boolean equals( dLinkedList other)
9.(10points) To the implementation of a linked queue in Handout J, add a new instance method called “splice” which given another queue as a parameter concatenates all of the elements of the second queue to the end of the first queue. While leaving the second queue unaltered. (this should make a deep copy of the second queue)
public void splice( Queue otherQueue) 10.(10 points) Using the array based list in Handout A, add an CLIENT method called rotate which given the list and an integer “count” as parameters, moves those number of elements from the front of the list to the end. IF the number specified is greater than the size of the list throw an exception. 11.( Consider the language L = { An$Bn where n=> 1 }
strings in this language consists of a series of A’s followed by a ‘$’, followed by a series of B’s, where the number of A’s and B’s are the same
Samples of valid strings are: A$B AA$BB AAA$BBB
Invalid strings are: A$ $B AA$B A$BB… Explain in code or pseudo code how a stack count be used to evaluate if a string is in this language. Explain in code or pseudo code how a stack count be used to evaluate if a string is in this language. Assuming that there exists a circular array based queue “Q” instantiated for integers, the queue can hold a maximum of 5 values. Show the contents of the queue, & the locations of front and rear, as well as currentSize after the following operations. (5 points)
Sample Solution