스킵 리스트 편집하기 (부분)

==예제==
다음은 Python으로 구현한 스킵 리스트의 주요 연산(탐색, 삽입, 삭제) 예시이다.

<syntaxhighlight lang="python">
import random

class SkipNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level, p):
        self.max_level = max_level  # 최대 레벨
        self.p = p                  # 노드가 상위 레벨에 포함될 확률
        self.header = SkipNode(float('-inf'), max_level)
        self.level = 0             # 현재 리스트의 최대 레벨

    def random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def look_up(self, key):
        u = self.header
        for i in reversed(range(self.level + 1)):
            while u.forward[i] and u.forward[i].key <= key:
                u = u.forward[i]
        return u  # key 이하의 가장 큰 노드 반환

    def search(self, key):
        node = self.look_up(key)
        return node if node.key == key else None

    def insert(self, key):
        update = [None] * (self.max_level + 1)
        u = self.header
        for i in reversed(range(self.level + 1)):
            while u.forward[i] and u.forward[i].key < key:
                u = u.forward[i]
            update[i] = u

        node = u.forward[0]
        if node and node.key == key:
            return  # 중복 키는 삽입하지 않음

        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header
            self.level = lvl

        new_node = SkipNode(key, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def delete(self, key):
        update = [None] * (self.max_level + 1)
        u = self.header
        for i in reversed(range(self.level + 1)):
            while u.forward[i] and u.forward[i].key < key:
                u = u.forward[i]
            update[i] = u

        node = u.forward[0]
        if node and node.key == key:
            for i in range(self.level + 1):
                if update[i].forward[i] != node:
                    continue
                update[i].forward[i] = node.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1

# 실행 예시
if __name__ == "__main__":
    sl = SkipList(max_level=4, p=0.5)
    for k in [3, 6, 7, 9, 12, 19]:
        sl.insert(k)

    print("Search 6:", sl.search(6).key if sl.search(6) else "Not Found")
    sl.delete(6)
    print("Search 6 after deletion:", sl.search(6).key if sl.search(6) else "Not Found")
</syntaxhighlight>

'''자료 구조'''
위 구현은 다음과 같은 구조를 따른다.
*각 노드는 key 값을 가지며, 최대 max_level+1 개의 forward 포인터를 가진다.
*SkipList는 확률 p를 기준으로 랜덤하게 레벨을 결정하고, 삽입 시 각 레벨에 노드를 연결한다.
*look_up 연산은 상위 레벨부터 오른쪽으로 이동하며 key 이하의 가장 큰 노드를 찾아 반환한다.