CODEWITHSUNDEEP
algorithmperformancelistdata-structuressequence
dominosam
dominosam

Reputation: 7

Self-organising sequence of numbers with big amount of operations on it - best data structure

I need help with choosing right data structure to my exercise.

For input I have been given number of operations that should be executed(t) and after that indexed sequence of natural numbers seperated with a space. So for example:

3 1 2 3

This means that there will be 3 operations executed on sequence {1,2,3}.

There is also defined a pointer, which shows current position. Operations on that sequence that I should implement are:

My job is to find ending sequence after performing operations R and X t times so that if its element is even then do the R, else do the X. At the start PTR shows first element(if exists) and it should be all in cycle.

For given example at the start of post the output should be:

0 0 3 1

I know that it might sound confusing, so let me show you how this should work step by step.

t = 1

Starting sequence: 1 2 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 2 3

Ending position: PTR -> 0

t = 2

Starting sequence: 1 0 2 3

Actual position: PTR -> 0

Operation: R, c=2

Ending sequence: 1 0 3

Ending position: PTR -> 1

t = 3

Starting sequence: 1 0 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 0 3

Ending position: PTR -> 0

The solution is a sequence from PTR in right direction. So output should be: 0 0 3 1

As for circumscriptions:

I have created my algorithm, which is based on circular linked list. Works, but it's too slow for some tests. I'd be more than grateful if someone could help me in finding the best data structure.

I've got also a hint from my teacher that I should use binary list, but to be honest I didn't find anything about this structure on the internet! Maybe also someone knows this thing and show me where can I search for information about it? I'd apreciate any help.

Upvotes: 0

Views: 92

Answers (3)

Andriy Berestovskyy
Andriy Berestovskyy

Reputation: 8544

R -> removing element c on index PTR+1 and moving PTR forward c times

Looks like a single-linked list: PTR points to a list element, we need to remove the next element and advance PTR pointer c times.

X -> inserting right after element c, which is on index PTR (so inserting on PTR+1), element with value of c-1 and of course moving PTR forward c times.

Also looks like a single-linked list. PTR points to a list element, we insert next element with value c-1 and advance PTR pointer c times.

@dominosam The answer you marked as correct is wrong in fact. There is no need to traverse back the list, so all you need is a circular single-linked list like described, for example, on Wikipedia.

Upvotes: 0

Doug Currie
Doug Currie

Reputation: 41200

Use a circular doubly linked list. It has O(1) insert and remove. (Perhaps this is what your instructor meant by "binary list.")

Fun fact: you can reduce the memory utilization of a doubly linked list with an XOR trick with code here. Lower memory utilization will mean better speed for large lists due to better cache behavior. There's also a SO Q&A on XOR linked lists, which itemizes some of its drawbacks.

Upvotes: 1

Prune
Prune

Reputation: 77850

The data structure depends very much on those available in your chosen implementation language. In most, simply use an array, and adjust the index with the modulus operator. That will give you the needed circularity.

This assumes that your chosen language has basic insert & delete methods, or slicing to facilitate doing it on your own.

Upvotes: 0

Related Questions