Data-Structures

블룸 필터 (Bloom filter) 블룸 필터(Bloom Filter)는 공간 효율적인 확률적 데이터 구조로, 원소가 집합에 속하는지 여부를 빠르게 확인하는 데 사용된다. 1970년 Burton Howard Bloom이 고안한 이 구조는 **거짓 양성(false positive)**은 허용하지만 **거짓 음성(false negative)**은 절대 발생하지 않는다. 블룸 필터는 빠른 검색과 극도의 공간 효율이 필요한 시스템에서 필수적이다. 특히 대용량 데이터 처리, 실시간 애플리케이션, 메모리 제약 환경에서 강력한 성능을 발휘한다. 다만 정확성이 절대적이라면 전통적 해시 테이블이 더 적합하다. 핵심 구성 요소 비트 배열(Bit Array): 모든 비트가 0으로 초기화된 배열 (크기 m) 해시 함수(Hash Functions): 원소를 비트 배열의 인덱스로 매핑하는 k개의 독립적 해시 함수 동작 과정 삽입(Add) 원소를 k개의 해시 함수로 해싱 → 각 결과값을 비트 배열의 인덱스로 사용 → 해당 위치의 비트를 1로 설정. 예시: 원소 “apple"을 3개의 해시 함수로 해싱 → 인덱스 1, 4, 7 → 비트 배열 [0,1,0,1,0,0,1,0,0,0] 갱신. ...

Concurrent Skip List Concurrent Skip List는 Skip List 자료구조를 기반으로 하여 멀티스레드 환경에서 동시에 삽입, 삭제, 검색 작업을 수행할 수 있도록 구현된 동시성 자료구조이다. Skip List는 여러 계층의 연결 리스트로 구성된 정렬된 데이터 구조인데, ConcurrentSkipList는 이를 멀티스레드 환경에서 안전하게 사용할 수 있도록 구현한 것이다. 이 자료구조는 락-프리(lock-free) 또는 세밀한 동기화 메커니즘을 사용하여 높은 동시성을 제공한다. 특징 동시성 지원: 여러 스레드가 동시에 자료구조에 접근하고 수정할 수 있다. 락-프리 구현: 대부분의 연산에서 락을 사용하지 않고 Compare-and-Swap(CAS) 연산을 활용한다. 확장성: 멀티코어 시스템에서 높은 확장성을 제공한다. 로그 시간 복잡도: 평균적으로 O(log n) 시간 복잡도로 검색, 삽입, 삭제 연산을 수행한다. 확률적 균형: 재조정 작업 없이 확률적으로 균형을 유지한다. 구현 방식 레벨별 락-프리 리스트: 각 레벨의 리스트를 락-프리 연결 리스트로 취급한다. CAS 연산 사용: 노드 삽입 시 CAS 연산을 사용하여 동시성을 제어한다. 마킹 기법: 노드 삭제 시 다음 참조를 마킹하여 논리적 삭제를 수행한다. 도움 메커니즘: find() 메서드가 마킹된 노드를 정리하는 역할을 수행한다. 장점 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다. 확장성: 스레드 수가 증가해도 성능 저하가 적다. 간단한 구현: 동시성 트리 구조에 비해 구현이 상대적으로 간단하다. 메모리 효율성: 일부 트리 구조보다 메모리 효율적일 수 있다. 응용 동시성 우선순위 큐: 멀티스레드 환경에서 효율적인 우선순위 큐 구현에 사용된다. 데이터베이스 시스템: 동시성 인덱싱 구조로 활용된다. 분산 시스템: 분산 환경에서의 정렬된 데이터 관리에 사용된다. 캐시 시스템: 동시성 캐시 구현에 활용될 수 있다. 동작 원리 Concurrent Skip List는 여러 레벨의 연결 리스트로 구성되며, 각 레벨은 이전 레벨의 “빠른 경로"로 작용한다. 검색, 삽입, 삭제 작업은 상위 레벨에서 시작하여 하위 레벨로 이동하면서 수행된다. ...

Read-Copy-Update (RCU) List RCU List는 동시성을 지원하는 연결 리스트 구조로, 여러 스레드가 동시에 안전하게 접근하고 수정할 수 있도록 설계되었다. RCU List는 Read-Copy-Update 메커니즘을 사용하여 구현된 동시성 연결 리스트로 읽기 작업에 대해 락을 사용하지 않으면서도 동시에 업데이트를 수행할 수 있게 해준다. 특징 락 없는 읽기: 읽기 작업은 동기화 없이 수행된다. 동시성 지원: 여러 스레드가 동시에 리스트에 접근할 수 있다. 읽기 성능 최적화: 읽기 작업의 성능이 매우 뛰어나다. 공간-시간 트레이드오프: 더 많은 공간을 사용하여 빠른 연산을 가능하게 한다. 구현 방식 삽입: 새 노드를 생성하고 원자적으로 리스트에 연결한다. 삭제: 노드를 리스트에서 제거한 후, 일정 시간이 지난 뒤 메모리를 해제한다. 읽기: 동기화 없이 리스트를 순회한다. 장점 높은 읽기 성능: 읽기 작업이 매우 빠르다. 확장성: 다중 코어 시스템에서 좋은 성능을 보인다. 데드락 방지: 읽기 작업에서 락을 사용하지 않아 데드락 위험이 줄어든다. 응용 운영체제 커널 데이터베이스 시스템 네트워크 스택 고성능 멀티스레드 애플리케이션 동작 원리 읽기 작업: 동기화 없이 리스트를 순회한다. 쓰기 작업: 새로운 버전의 데이터를 생성하고, 원자적으로 포인터를 업데이트한다. 삭제: 노드를 리스트에서 제거한 후, 모든 읽기 작업이 완료될 때까지 기다렸다가 메모리를 해제한다. 구성 요소 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다. RCU 동기화 프리미티브: rcu_read_lock(), rcu_read_unlock(), synchronize_rcu() 등 예시 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.concurrent.atomic.AtomicReference; public class LockFreeStack<T> { private static class Node<T> { final T value; Node<T> next; Node(T value) { this.value = value; } } private AtomicReference<Node<T>> head = new AtomicReference<>(null); public void push(T value) { Node<T> newNode = new Node<T>(value); while (true) { Node<T> currentHead = head.get(); newNode.next = currentHead; // CAS로 head를 새 노드로 업데이트 시도 if (head.compareAndSet(currentHead, newNode)) { return; } // 실패하면 다시 시도 } } public T pop() { while (true) { Node<T> currentHead = head.get(); if (currentHead == null) { return null; } // CAS로 head를 다음 노드로 업데이트 시도 if (head.compareAndSet( currentHead, currentHead.next)) { return currentHead.value; } // 실패하면 다시 시도 } } } 참고 및 출처

Lock-free Queue Lock-free Queue는 락(lock)을 사용하지 않고 동시성을 제공하는 FIFO(First-In-First-Out) 자료구조이다. 이 자료구조는 여러 생산자(producer)와 소비자(consumer)가 동시에 큐에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 큐에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Queue는 주로 다음과 같은 방식으로 구현된다: ...

Circular Linked List 이는 Linked List의 한 변형으로, 데이터를 저장하고 조직하는 특정한 방식을 제공한다. Circular Linked List(원형 연결 리스트)는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트의 변형이다. 이 구조에서는 리스트의 끝이 존재하지 않으며, 모든 노드가 연결되어 원을 형성한다. https://www.geeksforgeeks.org/circular-linked-list/ 특징 마지막 노드의 next 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다. 리스트의 어느 노드에서 시작하더라도 모든 노드를 순회할 수 있다. 리스트의 끝과 시작이 연결되어 있어 순환 구조를 가진다. 장점 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다. 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 순환적인 데이터 구조를 표현하기에 적합하다. 메모리를 효율적으로 사용할 수 있다. 단점 구현이 단순 연결 리스트보다 복잡하다. 무한 루프에 빠질 가능성이 있어 순회 중단이 어려울 수 있다. 노드 삭제 시 이전 노드를 찾기 위해 전체 리스트를 순회해야 할 수 있다. 응용 Circular Linked List는 다음과 같은 상황에서 유용하게 사용된다: ...

Circular Queue (Circular Buffer) 이는 선형 큐의 확장된 버전으로, 데이터를 효율적으로 저장하고 관리하는 특정한 방식을 제공한다. Circular Queue는 마지막 요소가 첫 번째 요소와 연결되어 원형 구조를 형성하는 큐 데이터 구조이다. 이는 ‘Ring Buffer’라고도 불리며, 고정 크기의 배열을 사용하여 데이터를 연속적인 루프로 저장한다. https://www.geeksforgeeks.org/what-is-circular-queue-circular-queue-meaning/ 특징 원형 구조: 마지막 위치가 첫 번째 위치와 연결되어 있다. FIFO (First In First Out) 원칙을 따른다. 두 개의 포인터: 큐의 front와 rear를 추적하는 두 개의 포인터를 사용한다. 고정 크기: 초기화 시 크기가 설정되며, 이후 변경이 어렵다. 장점 메모리 효율성: 선형 큐의 주요 한계인 메모리 낭비 문제를 해결한다. 빠른 연산: 삽입과 삭제 연산의 시간 복잡도가 O(1)이다. 공간 재사용: 큐의 앞부분이 비어있을 때 재사용이 가능하다. 캐시 지역성: 연속된 메모리 사용으로 CPU 캐시 성능이 향상된다. 단점 크기 제한: 고정 크기로 인해 오버플로우와 데이터 손실 가능성이 있다. 구현 복잡성: 선형 큐보다 구현이 복잡하다. 디버깅 어려움: 원형 구조로 인해 디버깅이 어려울 수 있다. 동적 크기 조정의 어려움: 크기를 동적으로 조정하기 어렵다. 응용 CPU 스케줄링: 운영 체제에서 프로세스 관리에 사용된다. 트래픽 관리 시스템: 교차로에서의 효율적인 흐름 제어에 활용된다. 메모리 관리: 운영 체제의 메모리 관리에 사용된다. 스트리밍 서비스: 오디오 및 비디오 스트리밍에 활용된다. 네트워크 패킷 관리: 라우터와 스위치에서 패킷 데이터 처리에 사용된다. 동작 원리 초기화: front와 rear 포인터를 -1로 설정한다. 삽입(Enqueue): 큐가 가득 찼는지 확인한다. rear 포인터를 원형으로 증가시킨 ((rear + 1) % size). 새 요소를 rear 위치에 삽입한다[11]. 삭제(Dequeue): 큐가 비어있는지 확인한다. front 위치의 요소를 반환한다. front 포인터를 원형으로 증가시킨다 ((front + 1) % size). 구성 요소 배열: 데이터를 저장하는 고정 크기의 배열. front 포인터: 큐의 첫 번째 요소를 가리킨다. rear 포인터: 큐의 마지막 요소를 가리킨다. size: 큐의 최대 크기를 나타낸다. 구현 방식 JavaScript를 사용한 Circular Queue 구현 예시: ...

Doubly Linked List Doubly Linked List는 노드들이 양방향으로 연결된 선형 데이터 구조로, 각 노드가 데이터와 이전 노드, 다음 노드를 가리키는 포인터를 포함하고 있다. Doubly Linked List는 각 노드가 데이터와 두 개의 링크 필드를 가지고 있는 있으며, 이 두 개의 링크는 이전 노드(previous node)와 다음 노드(next node)를 가리킨다. 이러한 구조로 인해 리스트의 양방향 순회가 가능해진다. 과 끝(테일)을 모두 가리키는 포인터를 유지한다. 순환 구조: 마지막 노드의 다음 노드는 첫 번째 노드를, 첫 번째 노드의 이전 노드는 마지막 노드를 가리킬 수 있다. 장점 양방향 탐색: 리스트를 앞뒤로 탐색할 수 있어 효율적인 검색이 가능하다. 삽입과 삭제의 효율성: 노드의 삽입과 삭제가 O(1) 시간 복잡도로 수행된다. 리스트 끝에서의 연산: 테일 포인터를 통해 리스트의 마지막 요소에 즉시 접근할 수 있다. 단점 메모리 사용량 증가: 각 노드가 두 개의 포인터를 저장해야 하므로 메모리 사용량이 증가한다. 구현의 복잡성: 단일 연결 리스트에 비해 구현이 더 복잡하다. 삽입과 삭제 시 포인터 조작: 노드 삽입과 삭제 시 여러 포인터를 조작해야 한다. 응용 웹 브라우저의 앞으로/뒤로 탐색 기능 음악 플레이어의 재생 목록 운영 체제의 작업 스케줄링 캐시 구현 복잡한 데이터 구조(예: 그래프)의 기본 구성 요소 동작 원리 삽입: 새 노드를 생성하고 이전 노드와 다음 노드의 포인터를 적절히 조정한다. 삭제: 삭제할 노드의 이전 노드와 다음 노드를 서로 연결하고 해당 노드를 메모리에서 해제한다. 탐색: 헤드나 테일에서 시작하여 원하는 노드를 찾을 때까지 포인터를 따라 이동한다. 구성 요소 노드: 데이터와 이전/다음 노드를 가리키는 두 개의 포인터로 구성된다. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다. 테일 포인터: 리스트의 마지막 노드를 가리킨다. 구현 방식 JavaScript를 사용한 Doubly Linked List 구현 예시: ...

Skip List Skip List는 정렬된 연결 리스트를 기반으로 하여 빠른 검색, 삽입, 삭제 연산을 지원하는 확률적 데이터 구조이다. Skip List는 여러 레벨의 연결 리스트로 구성된 데이터 구조로, 각 레벨은 그 아래 레벨의 일부 요소를 포함하며, 최하위 레벨은 모든 요소를 포함한다. https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg 특징 다중 레벨 구조: 여러 층의 연결 리스트로 구성된다. 확률적 균형: 랜덤화를 통해 구조의 균형을 유지한다. 정렬 상태 유지: 요소들은 정렬된 순서로 유지된다. 장점 빠른 검색: 평균 O(log n) 시간 복잡도로 검색이 가능하다. 효율적인 삽입/삭제: 평균 O(log n) 시간에 삽입과 삭제가 가능하다. 구현의 단순성: 균형 이진 탐색 트리에 비해 구현이 간단하다. 단점 추가 메모리 사용: 여러 레벨의 포인터로 인해 추가 메모리가 필요하다. 확률적 성능: 최악의 경우 O(n) 시간 복잡도가 발생할 수 있다. 응용 데이터베이스 인덱싱: RocksDB와 같은 키-값 저장소에서 사용된다. 메모리 관리: 비휘발성 메모리 최적화에 활용된다. 캐시 구현: 효율적인 캐시 시스템 구축에 사용된다. 동작 원리 검색: 최상위 레벨에서 시작하여 목표 값보다 작은 노드를 따라 이동하고, 큰 값을 만나면 아래 레벨로 내려간다. 삽입: 랜덤하게 레벨을 결정하고, 해당 레벨까지 노드를 생성하여 연결한다. 삭제: 노드를 찾아 모든 레벨에서 제거한다. 구성 요소 노드: 키, 값, 여러 레벨의 다음 노드 포인터를 포함한다. 헤드 노드: 모든 레벨의 시작점 역할을 한다. 레벨: 여러 층의 연결 리스트 구조를 형성한다. 구현 방식 JavaScript를 사용한 Skip List 구현 예시: ...

Array vs. Linked List 데이터 구조는 프로그래밍에서 데이터를 효율적으로 저장하고 관리하기 위한 방법을 제공합니다. 이 중에서도 배열과 연결 리스트는 가장 기본적이면서도 중요한 데이터 구조이다. 두 구조는 서로 다른 특성과 장단점을 가지고 있어 적절한 상황에 맞게 선택해 사용해야 한다. 배열은 인덱스를 통한 빠른 접근과 간단한 구현이 장점이지만, 크기가 고정되어 있고 중간 삽입/삭제가 비효율적이다. 반면 연결 리스트는 동적 크기 조정과 효율적인 삽입/삭제가 장점이지만, 임의 접근이 불가능하고 추가 메모리를 사용한다. 적절한 상황에 맞는 자료구조 선택은 효율적인 프로그램 개발의 핵심이다. 따라서 문제의 특성과 요구사항을 잘 분석하여 최적의 자료구조를 선택해야 한다. 때로는 두 자료구조의 장점을 결합한 하이브리드 접근 방식이나 다른 고급 자료구조를 활용하는 것이 더 나은 해결책이 될 수도 있다. ...