I have problems about skiplist removal, but I don't really see how it fails(A lot of testcases did work well), can someone help me? Thanks!
I think most of the functions and main structure are correct, only the removal has some potential problems, my list is based on a descending order. I need to include the cases of empty list or remove not-existed number(just skip it).
It has really confused me for a long time, I think I need to think of some extreme cases on this one.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<limits.h>
#define MaxLevel 65
int currLevel = 0;
typedef struct Node
{
long long data;
struct Node *next;
struct Node *last;
struct Node *up;
struct Node *down;
} Node;
typedef struct
{
int level;
struct Node *node;
} skipStep;
bool CoinFlip(long long k, int i)
{
return k >> (i - 1) & 1;
}
void skiplist_insert(Node *SL[], long long data)
{
int level = currLevel;
Node *last = NULL;
skipStep steps[MaxLevel];
for (int i = 0 ; i < MaxLevel; i++)
{
steps[i].level = 0;
steps[i].node = SL[i];
}
Node* Head = SL[level];
Node* tmp = Head->next;
while(level > 0 && data > tmp->data)
{
level--;
Head = SL[level];
tmp = Head->next;
}
while(level > 0)
{
while(tmp != NULL)
{
if (data > tmp->data)
{
steps[level].level = level;
if (last != NULL)
{
steps[level].node = last;
}
tmp = last->down;
level--;
break;
}
last = tmp;
tmp = tmp->next;
}
if(tmp == NULL)
{
steps[level].level = level;
if (last != NULL)
{
steps[level].node = last;
}
tmp = last->down;
level--;
}
}
while (tmp != NULL)
{
if (data > tmp->data)
{
break;
}
last = tmp;
tmp = tmp->next;
}
Node *newData = (Node *)malloc(sizeof(Node));
newData->data = data;
newData->up = NULL;
newData->down = NULL;
newData->last = NULL;
newData->next = NULL;
int k = 0;
if(last == NULL)
{
Head = SL[0];
Node *headNext = Head->next;
if(headNext != NULL)
{
newData->next = headNext;
headNext->last = newData;
newData->last = Head;
}
Head->next = newData;
newData->last = Head;
}
else if(tmp == NULL)
{
last->next = newData;
newData->last = last;
}
else
{
newData->next = tmp;
tmp->last = newData;
newData->last = last;
last->next = newData;
}
while(CoinFlip(data, k + 1))
{
k++;
if(k >= MaxLevel)
{
break;
}
Node *newIndex = (Node *)malloc(sizeof(Node));
newIndex->data = data;
newIndex->down = newData;
newData->up = newIndex;
Node *node = steps[k].node;
Node *nextIndex = node->next;
node->next = newIndex;
newIndex->last = node;
newIndex->next = nextIndex;
if(nextIndex != NULL)
{
nextIndex->last = newIndex;
}
newData = newIndex;
if (k > currLevel)
{
currLevel = k;
}
}
}
Node *initSkipList(Node *skipList[])
{
for (int i = 0; i < MaxLevel; i++)
{
Node *newHead = (Node *)malloc(sizeof(Node));
newHead->data = LLONG_MAX;
newHead->down = NULL;
newHead->up = NULL;
newHead->next = NULL;
newHead->last = NULL;
skipList[i] = newHead;
}
return skipList[MaxLevel - 1];
}
Node *skiplist_search(Node *SL[], long long data)
{
if(SL[0]->next == NULL)
{
return NULL;
}
int level = currLevel;
Node *Head = NULL;
Node *tmp = NULL;
Node *last = NULL;
Head = SL[level];
tmp = Head->next;
long long endQuery = -1;
while(level > 0 && data > tmp->data)
{
level--;
endQuery = tmp->data;
Head = SL[level];
tmp = Head->next;
}
while(level > 0 )
{
while(tmp != NULL)
{
if(data > tmp->data)
{
level--;
endQuery = tmp->data;
tmp = last->down;
break;
}
printf("%lld ", tmp->data);
last = tmp;
tmp = tmp->next;
}
if(NULL == tmp)
{
tmp = last->down;
endQuery = -1;
level--;
}
}
while(!level && tmp != NULL && tmp->data >= data)
{
printf("%lld ", tmp->data);
tmp = tmp->next;
if(tmp != NULL && tmp->data == data)
{
return tmp;
}
else if(tmp == NULL || tmp->data < data)
{
return NULL;
}
}
return NULL;
}
Node *SlowGet(Node *SL[], long long data)
{
if(SL[0]->next == NULL || data > SL[0]->next->data)
{
return NULL;
}
Node *Head = SL[0];
Node *tmp = Head->next;
while(tmp != NULL && data < tmp->data)
{
printf("%lld ", tmp->data);
tmp = tmp->next;
}
if(tmp != NULL && data == tmp->data)
{
return tmp;
}
else
{
return NULL;
}
}
void skiplist_delete(Node *SL[], long long data)
{
int level = currLevel;
Node *Head = NULL;
Node *tmp = NULL;
Node *last = NULL;
Head = SL[level];
tmp = Head->next;
long long endQuery = -1;
while(level > 0 && data > tmp->data)
{
level--;
endQuery = tmp->data;
Head = SL[level];
tmp = Head->next;
}
while(level > 0)
{
while(tmp != NULL)
{
if(data > tmp->data)
{
level--;
endQuery = tmp->data;
tmp = last->down;
break;
}
last = tmp;
tmp = tmp->next;
}
if(tmp == NULL)
{
tmp = last->down;
endQuery = -1;
level--;
}
}
while(tmp != NULL)
{
if(endQuery != -1)
{
if(tmp->data > endQuery)
{
tmp = NULL;
break;
}
}
if (tmp->data == data)
{
break;
}
tmp = tmp->next;
}
if(tmp == NULL)
{
return;
}
level = 0;
Node *t_last = NULL;
Node *t_next = NULL;
while(tmp->up != NULL)
{
level++;
tmp = tmp->up;
}
while(tmp != NULL)
{
t_last = tmp->last;
t_next = tmp->next;
Node *t_down = tmp->down;
if (t_last == NULL)
{
return;
}
t_last->next = t_next;
if(t_next != NULL)
t_next->last = t_last;
else
t_last->next = NULL;
if(t_last == SL[level] && t_next == NULL)
{
currLevel--;
}
free(tmp);
tmp = t_down;
level--;
if(currLevel < 0)
{
currLevel = 0;
}
if(level < 0)
{
level = 0;
}
}
}
int main()
{
int M;
scanf("%d", &M);
Node *SL[MaxLevel];
Node *skipList = initSkipList(SL);
for (int i = 0; i < M; ++i)
{
int t;
long long k;
scanf("%d%lld", &t, &k);
Node* node = NULL;
switch(t)
{
case 1:
node = SlowGet(SL, k);
if(node != NULL)
{
printf("%lld", node->data);
}
else if(SL[0]->next == NULL || (node == NULL && k > SL[0]->next->data))
{
printf("-1");
}
printf("\n");
break;
case 2:
node = skiplist_search(SL, k);
if (node != NULL)
{
printf("%lld", node->data);
}
else if(SL[0]->next == NULL || (node == NULL && k > SL[0]->next->data))
{
printf("-1");
}
printf("\n");
break;
case 3:
skiplist_insert(SL, k);
break;
case 4:
skiplist_delete(SL, k);
break;
}
}
return 0;
}
I have wrong answers when removal, and only one runtime error, since mostly correct, I really don't know what to inspect.