Introduction to Skip Lists in C Programming
Skip lists are highly efficient probabilistic data structures that provide a relatively simple way to perform quick searches, insertions, and deletions. They were first introduced by William Pugh in his 1990 paper Skip Lists: A Probabilistic Alternative to Balanced Trees. Skip lists are particularly useful when dealing with large datasets where operations like searching, insertion, and deletion need to be performed quickly.
Understanding the Concept of Skip Lists
Imagine you have a long list of numbers, arranged in sorted order. If you wanted to find a specific number in this list, you would have to start from the beginning and traverse sequentially until you found it, or you could use binary search if the list is implemented as an array. However, both methods can be slow when dealing with very large lists.
Skip lists tackle this problem by providing multiple levels of linked lists, allowing you to skip over many elements during a search operation. At the bottom level, you have a regular singly linked list containing all the elements. Above this level, there may be one or more linked lists that contain only a subset of the elements. The topmost level typically contains just a few pointers that span large sections of the lower levels, thus enabling faster access to elements.
Each node in a skip list contains a key (or value), multiple forward pointers (or levels), and potentially other data (like a payload). The number of levels in each node is determined randomly, which helps maintain a roughly balanced structure without the overhead of maintaining strict balance conditions like those required in AVL trees or Red-Black trees.
Structure of a Skip List
A skip list consists of several layers, starting from the base layer which holds all the elements. Each element has a certain probability assigned to it to determine how many levels it spans above the base. Typically, this probability is ( \frac{1}{2} ) and higher layers are exponentially less dense. For example, each element on the second highest level might appear on the fourth highest level with half the probability of appearing on the second highest level.
Here’s a typical structure of a skip list node:
struct Node {
int key;
struct Node* forward[LEVELS]; // LEVELS is the maximum number of levels in the entire skip list
};
The base layer of a skip list is similar to a standard linked list:
head → [ ] → [ ] → [ ] → [ ] → NULL (Base Level)
Higher levels might look like this:
head → [ ] → [ ] → [ ] → NULL (Level 3)
head → [ ] → [ ] → [ ] → NULL (Level 2)
head → [ ] → [ ] → [ ] → [ ] → NULL (Level 1)
In the above example, LEVELS is set to 4, but individual nodes may not span all of these levels. For instance, a node with value 3 might only span levels 1 and 2.
Benefits of Skip Lists
- Simplicity: Unlike balanced trees, skip lists have a relatively straightforward design and code implementation.
- Expected O(log n) Performance: On average, skip lists perform operations such as search, insertion, and deletion in ( O(\log n) ) time.
- Randomized Levels: The randomization ensures that the data structure remains balanced with high probability without the need for meticulous balancing mechanisms.
- Ease of Implementation: Because they are based on linked lists, skip lists are easier to implement than sophisticated balanced tree algorithms.
Drawbacks of Skip Lists
- Worst-case Performance: The worst-case performance is ( O(n) ) for search, insertion, and deletion, although this is unlikely due to the probabilistic nature of the structure.
- Space Overhead: Skip lists require additional space to store the extra levels and corresponding forward pointers.
- Determinism: The randomized nature of skip lists makes them non-deterministic, which might not be suitable for certain applications.
Basic Operations on Skip Lists
Let's go through the basic operations on a skip list: creating a skip list, searching, insertion, and deletion.
1. Creating a Skip List:
To create a skip list, initialize the head node with multiple levels and fill forward pointers with NULL.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LEVELS 16
#define PROBABILITY 0.5
struct Node {
int key;
struct Node* forward[MAX_LEVELS];
};
struct SkipList {
int max_level;
int level;
struct Node* header; // This points to the first node at each level
};
struct Node* create_node(int key, int level) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->key = key;
for (int i = 0; i <= level; i++) {
n->forward[i] = NULL;
}
return n;
}
struct SkipList* create_skip_list() {
struct SkipList* sl = malloc(sizeof(struct SkipList));
sl->max_level = MAX_LEVELS;
sl->level = 0;
struct Node* header = create_node(-1, MAX_LEVELS - 1); // Header node with key -1 for sentinel purpose
for (int i = 0; i < MAX_LEVELS; i++) {
header->forward[i] = NULL;
}
sl->header = header;
srand(time(NULL)); // Seed for random functions
return sl;
}
2. Searching in a Skip List:
When searching, you start from the highest non-null level and move right until you find a key greater than the target key. Then, you move down one level and repeat the process until you reach the base level. If the key exists, it will be directly below where you stopped moving right at the last step.
// Function to search an item in skip list
int skip_list_search(struct SkipList* sl, int key) {
struct Node* current = sl->header;
for (int i = sl->level; i >= 0; i--) {
while (current->forward[i] != NULL &&
current->forward[i]->key < key){
current = current->forward[i];
}
}
// We reached level 0 and forward pointer to right, now go down to 0th level
current = current->forward[0];
// Check if we arrived at the target item
return (current != NULL && current->key == key);
}
3. Inserting into a Skip List:
Insertion requires you to keep track of the path while searching for the insertion position. Once found, a new node is created with a random number of levels, and its forward pointers are adjusted appropriately to fit in the path at each of its levels.
// Random level generator
int random_level(void) {
int lvl = 0;
while ((rand()/(double)RAND_MAX) < PROBABILITY && lvl < MAX_LEVELS) {
lvl++;
}
return lvl;
}
// Function to insert a value in skip list
void skip_list_insert(struct SkipList* sl, int key) {
struct Node* update[MAX_LEVELS];
memset(update, 0, sizeof(update));
struct Node* current = sl->header;
// Start from the top most level and move down a level at a time
for (int i = sl->level; i >= 0; --i) {
// Move to right in current level until you find a node with key greater than key to insert
while (current->forward[i] && current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
// Reaching level 0 and move right one step
current = current->forward[0];
// If current key is equal to the inserting key, then update the forward pointer of that node
if (current == NULL || current->key != key) {
// Create a new node with random level generated
int new_level = random_level();
if(new_level > sl->level) {
// Initialize update value to header for the new levels
for(int i=sl->level+1; i<new_level+1; i++)
update[i] = sl->header;
// Update max level in SL
sl->level = new_level;
}
// Create new node with random level, insert node by updating the forward pointer of nodes
// which comes before it
struct Node* n = create_node(key, new_level);
for(int i =0; i<=new_level; i++) {
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
}
}
4. Deleting from a Skip List:
Deletion involves keeping track of the path, similar to the search and insertion operations. You find the node to delete and adjust the forward pointers of nodes on each level to bypass the deleted node.
void skip_list_delete(struct SkipList* sl, int key) {
struct Node *update[MAX_LEVELS], *current = sl->header;
// Start from highest level and retrace the search path to store nodes having key bigger than input key
for(int i = sl->level ; i >= 0 ; i--) {
while(current->forward[i] != NULL && current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
// Reach level 0 and see if we find a node to remove
current = current->forward[0];
// If current node is target node
if(current != NULL && current->key == key) {
// For each level, update the forward pointers so that they skips current node
for(int i = 0; i <= sl->level; i++) {
// If at level i, next node is not target node, break the loop, no need to move further level down
if(update[i]->forward[i] != current)
break;
update[i]->forward[i] = current->forward[i];
}
// Remove all levels having no elements
while(sl->level > 0 && sl->header->forward[sl->level] == NULL)
sl->level--;
free(current);
}
}
Conclusion
Skip lists offer a practical alternative to traditional balanced tree structures. Their simplicity, combined with their expected logarithmic performance for essential operations, makes them particularly attractive for many real-world applications involving large datasets. However, their non-deterministic nature and increased space usage should be considered as trade-offs when choosing between different data structures. Implementing skip lists in C involves carefully managing linked list nodes and their forward pointers across multiple levels to ensure fast operations.
Skip lists are a testament to the power of randomness in algorithms, illustrating how simple probabilistic techniques can lead to efficient results. They remain an area of active research and application in computer science.
C Programming Data Structures: Skip List Intro
Introduction to Skip Lists
Skip lists are a probabilistic data structure that allows for efficient search, insertion, and deletion operations with an average time complexity of (O(\log n)). They are an alternative to balanced trees and maintain order among elements by using multiple levels of linked lists.
Step-by-Step Guide for Beginners
In this guide, we will walk you through setting up a basic Skip List in C, running a simple application, and understanding the data flow through important steps.
Setting Up the Development Environment
Before we begin, ensure that you have a working C compiler. Some popular choices are GCC and Clang. For this example, we'll use GCC.
Install GCC:
- On Linux, you can install GCC via package manager:
sudo apt-get install gcc - On Windows, you can download it from MinGW.
- On macOS, you can install Xcode Command Line Tools:
xcode-select --install
- On Linux, you can install GCC via package manager:
Create a Project Directory:
mkdir skip_list_example cd skip_list_example
Writing the Code: Skip List Data Structure
Define the Node Structure:
#define MAX_LEVEL 16 #define P 0.5 typedef struct snode { int value; struct snode *forward[MAX_LEVEL]; } skip_node; typedef struct { int level; skip_node *header; } skip_list;Initialize the Skip List:
#include <stdio.h> #include <stdlib.h> skip_list* create_skip_list() { skip_list *list = (skip_list *)malloc(sizeof(skip_list)); if (!list) { printf("Memory allocation failed\n"); return NULL; } list->level = 1; list->header = (skip_node *)malloc(sizeof(skip_node)); if (!list->header) { printf("Memory allocation failed\n"); return NULL; } for (int i = 0; i < MAX_LEVEL; i++) { list->header->forward[i] = NULL; } return list; }Random Level Generation:
int random_level() { int level = 1; while (rand() < RAND_MAX * P && level < MAX_LEVEL) { level++; } return level; }Insertion Function:
void insert(skip_list *list, int value) { skip_node *update[MAX_LEVEL]; skip_node *current = list->header; for (int i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->value < value) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->value != value) { int level = random_level(); if (level > list->level) { for (int i = list->level; i < level; i++) { update[i] = list->header; } list->level = level; } skip_node *new_node = (skip_node *)malloc(sizeof(skip_node)); if (!new_node) { printf("Memory allocation failed\n"); return; } new_node->value = value; for (int i = 0; i < level; i++) { new_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = new_node; } } }Search Function:
skip_node* search(skip_list *list, int value) { skip_node *current = list->header; for (int i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->value < value) { current = current->forward[i]; } } current = current->forward[0]; if (current && current->value == value) { return current; } return NULL; }Deletion Function:
void delete(skip_list *list, int value) { skip_node *update[MAX_LEVEL]; skip_node *current = list->header; for (int i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->value < value) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; for (int i = 0; i < list->level; i++) { if (update[i]->forward[i] != current) { break; } update[i]->forward[i] = current->forward[i]; } free(current); while (list->level > 1 && list->header->forward[list->level - 1] == NULL) { list->level--; } }
Running the Application
Create a main.c file with the following content:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
srand(time(NULL));
skip_list *list = create_skip_list();
if (!list) return 1;
insert(list, 3);
insert(list, 6);
insert(list, 7);
insert(list, 9);
insert(list, 12);
insert(list, 19);
insert(list, 17);
insert(list, 26);
insert(list, 21);
insert(list, 25);
printf("Searching for 19: %s\n", search(list, 19) ? "Found" : "Not Found");
printf("Searching for 5: %s\n", search(list, 5) ? "Found" : "Not Found");
delete(list, 12);
printf("After deleting 12, searching for 12: %s\n", search(list, 12) ? "Found" : "Not Found");
// Free allocated memory if necessary
// We skip the freeing for simplicity here
return 0;
}
Compilation and Execution
Compile the Code: In your terminal navigate to the
skip_list_exampledirectory where yourmain.cfile is located and run:gcc -o skip_list_example main.cRun the Program: After successful compilation, run the program:
./skip_list_exampleYou should see the following output:
Searching for 19: Found Searching for 5: Not Found After deleting 12, searching for 12: Not Found
Understanding the Data Flow
- Initialization: The skip list initializes with a header node and default level 1. Each level acts as a linked list.
- Random Level Generation: The random level function determines the level of a new node, which affects the node's position in the data structure.
- Insertion: When inserting a new value, the skip list searches from the highest level down to the lowest to determine the appropriate position of the new node. It then updates pointers accordingly to maintain the order and structure of the skip list.
- Search: Searching a value proceeds similarly to insertion but stops once the value is found.
- Deletion: Deletion involves finding the node and updating pointers to bypass it, thereby removing the node from the skip list.
Conclusion
Skip lists provide a simple and efficient way to maintain ordered data with probabilistic guarantees for performance. They are particularly useful when updates (insertions and deletions) are frequent, and the data structure needs to remain balanced.
This guide provided a step-by-step example of creating, inserting, searching, and deleting in a skip list using C, giving you a foundational understanding of skip lists and their operations.
Certainly! Below are the Top 10 questions and answers regarding Skip Lists in C programming, which cover the basics, functionalities, advantages, and some examples of skip lists.
1. What is a Skip List?
Answer: A Skip List is a probabilistic data structure that allows fast search, insertion, and deletion operations in logarithmic time on average. It works similarly to a linked list but with an additional hierarchy of forward pointers at various levels, enabling faster traversal through the list. This structure reduces the number of steps needed for these operations, making it efficient for handling large datasets.
2. What are the key differences between a Skip List and a Balanced Tree?
Answer: The primary differences between Skip Lists and Balanced Trees are:
- Data Structure Type: Skip Lists are a type of linked list enhanced with multiple layers, whereas Balanced Trees (like AVL or Red-Black Trees) are hierarchical tree structures.
- Complexity: While both structures provide expected O(log n) performance for search, insertion, and deletion, Skip Lists tend to have simpler implementation due to their probabilistic nature rather than strict balancing rules.
- Randomization: Skip Lists use randomization to maintain their height, which keeps the expected time complexity low.
- Efficiency: Balanced Trees guarantee O(log n) time for all operations, but Skip Lists provide this performance probabilistically with generally equivalent efficiency.
3. How does the probability factor affect the performance of a Skip List?
Answer: In a skip list, each node can have multiple levels connected by forward pointers. The height (or the number of levels) is decided probabilistically when a node is inserted into the skip list. Typically, a coin flip decides whether to add another level or stop. This probabilistic distribution ensures that the height of the skip list remains approximately log n, where n is the number of nodes, thus maintaining the average time complexity of search, insertion, and deletion operations close to O(log n). The key advantage is that the complexity remains high even if the worst-case scenario happens infrequently, as long as its probability is low enough not to impact overall performance heavily.
4. Describe the basic operations of a Skip List: Insertion, Search, and Deletion.
Answer:
Insertion: Inserting an element into a skip list involves several steps:
- First, you start from the head node and traverse the list level by level using forward pointers until you find the correct position in the base list.
- Then, you decide the height of the new node using the probabilistic method (often flipping a coin).
- Finally, you insert the new node at every relevant level by updating the pointers of neighboring nodes.
Search: Searching for an element in a skip list is done by:
- Starting at the topmost level of the head node and moving forward using the pointer until you find a node with a value greater than or equal to the target.
- When you find such a node, you move down one level and repeat this until you reach level 0, where you either find the target element or determine it is not present.
Deletion: Deleting a node from a skip list consists of:
- Similar to search, first, locate the node at each level starting from the top.
- Once you find the node at a particular level, adjust the pointers of the surrounding nodes to bypass the node being deleted.
- Continue with this adjustment process until you’ve removed the node from all its existing levels.
5. What are the advantages of using Skip Lists over other data structures?
Answer:
- Simplicity and Ease of Implementation: Skip Lists are easier to implement compared to AVL trees and Red-Black trees.
- Expected O(log n) Performance: They offer fast search, insertion, and deletion times on average with O(log n) expected performance.
- No Balancing Overhead: There’s no need for complicated balancing operations like rotations in trees.
- Good Cache Performance: Pointers are usually stored locally within a node, providing better cache locality than tree-based structures.
6. Explain the role of randomization in Skip Lists.
Answer: Randomization is crucial in Skip Lists as it determines the height of newly inserted nodes, contributing to their expected optimal performance. Without randomization, a skip list could degrade to a singly linked list, leading to O(n) time complexity for operations. Typically, upon inserting a new node, the height is determined by flipping a biased coin, where the probability p of adding an extra level at each step is usually set to 1/2. The randomization helps distribute nodes across different levels, ensuring the skip list retains its logarithmic average depth even in unfavorable distributions of input data. This random height assignment ensures no specific structure needs to be maintained, simplifying the operations and reducing the overhead often associated with strictly balanced data structures like trees.
7. How do you create a Skip List in C?
Answer: To create a skip list in C, you need to define the levels and the nodes. Below is a simple implementation outline:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define PROBABILITY 0.5 // Probability for each level increase
#define MAX_LEVEL 16 // Max possible level
typedef struct Node {
int data;
struct Node* next[MAX_LEVEL]; // Forward pointers array
} Node;
Node* create_node(int level, int data) {
Node* node = (Node*)calloc(1, sizeof(Node));
node->data = data;
return node;
}
typedef struct SkipList {
Node* head; // Head node
int max_level; // Maximum level of the skip list
} SkipList;
SkipList* create_skip_list() {
SkipList* s_list = (SkipList*)calloc(1, sizeof(SkipList));
s_list->max_level = 0;
Node* head = create_node(MAX_LEVEL, -1);
for (int i = 0; i <= MAX_LEVEL; i++)
head->next[i] = s_list->head; // Initially point all forward pointers to NULL
s_list->head = head;
return s_list;
}
bool is_random_level() {
int level = 1;
while (level < MAX_LEVEL && ((double)rand()/RAND_MAX) < PROBABILITY) {
level++;
}
return level;
}
8. What is the probability used while choosing the height of a new node during insertion?
Answer: While choosing the height of a new node in a Skip List during insertion, a common approach is to use a probability of ( \frac{1}{2} ) (or sometimes ( \frac{1}{4} ) depending on the design). Specifically, a new node is given height 1. At each subsequent level, the node is promoted by flipping a coin with the assigned probability (e.g., ( \frac{1}{2} )). If the coin flip results in heads (success), you add another level; if tails (failure), you stop.
This probabilistic growth ensures that the height of any node is bounded by ( O(\log n) ), contributing to the efficient performance of operations. The exact probability can vary, but the key idea is to keep the height growth controlled and ensure the skip list remains flat enough for efficient operations.
9. Can you provide a function to insert a node in a skip list in C?
Answer: Certainly! Here's a function to insert a node in a skip list in C. This function uses the previously defined structures and functions to perform the insertion with probabilistic level assignment.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define PROBABILITY 0.5 // Probability for each level increase
#define MAX_LEVEL 16 // Max possible level
typedef struct Node {
int data;
struct Node* next[MAX_LEVEL]; // Forward pointers array
} Node;
Node* create_node(int level, int data) {
Node* node = (Node*)calloc(1, sizeof(Node));
node->data = data;
return node;
}
typedef struct SkipList {
Node* head;
int max_level; // Maximum level currently used
} SkipList;
SkipList* create_skip_list() {
SkipList* s_list = (SkipList*)calloc(1, sizeof(SkipList));
s_list->max_level = 0;
Node* head = create_node(MAX_LEVEL, -1); // Sentinel node with maximum level
for (int i = 0; i <= MAX_LEVEL; i++) {
head->next[i] = NULL;
}
s_list->head = head;
return s_list;
}
int random_level() {
int level = 1;
while (level < MAX_LEVEL && ((float)rand() / RAND_MAX) < PROBABILITY) {
level++;
}
return level;
}
void insert(SkipList*s_list, int data) {
Node* current = s_list->head;
Node* update[MAX_LEVEL + 1];
// Save pointers to the nodes after which the new node will be inserted
for (int i = s_list->max_level; i >= 0; i--) {
while (current->next[i] != NULL && current->next[i]->data < data)
current = current->next[i];
update[i] = current;
}
// Generate the level for the new node
int new_level = random_level();
if (new_level > s_list->max_level) {
for (int i = s_list->max_level + 1; i <= new_level; i++)
update[i] = s_list->head; // Extend the update pointers to the new level
s_list->max_level = new_level;
}
// Create a new node with the generated level
Node* new_node = create_node(new_level, data);
// Insert the new node into each level
for (int i = 0; i <= new_level; i++) {
new_node->next[i] = update[i]->next[i];
update[i]->next[i] = new_node;
}
printf("Successfully inserted %d\n", data);
}
int main() {
srand(time(NULL)); // Seed the random number generator
SkipList* s_list = create_skip_list();
insert(s_list, 3);
insert(s_list, 6);
insert(s_list, 9);
insert(s_list, 4);
return 0;
}
10. How can Skip Lists be adapted for use as a map or dictionary in C?
Answer: Skip Lists can be adapted for use as maps or dictionaries by storing key-value pairs in each node instead of just integer values. Here, we modify the node structure to store keys and values and adapt the skip list functions for these operations.
Modified Node Structure:
typedef struct Node {
int key;
void* value;
struct Node* next[MAX_LEVEL];
} Node;
Insert Function Adapted for Key-Value Pairs:
void* insert_skiplist(SkipList* s_list, int key, void* value) {
Node* current = s_list->head;
Node* update[MAX_LEVEL + 1];
// Identify the right place to insert the new node
for (int i = s_list->max_level; i >= 0; i--) {
while (current->next[i] != NULL && current->next[i]->key < key)
current = current->next[i];
update[i] = current;
}
// Determine the level of the new node
int new_level = random_level();
if (new_level > s_list->max_level) {
for (int i = s_list->max_level + 1; i <= new_level; i++) {
update[i] = s_list->head; // Extend the update pointers to the new level
}
s_list->max_level = new_level;
}
// Create a new node
Node* new_node = create_node(new_level, key);
new_node->value = value;
// Update pointers to insert the new node
for (int i = 0; i <= new_level; i++) {
new_node->next[i] = update[i]->next[i];
update[i]->next[i] = new_node;
}
printf("Inserted key: %d, Value: %p\n", key, new_node->value);
return new_node->value;
}
Search Function Adapted for Key Lookup:
void* search_skiplist(SkipList* s_list, int key) {
Node* current = s_list->head;
// Traverse the skip list level by level
for (int i = s_list->max_level; i >= 0; i--) {
while (current->next[i] != NULL && current->next[i]->key < key)
current = current->next[i];
}
// Move to the bottom level and check if the node we want is present
current = current->next[0];
if (current != NULL && current->key == key) {
printf("Found key %d, Value: %p\n", key, current->value);
return current->value;
}
printf("Key %d not found\n", key);
return NULL;
}
Example Usage:
int main() {
srand(time(NULL)); // Seed the random number generator
SkipList* s_list = create_skip_list();
int* val1 = malloc(sizeof(int));
int* val2 = malloc(sizeof(int));
int* val3 = malloc(sizeof(int));
*val1 = 10;
*val2 = 20;
*val3 = 30;
insert_skiplist(s_list, 3, val1);
insert_skiplist(s_list, 6, val2);
insert_skiplist(s_list, 9, val3);
insert_skiplist(s_list, 4, NULL);
search_skiplist(s_list, 3); // Should find
search_skiplist(s_list, 10); // Should not find
return 0;
}
In this adaptation, each node stores a key and a value, and the search and insertion functions use keys to locate nodes in the skip list. This setup allows the skip list to serve as a dynamic associative array, similar to a map or dictionary in other programming languages.
By understanding these fundamentals, you can effectively implement and utilize Skip Lists in your C programming projects, leveraging their probabilistic nature and simplicity.