Data-Structures

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 구현 예시: ...