Skip lists for probabilistic search in Data Structures Theory - Mini Project: Build & Apply

Skip lists for probabilistic search

📖 Scenario: Imagine you want to quickly find a friend's name in a long phone book. Instead of looking at every name one by one, you use a special method that lets you jump ahead in steps, sometimes skipping many names, to find the right page faster. This method is called a skip list.

🎯 Goal: You will build a simple model of a skip list using lists and pointers to understand how it helps in searching faster by skipping some elements probabilistically.

📋 What You'll Learn

Create a basic list of numbers representing sorted data

Add a level indicator to each element to show how many steps it can skip

Use a simple rule to assign levels to elements probabilistically

Show how the skip list structure is set up with levels for faster search

💡 Why This Matters

🌍 Real World

Skip lists are used in computer systems to speed up searching in sorted data by allowing jumps over multiple elements, making search faster than checking every item.

💼 Career

Understanding skip lists helps in software development and data engineering roles where efficient data retrieval is important, such as databases and network routing.

1

Create the base sorted list

Create a list called data with these exact sorted numbers: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91.

Data Structures Theory

# Create the list called data with the given numbers
# Your code here

Need a hint?

Use square brackets to create a list and separate numbers with commas.

2

Add level indicators for skipping

Create a list called levels with the same length as data, where each element is initially set to 1 to represent the base level of skipping.

Data Structures Theory

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# Create the levels list with all elements set to 1
# Your code here

Need a hint?

Use multiplication of a list to repeat the number 1 for the length of data.

3

Assign levels probabilistically

Use a for loop with variable i to go through each index in levels. For each index, if a random number between 0 and 1 is less than 0.5, increase levels[i] by 1 to simulate probabilistic skipping.

Data Structures Theory

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
levels = [1] * len(data)
import random
# Use a for loop with i to assign levels probabilistically
# Your code here

Need a hint?

Use random.random() to get a number between 0 and 1, then compare it to 0.5.

4

Combine data and levels to show skip list structure

Create a list called skip_list that contains tuples pairing each element in data with its corresponding level from levels using a for loop with variables value and level iterating over zip(data, levels).

Data Structures Theory

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
levels = [1] * len(data)
import random
for i in range(len(levels)):
    if random.random() < 0.5:
        levels[i] += 1
# Create skip_list as a list of tuples (value, level)
# Your code here

Need a hint?

Use a list comprehension with zip(data, levels) to pair values and levels.