랜덤 액세스 링크드 리스트에 관하여

랜덤 액세스 링크드 리스트(Random Access Linked List)는 기존의 연결 리스트(Linked List)의 단점인 느린 인덱스 접근(Random Access 불가능) 을 보완하기 위해 설계된 자료구조입니다.
일반적인 연결 리스트는 특정 인덱스에 접근하기 위해 O(n) 시간이 소요되는 반면, 랜덤 액세스 링크드 리스트는 O(log n) 혹은 O(1) 수준의 빠른 접근이 가능하도록 최적화된 구조를 가집니다.

---

1. 기존 연결 리스트의 문제점

일반적인 단일/이중 연결 리스트는 연속적인 메모리 공간이 아니라, 노드들이 포인터를 통해 연결된 형태이기 때문에 특정 위치의 데이터를 찾기 위해 항상 순차 탐색(Sequential Access) 해야 합니다.

• 배열(Array)의 경우 O(1) 시간 복잡도로 즉시 원하는 인덱스의 요소에 접근 가능하지만, 크기 조정이 어렵고 메모리 낭비가 발생할 수 있습니다.
• 반면, 연결 리스트(Linked List)는 삽입/삭제가 용이하지만, 특정 인덱스에 접근할 때 O(n) 시간이 소요되는 단점이 있습니다.

---

2. 랜덤 액세스 링크드 리스트의 개념 및 특징

랜덤 액세스 링크드 리스트는 다음과 같은 특징을 가집니다:

• 빠른 검색 가능: 특정 인덱스의 요소에 접근할 때 기존 연결 리스트보다 훨씬 빠르게 접근 가능.
• 동적 메모리 할당: 배열과 달리 크기를 미리 지정할 필요 없이 동적으로 관리 가능.
• 빠른 삽입/삭제: 기존 연결 리스트와 동일한 삽입/삭제 성능을 유지.

2.1 랜덤 액세스 기능을 구현하는 방법

랜덤 액세스를 지원하는 연결 리스트를 만들기 위해 다양한 기법이 활용됩니다.

✅ (1) Skip List 기반 접근

• Skip List는 여러 개의 레벨을 활용하여 검색 속도를 O(log n) 으로 줄이는 방식.
• 기본적인 연결 리스트 위에 추가적인 인덱스 레이어를 구성하여 빠른 탐색을 가능하게 함.

✅ (2) Hash Table 보조 방식

• 각 노드의 참조(포인터)를 해시 테이블(Hash Table)에 저장하여, 특정 노드에 대한 접근을 O(1)에 가깝게 단축하는 방식.
• 하지만 해시 충돌(Hash Collision) 처리 문제가 존재하며, 추가적인 메모리 사용량 증가.

✅ (3) 배열과 연결 리스트 혼합 방식

• 일정 개수의 노드를 묶어 배열로 관리하고, 배열 단위로 연결하여 탐색 속도를 향상.

---

3. 랜덤 액세스 링크드 리스트의 구현

3.1 Skip List 기반 예제

import java.util.Random;

class SkipListNode {
    int value;
    SkipListNode[] forward;

    public SkipListNode(int value, int level) {
        this.value = value;
        this.forward = new SkipListNode[level + 1]; // 레벨별 연결을 위한 배열
    }
}

class SkipList {
    private static final int MAX_LEVEL = 4;
    private SkipListNode head;
    private int level;
    private Random random;

    public SkipList() {
        head = new SkipListNode(-1, MAX_LEVEL);
        level = 0;
        random = new Random();
    }

    private int randomLevel() {
        int lvl = 0;
        while (random.nextInt(2) == 1 && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    public void insert(int value) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = head;

        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }

        SkipListNode newNode = new SkipListNode(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean search(int value) {
        SkipListNode current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == value;
    }
}

 

3.2 Hash Table 보조 방식 예제

import java.util.HashMap;

class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class RandomAccessLinkedList {
    private Node head;
    private HashMap<Integer, Node> indexMap;
    private int index;

    public RandomAccessLinkedList() {
        this.head = null;
        this.indexMap = new HashMap<>();
        this.index = 0;
    }

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
        indexMap.put(index++, newNode);
    }

    public Node get(int idx) {
        return indexMap.get(idx);
    }
}

---

4. 랜덤 액세스 링크드 리스트의 장단점

✅ 장점

• 특정 인덱스의 요소를 O(log n) 또는 O(1) 시간 내에 빠르게 찾을 수 있음.
• 삽입/삭제는 기존 연결 리스트와 동일한 성능을 유지.
• 동적 메모리 할당 가능하여 유연한 크기 조정이 가능.

❌ 단점

• 추가적인 인덱싱 구조(해시 테이블, 다중 레벨 링크 등)로 인해 메모리 오버헤드 발생.
• 구현이 비교적 복잡하여 유지보수가 어려울 수 있음.
• 순차 접근이 필요한 경우 오히려 기존 연결 리스트보다 성능이 떨어질 수 있음.

---

5. 마무리

랜덤 액세스 링크드 리스트는 배열과 연결 리스트의 장점을 결합한 자료구조로, 빠른 탐색 속도와 동적 데이터 관리를 가능하게 합니다.
특히, Skip List 및 Hash Table 기법을 활용하여 검색 성능을 개선할 수 있습니다.
이 자료구조를 적절히 활용하면 빠른 검색과 삽입/삭제 성능을 모두 만족하는 효율적인 데이터 구조를 설계할 수 있습니다.