Janusz Walig&#243;ra - 1 year ago 84
C Question

# Random access cyclical data structure with two defined operations

As input I recive a list of natural integers.
I have to store them inside a structure that enables me to go from the last element to the first without much problem.

The task is to perform t (number given from the start) operations on this data structure. Starting from the first number given as input (i=0):

If data[i] % 2 == 0 -> perform operation R

else -> perform operation X

operation R: remove element with index position i+1, and move to the right as many times as was the value of removed element.

operation X: take the value of data[i] element and insert new element in front of that one with value data[i]-1. Then move data[i] times to the right.

example (i->n means that i points to el. with value n):

input: 3 1 2 3

t = 3

data = [ 1, 2, 3 ]

`````` 1.
i->1
operation X,
result: [ 1, 0, 2, 3 ]

2.
i->0
operation R,
result: [ 1, 0, 3 ]

3.
i->1
operation X,
result: [ 1, 0, 0, 3 ]
``````

The real problem occurs when the value of t is very large.
I tried two implementations:

• One based on linked list. I know it works because the result is correct, but execution time is close to 2-3 minutes.

• One based on an array but the execution time is just a little faster.

Here is the fragment that takes 99,99% of execution time:

``````while(t--){
c = current -> value;
if(c % 2 == 0){
c = current -> next -> value;
Node* n = current -> next -> next;
free(current -> next);
current -> next = n;

--size;
}
else{
Node* n = getNode(current -> next);
current -> next = n;
n -> value = c-1;

++size;
}

c %= size;
while(c--){
current = current->next;
}
}
``````

getNode(Node* n) returnes new node with node -> next = n.

Any insight into optimalization method/ other approach appreciated.

*edit:

``````Node* getNode(Node* nxt){
Node* first = (Node*)malloc(sizeof(Node));
first -> value = -1;
first -> next = nxt;
return first;
}
``````

• You need `t` operations, so outside loop is `O(n)`
• If you use linked lists, finding ith element is `O(n)` and moving the `ith` element around is `Theta(1)` as you are just changing the pointers making your inner while loop `O(n)` so total runtime of `O(n^2)`
• With array, finding ith element is `Theta(1)` but moving them around is `O(n)`, so inner loop is again `O(n)`, total being `O(n^2)`
Can you use a hashmap with integer index as the key and value working as if it's a linked list? Hashmaps will make both the search and move `Theta(1)` making the total `O(n)`