Underlying array structure

Assignment Help Basic Computer Science

Reference no: EM13968072

1. Ef?ciently implement a stack class using a singly linked list, with no header or tail nodes.

2. Ef?ciently implement a queue class using a singly linked list, with no header or tail nodes.

3. 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.

4. A linked list contains a cycle if, starting from some node p, following a suf?cient number of next links brings us back to node p. p does not have to be the ?rst node in the list. Assume that you are given a linked list that contains N nodes; however, the value of N is unknown.

a. Design an O(N) algorithm to determine if the list contains a cycle. You may use O(N) extra space.

b. Repeat part (a), but use only O(1) extra space. (Hint: Use two iterators that are initially at the start of the list but advance at different speeds.)

Reference no: EM13968072

Questions Cloud

Maintaining the integrity of the linked list : We do not have pointers to any other nodes (except by following links). Describe an O(1) algorithm that logically removes the value stored in such a node from the linked list, maintaining the integrity of the linked list. (Hint: Involve the next n..

Does the company have any preferred stock : What seems to be the main reason for the change in stockholders' equity from the past year to the most recent year?

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.

User Account

All Pages