Implementation of self-adjusting lists

Assignment Help Basic Computer Science

Reference no: EM13968070

1. Write an algorithm for printing a singly linked list in reverse, using only constant extra space. This instruction implies that you cannot use recursion but you may assume that your algorithm is a list member function. Can such an algorithm be written if the routine is a constant member function?

2. a. Write an array implementation of self-adjusting lists. In a self-adjusting list, all insertions are performed at the front. A self-adjusting list adds a find operation, and when an element is accessed by a find, it is moved to the front of the list without changing the relative order of the other items.

b. Write a linked list implementation of self-adjusting lists.

c. Suppose each element has a ?xed probability, pi, of being accessed. Show that the elements with highest access probability are expected to be close to the front.

Reference no: EM13968070

Questions Cloud

Problem regarding the circular linked list : One way to implement a queue is to use a circular linked list. In a circular linked list, the last node's next pointer points at the ?rst node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding..

How much work is required to stretch : The idea is that you exercise your muscles by stretching the spring from its natural length, which is 34 cm. If a 140 Newton force is required to keep the spring stretched to a length of 51 cm, how much work is required to stretch it from 52 cm to..

Underlying array structure : Ef?ciently implement a queue class using a circular array. You may use a vector (rather than a primitive array) as the underlying array structure.

Provide details on policy processes that were not utilized : Provide details on the other policy processes that were not utilized in your research. How could they be applied? Why would they be applicable?

Implementation of self-adjusting lists : Write a linked list implementation of self-adjusting lists. Suppose each element has a ?xed probability, pi, of being accessed. Show that the elements with highest access probability are expected to be close to the front.

Program to evaluate a post?x expression : 1. Write a program to evaluate a post?x expression. 2. a. Write a program to convert an in?x expression that includes (, ), +, -, *, and / to post?x.

Application of operator : Looking ahead in an STL iterator requires an application of operator++, which in turn advances the iterator. In some cases looking at the next item in the list, without advancing to it, may be preferable.

Describe the various shipping boxes : Describe the various shipping boxes available to the customer as listed above and then create a second table that lists the US Postal Service Hat Rate boxes and their shipping costs

Find out the running time of program : What is the running time of your program? If M = 1, what is the running time of your program? How is the actual speed affected by the delete routine for large values of N (N > 100,000)?

User Account

All Pages