연결 리스트 심화 — 이중 연결부터 Skip List까지

class Node<T> {
    T data;
    Node<T> next;
}

class DoublyNode<T> {
    T data;
    DoublyNode<T> prev; // 이전 노드
    DoublyNode<T> next; // 다음 노드
}

// newNode를 node와 node.next 사이에 삽입
void insertAfter(DoublyNode<T> node, DoublyNode<T> newNode) {
    newNode.prev = node;
    newNode.next = node.next;
    if (node.next != null) {
        node.next.prev = newNode;
    }
    node.next = newNode;
}

// 특정 노드를 삭제 — 노드 참조만 있으면 O(1)
void delete(DoublyNode<T> node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    }
}

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.addFirst("A");   // 앞에 추가: O(1)
list.addLast("C");    // 뒤에 추가: O(1)
list.add(1, "B");     // 중간 삽입: O(n) — 탐색이 필요

// 양방향 탐색이 가능합니다
// get(i)는 i가 size/2보다 작으면 앞에서, 크면 뒤에서 탐색
String middle = list.get(1); // 내부적으로 최적화된 탐색

// LRU 캐시에서 이중 연결 리스트 활용 (간략)
// Java의 LinkedHashMap이 내부적으로 이 구조를 사용합니다
LinkedHashMap<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100; // 100개 초과 시 가장 오래된 항목 제거
    }
};

class CircularList<T> {
    Node<T> tail; // 마지막 노드 (tail.next = head)

    void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (tail == null) {
            tail = newNode;
            tail.next = tail; // 자기 자신을 가리킴
        } else {
            newNode.next = tail.next; // 새 노드가 head를 가리킴
            tail.next = newNode;      // 기존 tail이 새 노드를 가리킴
            tail = newNode;           // 새 노드가 tail이 됨
        }
    }
}

Level 3: head ──────────────────────── 50 ────────── nil
Level 2: head ────────── 25 ────────── 50 ────── 75 ── nil
Level 1: head ── 10 ── 25 ── 30 ── 50 ── 60 ── 75 ── nil
Level 0: head ── 10 ── 20 ── 25 ── 30 ── 40 ── 50 ── 60 ── 70 ── 75 ── 80 ── nil

// 레벨을 확률적으로 결정
int randomLevel() {
    int level = 0;
    // 50% 확률로 레벨을 올림
    while (Math.random() < 0.5 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

class SkipListNode<T extends Comparable<T>> {
    T value;
    SkipListNode<T>[] forward; // 각 레벨의 다음 노드

    @SuppressWarnings("unchecked")
    SkipListNode(T value, int level) {
        this.value = value;
        this.forward = new SkipListNode[level + 1];
    }
}

class SkipList<T extends Comparable<T>> {
    private static final int MAX_LEVEL = 16;
    private SkipListNode<T> head;
    private int currentLevel;

    SkipList() {
        head = new SkipListNode<>(null, MAX_LEVEL);
        currentLevel = 0;
    }

    // 검색: O(log n) 평균
    boolean search(T target) {
        SkipListNode<T> current = head;
        for (int i = currentLevel; i >= 0; i--) {
            while (current.forward[i] != null &&
                   current.forward[i].value.compareTo(target) < 0) {
                current = current.forward[i]; // 같은 레벨에서 전진
            }
        }
        current = current.forward[0];
        return current != null && current.value.compareTo(target) == 0;
    }
}

# 요소 추가: Skip List에 삽입 — O(log n)
ZADD leaderboard 100 "player1"
ZADD leaderboard 200 "player2"

# 점수 기반 범위 조회: Skip List를 따라가며 수집
ZRANGEBYSCORE leaderboard 100 200

# 순위 조회: Skip List에서 앞의 노드 수를 세서 계산
ZRANK leaderboard "player1"